当前位置:网站首页>E - food chain
E - food chain
2022-07-06 06:14:00 【RCyyds】
Portal : The food chain
The question : The theme is simple , Just look at the topic directly .
Ideas : This is a classic weighted search topic .
According to convention , We need two arrays , One is the parent node array p, The other is recording x To p[x] The weight of d[x] Array , Stipulate here x eat p[x].
This question is The difficulty lies in the array of eating and being eaten d The relationship between .
1. If x And y It is the same kind and uses the common ancestor node , Then judge d[x]-d[y])%3 Is it equal to 0, be equal to 0 It means the same as what you said , Otherwise inconsistent ,ans++;
2. If x And y It is the same kind of ancestral node without common use , let px My father node is py, Work out d[px],d[px]=d[y]-d[x];
3. If x eat y And use the common ancestor node , Then judge d[x]-d[y]-1)%3 Is it equal to 0, be equal to 0 It means the same as what you said , Otherwise inconsistent ,ans++;
4. If x eat y And there is no common ancestor node , let px My father node is py, Work out d[px],d[px]=d[y]-d[x]+1;
5. If x,y Greater than n,ans++;
Code :
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
const int N=5e4+5;
int p[N],d[N];
int find(int x)
{
if(x!=p[x])
{
int t=find(p[x]);
d[x]+=d[p[x]];
p[x]=t;
}
return p[x];
}
int main()
{
int n,k;
scanf("%d%d",&n,&k);
for (int i = 1; i <= n; i ++ ) p[i] = i;
int ans=0;
while(k--)
{
int t,x,y;
scanf("%d%d%d",&t,&x,&y);
int px=find(x),py=find(y);
if (x > n || y > n) ans ++ ;
else
{
if(t==1)
{
if(px==py&&(d[x]-d[y])%3) ans++;
else if(px!=py)
{
p[px]=py;
d[px]=d[y]-d[x];
}
}
else{
if(px==py&&(d[x]-d[y]-1)%3) ans++;
else if(px!=py)
{
p[px]=py;
d[px]=d[y]-d[x]+1;
}
}
}
}
printf("%d",ans);
return 0;
}
边栏推荐
- Fault, error, failure of functional safety
- [untitled]
- [postman] collections configuration running process
- Function of contenttype
- Configuring OSPF GR features for Huawei devices
- 黑猫带你学UFS协议第18篇:UFS如何配置逻辑单元(LU Management)
- 数据库隔离级别
- Manhattan distance and Manhattan rectangle - print back font matrix
- LeetCode 729. 我的日程安排表 I
- 数字三角形模型 AcWing 1015. 摘花生
猜你喜欢
LeetCode 729. 我的日程安排表 I
Idea new UI usage
IP day 16 VLAN MPLS configuration
功能安全之故障(fault),错误(error),失效(failure)
H3C firewall rbm+vrrp networking configuration
[postman] collections - run the imported data file of the configuration
【eolink】PC客户端安装
Seven imperceptible truths in software testing
The latest 2022 review of "graph classification research"
Manhattan distance and Manhattan rectangle - print back font matrix
随机推荐
Luogu p1460 [usaco2.1] healthy Holstein cows
[C language] string left rotation
【Postman】Monitors 监测API可定时周期运行
Cognitive introspection
Eigen sparse matrix operation
公司視頻加速播放
MPLS test report
Embedded point test of app
多线程应用的测试与调试
GTSAM中李群的運用
[course notes] Compilation Principle
Introduction to promql of # yyds dry goods inventory # Prometheus
职场进阶指南:大厂人必看书籍推荐
H3C firewall rbm+vrrp networking configuration
Cannot create PoolableConnectionFactory (Could not create connection to database server. 错误
使用Nacos管理配置
[postman] collections - run the imported data file of the configuration
VINS-Mono: A Robust and Versatile Monocular Visual-Inertial State Estimator
Summary of anomaly detection methods
Fault, error, failure of functional safety