。。
食物链
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 105599 | Accepted: 31966 |
Description
动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B， B吃C，C吃A。
现有N个动物，以1－N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。
有人用两种说法对这N个动物所构成的食物链关系进行描述：
第一种说法是"1 X Y"，表示X和Y是同类。
第二种说法是"2 X Y"，表示X吃Y。
此人对N个动物，用上述两种说法，一句接一句地说出K句话，这K句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。
1） 当前的话与前面的某些真的话冲突，就是假话；
2） 当前的话中X或Y比N大，就是假话；
3） 当前的话表示X吃X，就是假话。
你的任务是根据给定的N（1 <= N <= 50,000）和K句话（0 <= K <= 100,000），输出假话的总数。
现有N个动物，以1－N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。
有人用两种说法对这N个动物所构成的食物链关系进行描述：
第一种说法是"1 X Y"，表示X和Y是同类。
第二种说法是"2 X Y"，表示X吃Y。
此人对N个动物，用上述两种说法，一句接一句地说出K句话，这K句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。
1） 当前的话与前面的某些真的话冲突，就是假话；
2） 当前的话中X或Y比N大，就是假话；
3） 当前的话表示X吃X，就是假话。
你的任务是根据给定的N（1 <= N <= 50,000）和K句话（0 <= K <= 100,000），输出假话的总数。
Input
第一行是两个整数N和K，以一个空格分隔。
以下K行每行是三个正整数 D，X，Y，两数之间用一个空格隔开，其中D表示说法的种类。
若D=1，则表示X和Y是同类。
若D=2，则表示X吃Y。
以下K行每行是三个正整数 D，X，Y，两数之间用一个空格隔开，其中D表示说法的种类。
若D=1，则表示X和Y是同类。
若D=2，则表示X吃Y。
Output
只有一个整数，表示假话的数目。
Sample Input
100 7 1 101 1 2 1 2 2 2 3 2 3 3 1 1 3 2 3 1 1 5 5
Sample Output
3
Source
。。
1 #include <iostream> 2 #include <algorithm> 3 #include <cmath> 4 #include <stdio.h> 5 #include <cstring> 6 #include <string> 7 #include <cstdlib> 8 #include <queue> 9 #include <stack> 10 #include <set> 11 #include <vector> 12 #include <map> 13 #include <list> 14 #include <iomanip> 15 #include <fstream> 16 17 using namespace std; 18 int fa[50009],eat[50009]; 19 //不要忘记初始化数组惹qwq 20 void initailize(int n) 21 { 22 for(int i=0;i<n;++i) 23 { 24 fa[i]=i;//一开始自立门户 25 eat[i]=0;//食性是莫得食性的 26 } 27 } 28 int get(int x)//查询根节点 29 { 30 int temp; 31 if(x==fa[x]) 32 return x;//找到根节点 33 34 temp=fa[x];//没有找到根节点，但是找到了上一级 35 fa[x]=get(temp);//更新自己的根节点，找到了上一级的根节点 36 //捕食关系更新，根据自己祖宗的食性知道自己的食性 37 eat[x]=(eat[x]+eat[temp])%3;//哇呜，传说中的矢量运算了？ 38 //暂时规定其中的关系数字 0 1 2 分别代表同类/捕食/被捕食 39 return fa[x]; 40 } 41 42 int main() 43 { 44 int n,k,cnt=0; 45 scanf("%d%d",&n,&k); 46 initailize(n);//不知道有没有拼对，反正是初始化的意思 47 for(int i=1;i<=k;++i) 48 { 49 int d,x,y; 50 scanf("%d%d%d",&d,&x,&y); 51 //注意特殊情况（条件2、3），小动物的编号都已经超过了n 52 if(x>n||y>n||(x==y&&d==2))//我~吃~我~自~己~ 53 {cnt++;continue;} 54 int gx=get(x),gy=get(y);//先找一下自己祖宗 55 //如果他们祖宗不一样，那就合并成一个（所以一直合并的最终结果就是长度为2的树咯？） 56 if(gx!=gy) 57 { 58 //emm毕竟一般来说都是x吃y，所以x是y的上级祖宗，加之它是有方向的矢量，所以方便编程就是 59 fa[gy]=gx; 60 //d-1=实际捕食关系， 矢量相减就是食性距离，加3防止数字变负 61 eat[gy]=((d-1)+eat[x]-eat[y]+3)%3; 62 continue; 63 } 64 //他们已经是一个祖宗了 65 else{ 66 if(d==1)//同类 67 { 68 if(eat[x]!=eat[y])//同类的食性居然不一样？！ 69 {cnt++;continue;} 70 } 71 if(d==2)//x吃y，注意这是矢量加减（据称;滑稽），所以有方向 72 { 73 if((eat[y]-eat[x]+3)%3!=1)//x吃y但是之前说x与y是同类/被捕食的关系 74 { 75 {cnt++;continue;} 76 } 77 } 78 } 79 } 80 printf("%d ",cnt); 81 return 0; 82 }
一开始自作聪明，把get函数里return 的值直接写成temp，结果TLE 因为当x=fa[x]的时候，temp根本不会被赋值啊。
没有注释的清爽压行版本~❤
1 #include <iostream> 2 #include <algorithm> 3 #include <cmath> 4 #include <stdio.h> 5 #include <cstring> 6 #include <string> 7 #include <cstdlib> 8 #include <queue> 9 #include <stack> 10 #include <set> 11 #include <vector> 12 #include <map> 13 #include <list> 14 #include <iomanip> 15 #include <fstream> 16 17 using namespace std; 18 int fa[50009],eat[50009]; 19 20 int get(int x) 21 { 22 int temp; 23 if(x==fa[x]) 24 return x; 25 temp=fa[x]; 26 fa[x]=get(temp); 27 eat[x]=(eat[x]+eat[temp])%3; 28 return fa[x]; 29 } 30 31 int main() 32 { 33 int n,k,cnt=0; 34 scanf("%d%d",&n,&k); 35 for(int i=1;i<=n;++i){ 36 fa[i]=i; 37 eat[i]=0; 38 } 39 for(int i=1;i<=k;++i) 40 { 41 int d,x,y; 42 scanf("%d%d%d",&d,&x,&y); 43 if(x>n||y>n||(x==y&&d==2)) {cnt++;continue;} 44 int gx=get(x),gy=get(y); 45 if(gx!=gy) 46 { 47 fa[gy]=gx; 48 eat[gy]=((d-1)+eat[x]-eat[y]+3)%3; continue; 49 } 50 else{ 51 if(d==1&&(eat[x]!=eat[y])) {cnt++;continue;} 52 if(d==2&&((eat[y]-eat[x]+3)%3!=1) ) {cnt++;continue;} 53 } 54 } 55 printf("%d ",cnt); 56 return 0; 57 }