程序自动分析

这道题目让我感受到我是如此得蒟链接：程序自动分析

memset初始化数组时如果数组很大跑的会很慢！！！（龟龟太可怕了，卡了很长时间）

然后剩下的就是无脑离散和无脑冰碴鸡了

无脑程序

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <cstring>
 5 using namespace std;
 6 const int N = 1e5 + 5;
 7 int T,n,fa[N],ls[N];
 8 struct node
 9 {
10     int x,y,e;
11 }a[N];  
12 bool cmp(node a,node b)
13 {
14     return a.e>b.e;
15 }
16 int getfa(int x)
17 {
18     if(fa[x]!=x) fa[x]=getfa(fa[x]);
19     return fa[x];
20 }
21 inline int read()
22 {
23     int x=0,w=1;
24     char c=getchar();
25     while(c>'9'||c<'0') {if(c=='-') w=-1; c=getchar();}
26     while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}
27     return w*x;
28 }
29 int main()
30 {
31     ios::sync_with_stdio(false);
32     T=read();
33     while(T--)
34     {
35           int cnt=-1;
36          memset(ls,0,sizeof(ls));
37           memset(a,0,sizeof(a));
38           memset(fa,0,sizeof(fa));
39           bool flag=true;
40         n=read();
41         for(int i=1;i<=n;++i)
42         {
43             a[i].x=read(); a[i].y=read(); a[i].e=read();
44             ls[++cnt]=a[i].x;
45             ls[++cnt]=a[i].y;
46         }
47         sort(ls,ls+cnt);
48         int tmp=unique(ls,ls+cnt)-ls;
49         for(int i=1;i<=n;++i)
50         {
51            a[i].x=lower_bound(ls,ls+tmp,a[i].x)-ls;
52            a[i].y=lower_bound(ls,ls+tmp,a[i].y)-ls;   
53         } 
54         for(int i=1;i<=tmp;++i) fa[i]=i;
55         sort(a+1,a+n+1,cmp);
56         for(int i=1;i<=n;++i)
57         {
58             int t1=getfa(a[i].x),t2=getfa(a[i].y);
59             if(a[i].e) fa[t1]=t2;
60             else if(t1==t2)
61             {
62                 printf("NO
");
63                 flag=false;
64                 break;
65             }
66         }
67         if(flag) printf("YES
");
68     }
69     return 0;
70 }