QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#527169	#8921. Интерактивные переходы	DaiRuiChen007	100 ✓	45ms	11764kb	C++17	889b	2024-08-22 11:15:49	2024-08-22 11:15:49

Judging History

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

[2024-08-22 11:15:49]
评测

测评结果：100
用时：45ms
内存：11764kb

查看

[2024-08-22 11:15:49]
提交

answer

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
int n,m,a[MAXN],q[MAXN],d[MAXN];
vector <int> G[MAXN];
void solve() {
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i) G[i].clear(),d[i]=0;
	vector <array<int,3>> E(m);
	for(auto&e:E) scanf("%d%d%d",&e[0],&e[1],&e[2]);
	for(int i=1;i<=n;++i) scanf("%d",&a[i]);
	for(auto e:E) {
		int u=e[0],v=e[1];
		if(a[u]^a[v]) {
			if(a[u]^e[2]) swap(u,v);
			G[u].push_back(v),++d[v];
		} else if(a[u]^e[2]) return puts("NO"),void();
	}
	int p=0;
	for(int i=1;i<=n;++i) if(!d[i]) q[++p]=i;
	for(int i=1;i<=p;++i) for(int v:G[q[i]]) if(!--d[v]) q[++p]=v;
	if(p<n) return puts("NO"),void();
	printf("YES\n%d\n",2*n-accumulate(a+1,a+n+1,0));
	for(int i=1;i<=n;++i) {
		printf("%d 1\n",q[i]);
		if(!a[q[i]]) printf("%d 0\n",q[i]);
	}
}
signed main() {
	int T; scanf("%d",&T);
	while(T--) solve();
	return 0;
}

Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 4

Accepted

Test #1:

score: 4

Accepted

time: 0ms

memory: 6208kb

input:

output:

result:

ok ok (230 test cases)

Subtask #2:

score: 10

Accepted

Test #2:

score: 10

Accepted

time: 0ms

memory: 6140kb

input:

output:

result:

ok ok (222 test cases)

Test #3:

score: 10

Accepted

time: 0ms

memory: 5924kb

input:

1
6 7
1 2 1
2 3 0
2 4 1
2 5 1
3 6 1
4 5 0
5 6 0
1 1 0 0 0 1

output:

NO

result:

ok ok (1 test case)

Test #4:

score: 10

Accepted

time: 2ms

memory: 7320kb

input:

250
6 8
1 6 1
3 4 1
2 5 0
2 6 1
5 6 1
3 6 1
4 6 1
4 5 0
0 1 1 1 0 1
6 8
2 4 1
5 6 1
1 3 0
2 5 1
3 5 0
1 5 0
2 3 0
3 4 0
0 1 0 1 1 1
6 8
1 4 0
3 5 0
2 3 1
1 3 0
3 6 0
3 4 1
2 5 1
5 6 0
0 1 0 1 0 0
6 8
2 4 0
1 6 1
1 2 0
3 5 1
4 5 1
1 5 1
2 6 0
2 5 0
0 0 1 1 1 1
6 8
2 3 1
1 3 1
1 4 1
4 6 1
4 5 1
2 5 0
...

output:

result:

ok ok (250 test cases)

Test #5:

score: 10

Accepted

time: 0ms

memory: 6200kb

input:

100
14 0
1 0 0 1 0 1 0 1 0 0 0 1 1 0
14 0
0 0 1 0 0 0 0 0 0 0 0 0 1 0
14 0
0 0 0 0 1 0 0 0 0 1 0 1 1 0
14 0
0 0 1 1 0 0 0 1 0 0 0 0 1 0
14 0
0 1 1 0 1 0 0 0 1 1 1 0 0 0
14 0
0 0 0 0 0 1 1 1 1 1 0 0 0 1
14 0
0 0 0 0 0 0 1 0 0 1 0 1 0 1
14 0
0 1 0 1 1 0 0 1 0 1 0 0 0 1
14 0
0 0 1 0 0 1 0 1 1 1 1 0 1 1...

output:

result:

ok ok (100 test cases)

Subtask #3:

score: 8

Accepted

Test #6:

score: 8

Accepted

time: 23ms

memory: 6892kb

input:

4000
20 25
14 18 1
14 16 1
2 18 1
2 3 1
11 17 1
4 17 1
10 14 1
2 7 1
11 12 1
6 8 1
15 20 1
6 17 1
7 8 1
7 9 1
7 16 1
17 19 1
1 17 1
12 17 1
2 17 1
11 20 1
3 8 1
11 19 1
5 14 1
2 13 1
3 16 1
1 1 0 1 1 1 1 1 0 1 1 0 0 0 1 1 1 1 1 1
20 25
3 15 1
12 17 1
5 12 1
9 14 1
15 17 1
9 10 1
5 14 1
7 20 1
10 18 ...

output:

result:

ok ok (4000 test cases)

Test #7:

score: 8

Accepted

time: 19ms

memory: 7840kb

input:

1
100000 99999
1 87012 1
1 87571 1
2 73382 1
3 3711 1
3 15350 1
3 46773 1
3 56986 1
5 38515 1
5 70500 1
5 85371 1
6 7257 1
6 16656 1
6 47387 1
6 72385 1
6 90108 1
7 14999 1
7 61148 1
7 75467 1
7 87271 1
9 65212 1
9 67960 1
10 7122 1
10 21728 1
11 5206 1
11 24063 1
11 32274 1
12 69255 1
13 48758 1
13...

output:

NO

result:

ok ok (1 test case)

Test #8:

score: 8

Accepted

time: 28ms

memory: 9476kb

input:

1
100000 99999
1 35181 1
2 42232 1
3 13315 1
4 27383 1
4 67403 1
8 16000 1
8 57200 1
8 83634 1
9 38773 1
9 48963 1
9 75230 1
9 90121 1
10 35736 1
11 4072 1
11 13341 1
11 26005 1
12 79774 1
14 7232 1
14 8821 1
14 33012 1
14 41943 1
14 68173 1
14 78849 1
14 91086 1
14 95531 1
15 5822 1
15 49700 1
18 3...

output:

result:

ok ok (1 test case)

Test #9:

score: 8

Accepted

time: 10ms

memory: 7044kb

input:

1
50000 49998
1 11048 1
1 12289 1
2 12244 1
2 31474 1
5 8297 1
5 28740 1
5 42907 1
6 3977 1
7 30422 1
8 24707 1
9 2499 1
9 13069 1
9 25545 1
10 26569 1
10 33390 1
11 1042 1
11 1769 1
12 15195 1
12 26515 1
12 44207 1
13 19568 1
13 21995 1
14 13136 1
15 17511 1
15 20144 1
15 34964 1
15 48216 1
16 1882...

output:

NO

result:

ok ok (1 test case)

Test #10:

score: 8

Accepted

time: 12ms

memory: 7916kb

input:

1
50000 49998
1 33649 1
1 38342 1
2 16465 1
2 45368 1
2 48541 1
3 14297 1
3 14338 1
3 43149 1
5 24062 1
5 40478 1
6 39136 1
7 8171 1
7 47461 1
8 41007 1
9 38951 1
9 47384 1
9 49343 1
10 20889 1
10 33345 1
11 11776 1
11 38722 1
12 44642 1
13 490 1
13 9412 1
13 26137 1
13 32356 1
13 39692 1
14 31978 1...

output:

result:

ok ok (1 test case)

Subtask #4:

score: 6

Accepted

Test #11:

score: 6

Accepted

time: 25ms

memory: 6712kb

input:

10000
10 9
1 2 0
1 3 0
1 4 0
1 5 0
1 6 0
1 7 0
1 8 0
1 9 0
1 10 0
0 0 0 0 0 0 1 1 0 0
10 9
1 2 1
1 3 0
1 4 1
1 5 1
1 6 1
1 7 1
1 8 1
1 9 1
1 10 0
1 1 0 0 1 1 1 0 1 0
10 9
1 2 1
1 3 1
1 4 1
1 5 1
1 6 1
1 7 1
1 8 1
1 9 1
1 10 1
1 0 0 0 1 1 0 0 1 0
10 9
1 2 0
1 3 0
1 4 1
1 5 1
1 6 0
1 7 1
1 8 1
1 9 1
1...

output:

result:

ok ok (10000 test cases)

Test #12:

score: 6

Accepted

time: 25ms

memory: 7208kb

input:

output:

result:

ok ok (100 test cases)

Test #13:

score: 6

Accepted

time: 24ms

memory: 9240kb

input:

1
100000 99999
1 2 1
1 3 1
1 4 1
1 5 1
1 6 1
1 7 1
1 8 1
1 9 1
1 10 1
1 11 1
1 12 1
1 13 0
1 14 0
1 15 0
1 16 0
1 17 0
1 18 1
1 19 1
1 20 1
1 21 0
1 22 0
1 23 1
1 24 1
1 25 0
1 26 0
1 27 1
1 28 0
1 29 0
1 30 0
1 31 1
1 32 0
1 33 0
1 34 0
1 35 0
1 36 1
1 37 1
1 38 1
1 39 0
1 40 1
1 41 0
1 42 1
1 43 0...

output:

result:

ok ok (1 test case)

Subtask #5:

score: 6

Accepted

Test #14:

score: 6

Accepted

time: 38ms

memory: 10696kb

input:

1
100000 199997
1 19238 0
1 42340 0
1 50103 0
1 72140 0
1 94374 0
2 918 1
2 30562 1
2 48451 1
2 53070 1
2 77905 1
3 56418 0
3 61803 0
4 19423 0
4 33995 0
4 64168 0
4 83220 0
4 87239 0
5 24531 1
5 45512 1
6 23321 1
6 34013 1
6 36584 1
6 37278 1
7 16740 1
7 23485 1
7 63378 1
7 71568 1
7 80434 1
7 8103...

output:

result:

ok ok (1 test case)

Test #15:

score: 6

Accepted

time: 38ms

memory: 9608kb

input:

1
100000 199990
1 12954 0
1 34837 0
1 56925 0
2 2727 0
2 23291 0
2 34498 0
2 83496 0
3 18494 0
3 38160 0
3 95686 0
4 4643 0
4 42952 0
4 60758 0
4 74112 0
5 5226 0
5 99964 0
6 25938 0
6 29934 0
6 95643 0
7 12538 0
7 15788 0
7 36142 0
7 83988 0
7 87408 0
8 51940 0
8 89269 0
8 95253 0
9 8664 0
9 46696 ...

output:

result:

ok ok (1 test case)

Test #16:

score: 6

Accepted

time: 34ms

memory: 9880kb

input:

1
100000 199993
1 35659 1
1 40405 1
1 42576 1
1 59472 1
1 93456 1
2 5554 1
2 13807 1
2 16320 1
2 72601 1
2 89825 1
4 39136 1
4 56509 1
4 91423 1
5 8219 1
5 38830 1
5 42490 1
5 85394 1
5 99701 1
6 9204 0
6 25338 0
6 33566 0
6 56606 0
6 63549 0
7 3241 1
7 52579 1
7 75681 1
7 97174 1
8 18865 1
8 30353 ...

output:

result:

ok ok (1 test case)

Test #17:

score: 6

Accepted

time: 37ms

memory: 9772kb

input:

1
50000 199980
1 5699 0
1 7972 0
1 12001 0
1 21408 0
1 22748 0
1 23379 0
1 28184 0
1 34803 0
1 36835 0
1 47782 0
2 4067 1
2 4247 1
2 5958 1
2 10022 1
2 13882 1
2 18781 1
2 22215 1
2 29259 1
2 40478 1
2 47186 1
3 10820 0
3 11187 0
3 13770 0
3 14191 0
3 31138 0
3 32240 0
3 41566 0
3 46910 0
3 46981 0
...

output:

result:

ok ok (1 test case)

Test #18:

score: 6

Accepted

time: 31ms

memory: 9180kb

input:

1
50000 199984
1 25616 0
1 28351 0
1 32669 0
1 39879 0
1 40034 0
1 46455 0
2 3271 0
2 6427 0
2 14884 0
2 16854 0
2 17651 0
2 32673 0
2 41393 0
2 43967 0
2 44086 0
2 44357 0
3 2536 1
3 7684 1
3 12630 1
3 15608 1
3 17831 1
3 18085 1
3 18694 1
3 18753 1
3 26697 1
3 31231 1
3 41382 1
3 41549 1
3 43442 1...

output:

result:

ok ok (1 test case)

Test #19:

score: 6

Accepted

time: 24ms

memory: 9332kb

input:

1
50000 199987
1 7346 1
1 9333 1
1 10752 1
1 22449 1
1 26223 1
1 31067 1
1 36063 1
1 39164 1
2 26857 1
2 27426 1
2 45924 1
2 49776 1
3 3534 1
3 4872 1
3 11112 1
3 18587 1
3 19344 1
3 46857 1
4 5591 1
4 10896 1
4 28314 1
4 32866 1
4 36674 1
4 42045 1
5 2392 1
5 17180 1
5 31349 1
5 34495 1
5 40344 1
5...

output:

result:

ok ok (1 test case)

Test #20:

score: 6

Accepted

time: 27ms

memory: 9104kb

input:

1
100000 199995
1 11260 1
1 36669 1
1 65689 1
2 40027 1
3 11510 1
3 22649 1
3 41557 1
3 55383 1
3 94145 1
4 29777 1
4 34184 1
4 82941 1
4 98660 1
5 70248 1
6 1352 1
6 41406 1
6 50445 1
6 61232 1
6 67229 1
7 24577 1
7 36777 1
7 54446 1
8 5817 1
8 48484 1
9 37743 1
9 41038 1
9 57888 1
9 91818 1
10 708...

output:

result:

ok ok (1 test case)

Test #21:

score: 6

Accepted

time: 40ms

memory: 8956kb

input:

1
100000 199997
1 5769 0
1 6630 0
1 16266 0
1 87415 0
2 23456 0
2 34333 0
2 56018 0
2 58848 0
3 958 0
4 19451 0
4 40396 0
5 23284 0
5 37108 0
6 40220 0
6 53501 0
6 66616 0
6 78456 0
6 98427 0
7 15922 0
7 63343 0
7 73387 0
7 89652 0
8 20051 0
8 39219 0
8 75071 0
9 2884 0
9 53733 0
9 54398 0
9 68547 0...

output:

result:

ok ok (1 test case)

Subtask #6:

score: 8

Accepted

Test #22:

score: 8

Accepted

time: 2ms

memory: 6372kb

input:

output:

NO

result:

ok ok (1 test case)

Test #23:

score: 8

Accepted

time: 2ms

memory: 6792kb

input:

output:

result:

ok ok (1 test case)

Test #24:

score: 8

Accepted

time: 2ms

memory: 6928kb

input:

output:

NO

result:

ok ok (1 test case)

Test #25:

score: 8

Accepted

time: 0ms

memory: 6196kb

input:

output:

result:

ok ok (1 test case)

Test #26:

score: 8

Accepted

time: 1ms

memory: 6144kb

input:

output:

NO

result:

ok ok (1 test case)

Test #27:

score: 8

Accepted

time: 2ms

memory: 6412kb

input:

output:

result:

ok ok (1 test case)

Test #28:

score: 8

Accepted

time: 1ms

memory: 7264kb

input:

output:

YES
8
1 1
1 0
2 1
2 0
3 1
3 0
4 1
4 0
NO
NO
NO
NO
NO
NO
NO
YES
7
2 1
2 0
3 1
3 0
4 1
4 0
1 1
YES
7
1 1
3 1
3 0
4 1
4 0
2 1
2 0
NO
NO
NO
NO
NO
NO
YES
7
1 1
1 0
3 1
3 0
4 1
4 0
2 1
YES
7
3 1
3 0
4 1
4 0
2 1
1 1
1 0
YES
7
1 1
1 0
4 1
4 0
2 1
3 1
3 0
YES
7
2 1
4 1
4 0
1 1
1 0
3 1
3 0
NO
NO
NO
NO
NO
YES
...

result:

ok ok (128 test cases)

Subtask #7:

score: 8

Accepted

Dependency #6:

100%

Accepted

Test #29:

score: 8

Accepted

time: 15ms

memory: 7532kb

input:

1
100000 99999
1 2 0
2 3 0
3 4 0
4 5 1
5 6 1
6 7 0
7 8 0
8 9 1
9 10 0
10 11 1
11 12 1
12 13 0
13 14 0
14 15 1
15 16 1
16 17 1
17 18 0
18 19 1
19 20 0
20 21 0
21 22 1
22 23 0
23 24 1
24 25 1
25 26 1
26 27 1
27 28 0
28 29 0
29 30 1
30 31 0
31 32 0
32 33 0
33 34 1
34 35 1
35 36 1
36 37 0
37 38 1
38 39 ...

output:

NO

result:

ok ok (1 test case)

Test #30:

score: 8

Accepted

time: 30ms

memory: 9084kb

input:

1
100000 99999
1 2 0
2 3 0
3 4 0
4 5 0
5 6 0
6 7 0
7 8 0
8 9 1
9 10 0
10 11 0
11 12 0
12 13 1
13 14 0
14 15 0
15 16 1
16 17 0
17 18 0
18 19 0
19 20 0
20 21 0
21 22 0
22 23 0
23 24 1
24 25 1
25 26 0
26 27 0
27 28 0
28 29 1
29 30 0
30 31 0
31 32 1
32 33 1
33 34 0
34 35 0
35 36 0
36 37 0
37 38 0
38 39 ...

output:

result:

ok ok (1 test case)

Test #31:

score: 8

Accepted

time: 19ms

memory: 7944kb

input:

1
100000 99999
1 2 0
2 3 0
3 4 0
4 5 1
5 6 1
6 7 0
7 8 0
8 9 1
9 10 0
10 11 0
11 12 1
12 13 0
13 14 1
14 15 0
15 16 0
16 17 1
17 18 1
18 19 1
19 20 0
20 21 1
21 22 0
22 23 1
23 24 1
24 25 0
25 26 1
26 27 1
27 28 1
28 29 0
29 30 1
30 31 1
31 32 0
32 33 1
33 34 1
34 35 0
35 36 1
36 37 0
37 38 1
38 39 ...

output:

NO

result:

ok ok (1 test case)

Test #32:

score: 8

Accepted

time: 25ms

memory: 8484kb

input:

1
100000 99999
1 2 0
2 3 0
3 4 0
4 5 0
5 6 0
6 7 0
7 8 0
8 9 0
9 10 0
10 11 0
11 12 0
12 13 1
13 14 1
14 15 0
15 16 0
16 17 0
17 18 0
18 19 0
19 20 0
20 21 0
21 22 0
22 23 0
23 24 0
24 25 0
25 26 0
26 27 0
27 28 1
28 29 1
29 30 0
30 31 0
31 32 0
32 33 0
33 34 0
34 35 0
35 36 0
36 37 0
37 38 0
38 39 ...

output:

result:

ok ok (1 test case)

Test #33:

score: 8

Accepted

time: 14ms

memory: 7480kb

input:

1
100000 99999
1 2 1
2 3 1
3 4 0
4 5 0
5 6 1
6 7 1
7 8 0
8 9 0
9 10 1
10 11 0
11 12 0
12 13 1
13 14 0
14 15 1
15 16 1
16 17 1
17 18 1
18 19 0
19 20 1
20 21 0
21 22 1
22 23 0
23 24 1
24 25 0
25 26 1
26 27 0
27 28 1
28 29 1
29 30 1
30 31 0
31 32 1
32 33 1
33 34 0
34 35 1
35 36 1
36 37 1
37 38 1
38 39 ...

output:

NO

result:

ok ok (1 test case)

Test #34:

score: 8

Accepted

time: 25ms

memory: 8352kb

input:

1
100000 99999
1 2 0
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1
7 8 1
8 9 1
9 10 1
10 11 1
11 12 1
12 13 1
13 14 1
14 15 1
15 16 1
16 17 1
17 18 1
18 19 1
19 20 1
20 21 1
21 22 0
22 23 0
23 24 0
24 25 1
25 26 1
26 27 1
27 28 0
28 29 1
29 30 1
30 31 1
31 32 1
32 33 1
33 34 1
34 35 1
35 36 1
36 37 1
37 38 1
38 39 ...

output:

result:

ok ok (1 test case)

Test #35:

score: 8

Accepted

time: 2ms

memory: 6648kb

input:

output:

YES
10
1 1
1 0
2 1
2 0
3 1
3 0
4 1
4 0
5 1
5 0
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
9
2 1
2 0
3 1
3 0
4 1
4 0
5 1
5 0
1 1
YES
9
1 1
3 1
3 0
4 1
4 0
5 1
5 0
2 1
2 0
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
9
1 1
1 0
3 1
3 0
4 1
4 0
5 1
5 0
2 1
YES
9
3 1
3 0
4 1
4 0
5 1
5 0
2 1
1 1
1 ...

result:

ok ok (512 test cases)

Test #36:

score: 8

Accepted

time: 3ms

memory: 6020kb

input:

2048
6 5
1 2 0
2 3 0
3 4 0
4 5 0
5 6 0
0 0 0 0 0 0
6 5
1 2 1
2 3 0
3 4 0
4 5 0
5 6 0
0 0 0 0 0 0
6 5
1 2 0
2 3 1
3 4 0
4 5 0
5 6 0
0 0 0 0 0 0
6 5
1 2 1
2 3 1
3 4 0
4 5 0
5 6 0
0 0 0 0 0 0
6 5
1 2 0
2 3 0
3 4 1
4 5 0
5 6 0
0 0 0 0 0 0
6 5
1 2 1
2 3 0
3 4 1
4 5 0
5 6 0
0 0 0 0 0 0
6 5
1 2 0
2 3 1
3 4...

output:

YES
12
1 1
1 0
2 1
2 0
3 1
3 0
4 1
4 0
5 1
5 0
6 1
6 0
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
11
2 1
2 0
3 1
3 0
4 1
4 0
5 1
5 0
6 1
6 0
1 1
YES
11
1 1
3 1
3 0
4 1
4 0
5 1
5 0
6 1
6 0
2 1
2 0
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO...

result:

ok ok (2048 test cases)

Test #37:

score: 8

Accepted

time: 11ms

memory: 6076kb

input:

8192
7 6
1 2 0
2 3 0
3 4 0
4 5 0
5 6 0
6 7 0
0 0 0 0 0 0 0
7 6
1 2 1
2 3 0
3 4 0
4 5 0
5 6 0
6 7 0
0 0 0 0 0 0 0
7 6
1 2 0
2 3 1
3 4 0
4 5 0
5 6 0
6 7 0
0 0 0 0 0 0 0
7 6
1 2 1
2 3 1
3 4 0
4 5 0
5 6 0
6 7 0
0 0 0 0 0 0 0
7 6
1 2 0
2 3 0
3 4 1
4 5 0
5 6 0
6 7 0
0 0 0 0 0 0 0
7 6
1 2 1
2 3 0
3 4 1
4 5...

output:

YES
14
1 1
1 0
2 1
2 0
3 1
3 0
4 1
4 0
5 1
5 0
6 1
6 0
7 1
7 0
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
13
2 1
2 0
3 1
3 0
4 1
4 0
5 1
5 0
6 1
6 0
7...

result:

ok ok (8192 test cases)

Subtask #8:

score: 10

Accepted

Dependency #6:

100%

Accepted

Test #38:

score: 10

Accepted

time: 2ms

memory: 6044kb

input:

output:

NO

result:

ok ok (1 test case)

Test #39:

score: 10

Accepted

time: 2ms

memory: 5980kb

input:

output:

NO

result:

ok ok (1 test case)

Test #40:

score: 10

Accepted

time: 0ms

memory: 6500kb

input:

output:

NO

result:

ok ok (1 test case)

Test #41:

score: 10

Accepted

time: 2ms

memory: 7548kb

input:

output:

result:

ok ok (1 test case)

Test #42:

score: 10

Accepted

time: 0ms

memory: 6192kb

input:

output:

result:

ok ok (1 test case)

Test #43:

score: 10

Accepted

time: 2ms

memory: 6484kb

input:

output:

result:

ok ok (1 test case)

Subtask #9:

score: 6

Accepted

Dependency #4:

100%

Accepted

Dependency #6:

100%

Accepted

Dependency #7:

100%

Accepted

Dependency #8:

100%

Accepted

Test #44:

score: 6

Accepted

time: 19ms

memory: 7836kb

input:

1
100000 99999
1 2 1
1 3 1
3 4 0
2 5 1
2 6 1
2 7 0
5 8 0
8 9 0
6 10 0
5 11 0
2 12 0
8 13 0
13 14 1
3 15 1
2 16 0
8 17 0
3 18 1
18 19 0
10 20 0
17 21 0
8 22 0
11 23 1
9 24 1
10 25 1
11 26 1
25 27 0
7 28 1
3 29 1
8 30 1
17 31 0
29 32 1
28 33 1
10 34 1
13 35 0
9 36 0
15 37 0
14 38 1
31 39 1
30 40 1
40 ...

output:

NO

result:

ok ok (1 test case)

Test #45:

score: 6

Accepted

time: 15ms

memory: 7372kb

input:

1
100000 99999
1 2 0
1 3 0
2 4 0
4 5 1
2 6 0
4 7 0
6 8 1
5 9 1
3 10 0
3 11 0
11 12 1
5 13 1
2 14 1
5 15 1
1 16 1
16 17 1
2 18 1
5 19 0
1 20 1
18 21 1
3 22 0
6 23 0
4 24 0
11 25 1
19 26 1
23 27 1
16 28 0
4 29 1
12 30 0
16 31 1
7 32 1
18 33 1
10 34 1
16 35 1
5 36 1
1 37 1
32 38 0
20 39 0
21 40 1
14 41...

output:

NO

result:

ok ok (1 test case)

Test #46:

score: 6

Accepted

time: 12ms

memory: 7364kb

input:

1
100000 99999
1 2 0
1 3 0
2 4 1
3 5 1
5 6 0
1 7 1
6 8 0
2 9 0
4 10 1
2 11 0
5 12 1
1 13 1
10 14 1
5 15 1
13 16 0
13 17 1
16 18 1
18 19 0
1 20 1
14 21 1
2 22 0
5 23 1
22 24 0
11 25 0
9 26 0
17 27 1
19 28 0
26 29 1
11 30 0
20 31 1
20 32 1
6 33 1
21 34 1
32 35 0
35 36 1
9 37 0
37 38 1
34 39 1
3 40 1
1...

output:

NO

result:

ok ok (1 test case)

Test #47:

score: 6

Accepted

time: 24ms

memory: 9248kb

input:

1
100000 99999
1 2 0
2 3 0
2 4 0
3 5 0
4 6 0
4 7 0
3 8 0
4 9 1
7 10 1
2 11 0
3 12 0
7 13 0
13 14 0
9 15 1
14 16 1
3 17 0
5 18 0
15 19 1
15 20 1
8 21 1
11 22 1
16 23 0
5 24 1
6 25 0
15 26 1
7 27 0
26 28 0
24 29 1
21 30 1
20 31 1
10 32 1
12 33 1
23 34 1
12 35 1
11 36 0
6 37 0
29 38 0
6 39 0
9 40 0
33 ...

output:

result:

ok ok (1 test case)

Test #48:

score: 6

Accepted

time: 31ms

memory: 9032kb

input:

1
100000 99999
1 2 1
2 3 1
3 4 1
4 5 0
3 6 1
4 7 0
5 8 1
1 9 0
3 10 1
8 11 0
1 12 0
3 13 1
2 14 1
11 15 0
14 16 0
11 17 0
13 18 0
4 19 1
6 20 0
17 21 0
3 22 1
9 23 1
23 24 1
7 25 1
25 26 1
2 27 1
8 28 0
26 29 1
25 30 0
19 31 1
17 32 1
2 33 1
23 34 1
16 35 0
29 36 1
28 37 0
25 38 1
11 39 0
38 40 0
7 ...

output:

result:

ok ok (1 test case)

Test #49:

score: 6

Accepted

time: 27ms

memory: 9112kb

input:

1
100000 99999
1 2 1
1 3 1
2 4 1
4 5 0
5 6 1
1 7 1
4 8 0
3 9 0
7 10 1
3 11 0
10 12 0
1 13 1
7 14 1
9 15 0
10 16 0
15 17 1
12 18 0
11 19 1
18 20 1
1 21 0
20 22 1
19 23 1
20 24 1
1 25 1
20 26 1
8 27 0
27 28 0
9 29 0
16 30 1
4 31 1
9 32 0
19 33 1
27 34 0
15 35 1
24 36 1
30 37 1
24 38 1
32 39 1
8 40 0
4...

output:

result:

ok ok (1 test case)

Subtask #10:

score: 6

Accepted

Test #50:

score: 6

Accepted

time: 21ms

memory: 10732kb

input:

1
100000 100000
1 2 0
2 3 1
3 4 0
4 5 1
5 6 0
6 7 1
7 8 0
8 9 1
9 10 0
10 11 1
11 12 0
12 13 1
13 14 0
14 15 1
15 16 0
16 17 1
17 18 0
18 19 1
19 20 0
20 21 1
21 22 0
22 23 1
23 24 0
24 25 1
25 26 0
26 27 1
27 28 0
28 29 1
29 30 0
30 31 1
31 32 0
32 33 1
33 34 0
34 35 1
35 36 0
36 37 1
37 38 0
38 39...

output:

NO

result:

ok ok (1 test case)

Test #51:

score: 6

Accepted

time: 21ms

memory: 11128kb

input:

1
100000 100000
1 2 0
2 3 1
3 4 0
4 5 1
5 6 0
6 7 1
7 8 0
8 9 1
9 10 0
10 11 1
11 12 0
12 13 1
13 14 0
14 15 1
15 16 0
16 17 1
17 18 0
18 19 1
19 20 0
20 21 1
21 22 0
22 23 1
23 24 0
24 25 1
25 26 0
26 27 1
27 28 0
28 29 1
29 30 0
30 31 1
31 32 0
32 33 1
33 34 0
34 35 1
35 36 0
36 37 1
37 38 0
38 39...

output:

NO

result:

ok ok (1 test case)

Test #52:

score: 6

Accepted

time: 17ms

memory: 10740kb

input:

1
100000 100000
1 2 1
2 3 0
3 4 1
4 5 0
5 6 1
6 7 0
7 8 1
8 9 0
9 10 1
10 11 0
11 12 1
12 13 0
13 14 1
14 15 0
15 16 1
16 17 0
17 18 1
18 19 0
19 20 1
20 21 0
21 22 1
22 23 0
23 24 1
24 25 0
25 26 1
26 27 0
27 28 1
28 29 0
29 30 1
30 31 0
31 32 1
32 33 0
33 34 1
34 35 0
35 36 1
36 37 0
37 38 1
38 39...

output:

NO

result:

ok ok (1 test case)

Test #53:

score: 6

Accepted

time: 22ms

memory: 10736kb

input:

1
100000 100000
1 2 1
2 3 0
3 4 1
4 5 0
5 6 1
6 7 0
7 8 1
8 9 0
9 10 1
10 11 0
11 12 1
12 13 0
13 14 1
14 15 0
15 16 1
16 17 0
17 18 1
18 19 0
19 20 1
20 21 0
21 22 1
22 23 0
23 24 1
24 25 0
25 26 1
26 27 0
27 28 1
28 29 0
29 30 1
30 31 0
31 32 1
32 33 0
33 34 1
34 35 0
35 36 1
36 37 0
37 38 1
38 39...

output:

NO

result:

ok ok (1 test case)

Test #54:

score: 6

Accepted

time: 15ms

memory: 7568kb

input:

1
100000 100000
1 2 1
2 3 0
3 4 0
4 5 0
5 6 1
6 7 1
7 8 0
8 9 1
9 10 1
10 11 0
11 12 1
12 13 0
13 14 0
14 15 0
15 16 1
16 17 1
17 18 0
18 19 1
19 20 1
20 21 0
21 22 1
22 23 0
23 24 1
24 25 1
25 26 1
26 27 0
27 28 0
28 29 1
29 30 1
30 31 0
31 32 1
32 33 1
33 34 1
34 35 0
35 36 1
36 37 1
37 38 0
38 39...

output:

NO

result:

ok ok (1 test case)

Test #55:

score: 6

Accepted

time: 14ms

memory: 7444kb

input:

1
95000 95000
1 2 1
2 3 1
3 4 0
4 5 1
5 6 1
6 7 0
7 8 0
8 9 0
9 10 0
10 11 1
11 12 0
12 13 0
13 14 1
14 15 1
15 16 0
16 17 0
17 18 1
18 19 0
19 20 0
20 21 1
21 22 0
22 23 1
23 24 1
24 25 0
25 26 1
26 27 0
27 28 0
28 29 0
29 30 1
30 31 1
31 32 0
32 33 0
33 34 1
34 35 0
35 36 1
36 37 0
37 38 0
38 39 0...

output:

NO

result:

ok ok (1 test case)

Test #56:

score: 6

Accepted

time: 26ms

memory: 9080kb

input:

1
100000 100000
1 2 1
2 3 1
3 4 1
4 5 0
5 6 0
6 7 0
7 8 0
8 9 0
9 10 0
10 11 1
11 12 1
12 13 1
13 14 1
14 15 1
15 16 0
16 17 0
17 18 1
18 19 1
19 20 1
20 21 1
21 22 1
22 23 0
23 24 0
24 25 0
25 26 0
26 27 1
27 28 1
28 29 0
29 30 0
30 31 1
31 32 0
32 33 0
33 34 0
34 35 1
35 36 1
36 37 1
37 38 1
38 39...

output:

result:

ok ok (1 test case)

Test #57:

score: 6

Accepted

time: 25ms

memory: 9096kb

input:

1
95000 95000
1 2 0
2 3 0
3 4 0
4 5 0
5 6 0
6 7 0
7 8 0
8 9 0
9 10 1
10 11 1
11 12 0
12 13 0
13 14 0
14 15 0
15 16 0
16 17 0
17 18 1
18 19 1
19 20 1
20 21 0
21 22 0
22 23 0
23 24 0
24 25 1
25 26 1
26 27 0
27 28 0
28 29 1
29 30 1
30 31 0
31 32 0
32 33 0
33 34 0
34 35 1
35 36 1
36 37 1
37 38 1
38 39 1...

output:

result:

ok ok (1 test case)

Subtask #11:

score: 10

Accepted

Dependency #2:

100%

Accepted

Dependency #6:

100%

Accepted

Dependency #8:

100%

Accepted

Test #58:

score: 10

Accepted

time: 2ms

memory: 6100kb

input:

output:

NO

result:

ok ok (1 test case)

Test #59:

score: 10

Accepted

time: 1ms

memory: 6736kb

input:

output:

NO

result:

ok ok (1 test case)

Test #60:

score: 10

Accepted

time: 1ms

memory: 6624kb

input:

output:

NO

result:

ok ok (1 test case)

Test #61:

score: 10

Accepted

time: 1ms

memory: 6756kb

input:

output:

result:

ok ok (1 test case)

Test #62:

score: 10

Accepted

time: 1ms

memory: 6668kb

input:

1
1000 1992
1 341 0
1 591 0
1 754 0
1 788 0
2 368 0
4 138 0
4 252 0
4 784 0
5 480 0
7 225 0
7 296 0
7 456 0
7 532 0
7 616 0
8 369 0
8 960 0
10 150 0
10 288 0
10 487 0
10 553 0
10 775 0
11 136 0
11 153 0
11 162 0
11 552 0
11 685 0
11 999 0
12 904 0
13 32 0
13 761 0
14 232 0
14 548 0
14 610 0
15 122 0...

output:

result:

ok ok (1 test case)

Test #63:

score: 10

Accepted

time: 0ms

memory: 6916kb

input:

output:

result:

ok ok (1 test case)

Test #64:

score: 10

Accepted

time: 2ms

memory: 6152kb

input:

1
1000 1999
1 705 0
2 741 0
3 259 0
3 442 0
3 479 0
3 612 0
4 97 0
4 514 0
4 829 0
4 941 0
7 307 0
7 617 0
7 823 0
8 671 0
9 709 0
9 923 0
11 271 0
11 788 0
11 906 0
12 295 0
15 847 0
18 160 0
18 411 0
18 449 0
18 459 0
21 285 0
21 382 0
21 416 0
21 764 0
22 419 0
24 650 0
24 777 0
24 795 0
24 885 0...

output:

result:

ok ok (1 test case)

Test #65:

score: 10

Accepted

time: 2ms

memory: 6160kb

input:

output:

result:

ok ok (1 test case)

Test #66:

score: 10

Accepted

time: 0ms

memory: 6480kb

input:

output:

result:

ok ok (1 test case)

Test #67:

score: 10

Accepted

time: 2ms

memory: 6508kb

input:

output:

result:

ok ok (1 test case)

Test #68:

score: 10

Accepted

time: 2ms

memory: 6176kb

input:

output:

result:

ok ok (1 test case)

Test #69:

score: 10

Accepted

time: 2ms

memory: 6448kb

input:

output:

result:

ok ok (1 test case)

Test #70:

score: 10

Accepted

time: 2ms

memory: 6440kb

input:

output:

result:

ok ok (1 test case)

Test #71:

score: 10

Accepted

time: 2ms

memory: 6184kb

input:

output:

result:

ok ok (1 test case)

Subtask #12:

score: 18

Accepted

Dependency #1:

100%

Accepted

Dependency #2:

100%

Accepted

Dependency #3:

100%

Accepted

Dependency #4:

100%

Accepted

Dependency #5:

100%

Accepted

Dependency #6:

100%

Accepted

Dependency #7:

100%

Accepted

Dependency #8:

100%

Accepted

Dependency #9:

100%

Accepted

Dependency #10:

100%

Accepted

Dependency #11:

100%

Accepted

Test #72:

score: 18

Accepted

time: 40ms

memory: 11764kb

input:

1
100000 200000
7400 64761 0
64761 60287 1
60287 7113 0
7113 55727 1
55727 20838 0
20838 17799 1
17799 99870 0
99870 87603 1
87603 9059 0
9059 96506 1
96506 82355 0
82355 61387 1
61387 84097 0
84097 35019 1
35019 43828 0
43828 47890 1
47890 28453 0
28453 23828 1
23828 4756 0
4756 77657 1
77657 29379...

output:

NO

result:

ok ok (1 test case)

Test #73:

score: 18

Accepted

time: 7ms

memory: 8884kb

input:

1
50000 50000
1 2 0
2 3 1
3 4 0
4 5 1
5 6 0
6 7 1
7 8 0
8 9 1
9 10 0
10 11 1
11 12 0
12 13 1
13 14 0
14 15 1
15 16 0
16 17 1
17 18 0
18 19 1
19 20 0
20 21 1
21 22 0
22 23 1
23 24 0
24 25 1
25 26 0
26 27 1
27 28 0
28 29 1
29 30 0
30 31 1
31 32 0
32 33 1
33 34 0
34 35 1
35 36 0
36 37 1
37 38 0
38 39 1...

output:

NO

result:

ok ok (1 test case)

Test #74:

score: 18

Accepted

time: 38ms

memory: 10192kb

input:

1
50000 199968
2 19369 1
2 21364 1
2 25155 1
2 27339 1
2 27511 1
2 44556 1
2 45351 1
3 44569 0
3 45843 0
3 49912 0
4 9491 0
5 49735 1
6 16383 1
6 28552 1
7 30996 1
8 7229 1
8 10756 1
8 12621 1
8 19752 1
8 44330 1
9 26023 1
9 35659 1
10 7610 1
10 16819 1
10 22540 1
10 27829 1
10 32872 1
10 35055 1
10...

output:

result:

ok ok (1 test case)

Test #75:

score: 18

Accepted

time: 38ms

memory: 10640kb

input:

1
50000 199913
1 17199 0
1 34976 0
1 40637 0
2 19412 0
3 2252 1
3 2925 1
3 3029 1
3 6295 1
3 7328 1
3 10938 1
3 12057 1
3 17265 1
3 17912 1
3 18223 1
3 19003 1
3 21266 1
3 22296 1
3 22320 1
3 22663 1
3 24507 1
3 26280 1
3 26734 1
3 27637 1
3 28019 1
3 29941 1
3 31611 1
3 31704 1
3 31802 1
3 32467 1
...

output:

result:

ok ok (1 test case)

Test #76:

score: 18

Accepted

time: 36ms

memory: 10208kb

input:

1
50000 199911
1 8404 1
1 17242 1
1 24057 1
1 31078 1
1 32448 1
1 33608 1
2 27010 1
2 47233 1
3 5128 1
3 6418 1
3 24676 1
3 48487 1
5 1034 1
5 10374 1
5 23871 1
5 31896 1
5 44262 1
6 22036 1
6 41207 1
7 2667 1
7 7316 1
7 30778 1
7 35899 1
7 47038 1
8 7828 1
9 9734 1
9 35195 1
9 49220 1
10 6037 1
11 ...

output:

result:

ok ok (1 test case)

Test #77:

score: 18

Accepted

time: 45ms

memory: 11500kb

input:

1
100000 199993
2 5800 1
2 38429 1
2 87603 1
2 97076 1
3 17781 0
3 27608 0
3 57980 0
3 60559 0
3 88247 0
4 14335 0
5 63749 1
7 25192 1
7 60951 1
7 63367 1
9 62836 1
10 21312 1
10 22145 1
10 78654 1
11 21555 1
11 84212 1
11 86088 1
11 99696 1
12 37520 1
13 15200 1
13 18408 1
14 89343 0
15 1999 1
15 1...

output:

result:

ok ok (1 test case)

Test #78:

score: 18

Accepted

time: 44ms

memory: 11600kb

input:

1
100000 199989
1 76702 0
2 12252 0
3 30590 0
3 95162 0
5 79468 0
7 51874 0
9 506 0
9 11079 0
9 52889 0
9 80135 0
11 9629 0
11 49499 0
11 55682 0
11 66404 0
12 27992 0
12 42958 0
12 48475 0
12 69809 0
15 13998 0
15 29664 0
17 14463 0
17 28903 0
17 48901 0
17 82954 0
17 92913 0
20 14614 1
20 20196 1
...

output:

result:

ok ok (1 test case)

Test #79:

score: 18

Accepted

time: 45ms

memory: 11672kb

input:

1
100000 199973
1 26091 1
3 4696 0
3 12011 0
3 14048 0
3 23953 0
3 48581 0
3 55894 0
3 58903 0
3 58965 0
3 64006 0
3 65907 0
3 81900 0
4 76090 1
5 44397 1
6 23916 0
6 24472 0
6 29712 0
6 29819 0
6 30269 0
6 34134 0
6 34773 0
6 37470 0
6 41593 0
6 43439 0
6 48579 0
6 52101 0
6 53803 0
6 60060 0
6 618...

output:

result:

ok ok (1 test case)

Test #80:

score: 18

Accepted

time: 38ms

memory: 9788kb

input:

1
50000 199981
1 9617 0
1 13254 0
2 16509 1
2 27339 1
2 34328 1
2 38684 1
2 45351 1
3 1936 0
3 12116 0
3 21212 0
3 33378 0
3 41153 0
3 44569 0
3 49912 0
4 6411 0
4 17523 0
5 15195 1
5 19694 1
8 1301 1
8 12142 1
8 21098 1
8 29237 1
8 32347 1
8 36774 1
9 9064 1
9 26023 1
9 40620 1
10 4361 1
10 9251 1
...

output:

result:

ok ok (1 test case)

Test #81:

score: 18

Accepted

time: 31ms

memory: 8888kb

input:

1
50000 199990
1 779 0
1 1093 0
1 3698 0
1 8592 0
1 11226 0
1 21318 0
1 24643 0
1 29562 0
1 45487 0
2 6651 0
2 9349 0
2 19670 0
2 19954 0
2 27340 0
2 28329 0
2 39707 0
2 46852 0
2 47818 0
3 2296 1
3 3615 1
3 8279 1
3 9627 1
3 11443 1
3 17694 1
3 23201 1
3 29842 1
3 32123 1
3 34302 1
3 43999 1
4 1155...

output:

result:

ok ok (1 test case)

Test #82:

score: 18

Accepted

time: 30ms

memory: 9344kb

input:

1
50000 199983
1 11037 1
1 20705 1
1 22722 1
1 25398 1
1 32222 1
1 38283 1
1 43464 1
2 12626 1
2 25300 1
2 35398 1
2 40490 1
2 42361 1
2 42627 1
2 45506 1
3 9960 1
4 20466 1
4 34415 1
5 3631 1
5 7021 1
5 24632 1
5 30188 1
5 30666 1
5 32331 1
5 39201 1
5 45553 1
5 49795 1
6 5802 1
6 18080 1
6 20702 1...

output:

result:

ok ok (1 test case)

Test #83:

score: 18

Accepted

time: 39ms

memory: 10740kb

input:

1
100000 199995
2 5800 1
2 38429 1
2 48015 1
3 12089 0
3 27718 0
3 49401 0
3 84851 0
4 7198 0
4 55509 0
4 86361 0
7 25192 1
7 74682 1
8 97749 1
9 2068 1
10 69054 1
10 78654 1
10 81225 1
11 44076 1
11 50618 1
12 37520 1
12 79722 1
13 62651 1
14 68509 0
14 68889 0
15 9694 1
15 17146 1
15 33158 1
15 74...

output:

result:

ok ok (1 test case)

Test #84:

score: 18

Accepted

time: 34ms

memory: 9684kb

input:

1
100000 199996
1 40390 0
1 49542 0
2 3647 0
2 40814 0
2 84407 0
2 87973 0
4 41330 0
4 45152 0
5 49392 0
7 376 0
7 51974 0
7 62702 0
9 13433 0
9 19038 0
9 28940 0
9 31353 0
9 78327 0
9 88453 0
10 80144 0
11 22291 0
11 55175 0
12 68366 0
12 77297 0
14 25334 0
14 92999 0
15 50979 0
15 56214 0
16 14896...

output:

result:

ok ok (1 test case)

Test #85:

score: 18

Accepted

time: 35ms

memory: 9664kb

input:

1
100000 199993
2 36343 1
5 7051 1
5 19899 1
5 56841 1
5 78043 1
6 16961 0
6 82832 0
7 26247 1
7 39033 1
7 71905 1
7 73979 1
8 62552 1
8 92154 1
9 17984 1
9 26928 1
9 37416 1
9 83877 1
10 3821 1
10 10441 1
10 65072 1
10 77832 1
10 85366 1
12 35357 1
12 46221 1
12 72660 1
12 93814 1
12 96138 1
13 158...

output:

result:

ok ok (1 test case)

Test #86:

score: 18

Accepted

time: 40ms

memory: 9280kb

input:

1
100000 199995
2 4156 0
2 87333 0
2 90158 0
3 13118 0
3 15228 0
3 17999 0
4 2186 0
4 29195 0
4 47410 0
4 69083 0
4 78449 0
4 84967 0
6 28610 0
6 85599 0
7 17954 0
9 11209 0
11 35587 0
12 10861 0
12 78758 0
13 31375 0
13 89470 0
15 17362 0
15 25825 0
16 1142 0
16 2706 0
16 84404 0
18 5533 0
18 21178...

output:

result:

ok ok (1 test case)

Test #87:

score: 18

Accepted

time: 35ms

memory: 9148kb

input:

1
100000 199994
1 1585 1
1 73911 1
2 46807 1
3 939 1
4 18082 1
4 46856 1
7 10606 1
7 36179 1
7 53263 1
7 96897 1
10 50674 1
12 23467 1
14 3689 1
16 10071 1
16 63913 1
17 16662 1
17 23189 1
17 91225 1
17 95816 1
19 21529 1
20 47967 1
21 62050 1
22 21083 1
22 21376 1
22 84238 1
24 9167 1
24 49250 1
24...

output:

result:

ok ok (1 test case)

Extra Test:

score: 0

Extra Test Passed