QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#276701#5493. 程序自动分析SoyTony100 ✓532ms24780kbC++142.0kb2023-12-06 09:44:182023-12-06 09:44:20

Judging History

你现在查看的是最新测评结果

  • [2023-12-06 09:44:20]
  • 评测
  • 测评结果:100
  • 用时:532ms
  • 内存:24780kb
  • [2023-12-06 09:44:18]
  • 提交

answer

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<vector>
#include<map>
#include<stack>
#include<queue>
using namespace std;
typedef int ll;
typedef double db;
typedef unsigned long long ull;
const int maxn=1000005;
const int maxm=1e6+10;
const ll mod=1e9+7;
const ull base1=19260817;
const ull base2=19660813;
const ll maxxn=0x7fffffff;
const ll minxn=-0x7fffffff;
const db inf=1e13;
inline ll read(){
    ll x=0,w=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
    while(c<='9'&&c>='0'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    return x*w;
}
ll t,n;
ll fa[maxn],tot[maxn*2],cnt;
struct edge{
    ll from,to,ope;
}e[maxn];
inline ll find(ll x){
    if(fa[x]!=x) fa[x]=find(fa[x]);
    return fa[x];
}
inline bool cmp(edge x,edge y){
    return x.ope>y.ope;
}
int main(){
    t=read();
    while(t--){
        n=read();
        bool pd=true;
        memset(tot,0,sizeof(cnt));
        memset(fa,0,sizeof(fa));
        memset(e,0,sizeof(e));
        for(int i=1;i<=n;i++){
            //e[i].from=read(),e[i].to=read(),e[i].ope=read();
            scanf("%d%d%d",&e[i].from,&e[i].to,&e[i].ope);
            tot[++cnt]=e[i].from;
            tot[++cnt]=e[i].to;
        }
        sort(tot+1,tot+1+cnt);
        ll len=unique(tot+1,tot+1+cnt)-tot;
        for(int i=1;i<=n;i++){
            e[i].from=lower_bound(tot+1,tot+1+len,e[i].from)-tot;
            e[i].to=lower_bound(tot+1,tot+1+len,e[i].to)-tot;
        }
        for(int i=1;i<=len;i++){
            fa[i]=i;
        }
        sort(e+1,e+1+n,cmp);
        for(int i=1;i<=n;i++){
            ll fu=find(e[i].from),fv=find(e[i].to);
            if(e[i].ope){
                fa[fu]=fv;
            }
            else{
                if(fu==fv){
                    printf("NO\n");
                    pd=false;
                    break;
                }
            }  
        }
        if(pd) printf("YES\n");
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 10
Accepted
time: 5ms
memory: 19204kb

input:

5
2
1 2 1
1 2 0
3
1 2 1
2 3 1
3 1 1
4
1 2 1
2 3 1
3 4 1
1 4 0
2
1 2 1
2 1 1
1
1 1 1

output:

NO
YES
NO
YES
YES

result:

ok 5 lines

Test #2:

score: 10
Accepted
time: 8ms
memory: 19424kb

input:

10
1
1 2 1
1
2 2 0
10
1 2 1
2 3 1
3 5 1
5 10 1
10 100 1
10000 100 1
1 9999 0
3 2 1
10000 1 0
2 3 1
4
1 7 1
9 7 0
13 9 1
1 13 1
5
7 9 0
9 7 0
3 5 0
1 7 0
2 4 0
9
24 234 1
2837 1 1
235 877 1
242 78 0
23 1 1
223 977 0
254 76 1
235 987 0
877 987 1
9
24 234 1
2837 1 1
242 78 0
23 1 1
223 977 0
254 76 1
2...

output:

YES
NO
NO
NO
YES
NO
YES
NO
YES
YES

result:

ok 10 lines

Test #3:

score: 10
Accepted
time: 4ms
memory: 19164kb

input:

10
100
3039 366 1
608 1142 1
9794 4263 1
7148 6719 1
5824 9205 1
2757 6158 1
6183 298 1
4420 4418 1
4420 5600 0
4049 3039 1
7232 1799 1
9211 8516 1
398 389 1
4 8846 1
4492 571 1
6796 8019 1
603 571 1
575 837 1
389 1547 1
6195 8096 1
9906 6158 1
8846 9622 1
2964 571 1
9062 6119 1
7460 9719 1
5098 807...

output:

NO
YES
YES
YES
YES
YES
NO
NO
YES
YES

result:

ok 10 lines

Test #4:

score: 10
Accepted
time: 9ms
memory: 19208kb

input:

10
100
1547 7716 1
1733 8724 1
1621 5578 1
5578 3189 1
4519 3434 1
9216 4070 1
4764 5986 1
4534 9641 1
5520 8252 1
4029 3189 1
4012 1136 1
3602 5520 1
757 2121 1
3807 1088 1
9216 5578 1
8507 3620 1
4534 1088 1
4899 8252 1
4899 1941 1
3602 8451 1
438 7214 1
1547 4012 1
2121 5791 1
5105 8451 1
1887 55...

output:

YES
YES
NO
NO
YES
NO
YES
NO
NO
YES

result:

ok 10 lines

Test #5:

score: 10
Accepted
time: 12ms
memory: 19336kb

input:

10
1000
3951 3499 1
4458 5015 1
800 8958 1
702 4627 1
2052 7089 1
2456 4892 1
8683 9389 1
3922 2187 1
8170 3272 1
76 200 1
2567 2078 1
58 4897 1
8742 6328 1
8506 2462 1
1610 3150 1
9244 8025 1
7390 5968 1
4897 5015 1
2841 4592 1
2541 7630 1
7482 1157 1
2337 6156 1
4271 2349 1
2412 1750 1
8366 6196 1...

output:

NO
NO
NO
NO
YES
NO
YES
YES
NO
NO

result:

ok 10 lines

Test #6:

score: 10
Accepted
time: 66ms
memory: 19992kb

input:

10
10000
4967 5731 1
1154 4083 1
2643 9044 1
853 8116 1
1725 9222 1
975 7335 1
9579 8430 1
5832 6293 1
2621 9227 1
9620 8784 1
5617 4373 1
3185 774 1
3296 7952 1
6871 2143 1
8646 3606 1
1140 1859 1
6872 456 1
8619 2807 1
7935 6361 1
6768 1318 1
9112 3672 1
4064 9323 1
6200 2306 1
7524 5447 1
1408 87...

output:

NO
NO
NO
NO
YES
NO
NO
NO
YES
NO

result:

ok 10 lines

Test #7:

score: 10
Accepted
time: 11ms
memory: 19364kb

input:

10
1000
3607 6465 0
521 2274 0
8200 9210 0
5196 2370 0
7465 4838 0
215 6017 0
4681 5522 0
5239 1520 0
642 6258 0
2045 4894 0
1372 8333 0
7373 8456 0
1520 852 0
3908 2874 0
2158 697 0
9496 1751 0
8931 1124 0
9833 856 0
9247 9274 0
7676 3965 0
7821 2948 0
4822 4070 0
4383 8764 0
3067 3248 0
6505 4906 ...

output:

YES
NO
YES
YES
YES
NO
NO
YES
YES
YES

result:

ok 10 lines

Test #8:

score: 10
Accepted
time: 313ms
memory: 23556kb

input:

10
10000
5011 61 1
655 7926 1
9936 8349 1
6592 9678 1
2392 351 1
8674 8909 1
3479 7449 1
3541 5836 1
5958 4624 1
9755 2747 1
4444 8176 1
2339 8121 1
4868 9472 1
3132 8411 1
7864 2746 1
7800 8634 1
6866 7629 1
8558 5817 1
5004 1223 1
1520 7 1
4244 518 1
2124 7571 1
6876 9547 1
8604 3411 1
6241 8852 1...

output:

YES
YES
YES
YES
NO
YES
NO
NO
NO
NO

result:

ok 10 lines

Test #9:

score: 10
Accepted
time: 347ms
memory: 23552kb

input:

10
10000
2561 174 1
352 195 1
2456 998 1
6403 8398 1
3457 2250 1
603 4352 1
5509 415 1
1230 3575 1
4826 1335 1
1429 4836 1
6290 6211 1
6531 5533 1
3713 1549 1
5809 8575 1
1530 7098 1
4002 8133 1
708 5738 1
5069 4560 1
5740 6281 1
5968 2393 1
2293 9033 1
1164 8924 1
4393 3788 1
1474 6615 1
1773 4275 ...

output:

YES
YES
YES
NO
NO
YES
NO
NO
NO
NO

result:

ok 10 lines

Test #10:

score: 10
Accepted
time: 532ms
memory: 24780kb

input:

10
100000
1 2 1
3 4 1
5 6 0
7 8 0
9 10 1
11 12 0
13 14 0
15 16 0
17 18 0
19 20 0
21 22 1
23 24 1
25 26 1
27 28 1
29 30 1
31 32 1
33 34 1
35 36 0
37 38 1
39 40 0
41 42 1
43 44 0
45 46 0
47 48 1
49 50 0
51 52 0
53 54 1
55 56 0
57 58 0
59 60 1
61 62 1
63 64 0
65 66 1
67 68 0
69 70 1
71 72 0
73 74 1
75 ...

output:

YES
YES
YES
YES
NO
NO
YES
NO
NO
YES

result:

ok 10 lines

Extra Test:

score: 0
Extra Test Passed