QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#290658	#5493. 程序自动分析	MoRanSky	100 ✓	365ms	14808kb	C++23	1.1kb	2023-12-25 06:19:20	2023-12-25 06:19:20

Judging History

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

[2023-12-25 06:19:20]
评测

测评结果：100
用时：365ms
内存：14808kb

查看

[2023-12-25 06:19:20]
提交

answer

#include <cstdio>
#include <iostream>
#include <algorithm>
#define get(x) lower_bound(d + 1, d + 1 + m, x) - d
using namespace std;
const int N = 1000005;
int n, m, a[N], b[N], c[N], d[N << 1], f[N << 1];
int find(int x) {
    return x == f[x] ? x : f[x] = find(f[x]);
}
int main() {
    int T; scanf("%d", &T);
    while(T--) {
        scanf("%d", &n); m = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%d%d%d", a + i, b + i, c + i);
            d[++m] = a[i], d[++m] = b[i];
        }
        sort(d + 1, d + 1 + m);
        m = unique(d + 1, d + 1 + m) - d - 1;
        for (int i = 1; i <= m; i++) f[i] = i;
        for (int i = 1; i <= n; i++) {
            int x = get(a[i]), y = get(b[i]), z = c[i];
            if(z) f[find(x)] = find(y);
        }
        bool ok = true;
        for (int i = 1; i <= n; i++) {
            int x = get(a[i]), y = get(b[i]), z = c[i];
            if(!z) {  
                x = find(x), y = find(y);
                if(x == y) { ok = false; break; }
            }
        }
        puts(ok ? "YES" : "NO");
    }
    return 0;
}

Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 10

Accepted

time: 2ms

memory: 11828kb

input:

output:

NO
YES
NO
YES
YES

result:

ok 5 lines

Test #2:

score: 10

Accepted

time: 0ms

memory: 11752kb

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: 2ms

memory: 11924kb

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: 0ms

memory: 11844kb

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: 5ms

memory: 11864kb

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: 42ms

memory: 14052kb

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: 3ms

memory: 11928kb

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: 225ms

memory: 14072kb

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: 277ms

memory: 12068kb

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: 365ms

memory: 14808kb

input:

output:

YES
YES
YES
YES
NO
NO
YES
NO
NO
YES

result:

ok 10 lines

Extra Test:

score: 0

Extra Test Passed