QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#291245#2426. The Xana coupMysterious_Cat100 ✓29ms18824kbC++141.1kb2023-12-26 08:36:242023-12-26 08:36:25

Judging History

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

  • [2023-12-26 08:36:25]
  • 评测
  • 测评结果:100
  • 用时:29ms
  • 内存:18824kb
  • [2023-12-26 08:36:24]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
const int inf = 0x3f3f3f3f;

int n;
int a[N], dp[N][2][2], f[2][2];
vector<int> e[N];

void dfs(int u, int fa) {
	dp[u][a[u]][0] = 0;
	dp[u][a[u] ^ 1][1] = 1;
	for(int v : e[u]) {
		if(v == fa) {
			continue;
		}
		dfs(v, u);
		f[0][0] = min(dp[u][0][0] + dp[v][0][0], dp[u][1][0] + dp[v][0][1]);
		f[0][1] = min(dp[u][0][1] + dp[v][1][0], dp[u][1][1] + dp[v][1][1]);
		f[1][0] = min(dp[u][0][0] + dp[v][0][1], dp[u][1][0] + dp[v][0][0]);
		f[1][1] = min(dp[u][0][1] + dp[v][1][1], dp[u][1][1] + dp[v][1][0]);
		for(int i = 0; i < 2; i++) {
		    for(int j = 0; j < 2; j++) {
		        dp[u][i][j] = min(f[i][j], 0x3f3f3f3f);
		    }
		}
	}
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for (int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		e[u].emplace_back(v);
		e[v].emplace_back(u);
	}
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	memset(dp, 0x3f, sizeof(dp));
	dfs(1, 0);
	int ans = min(dp[1][0][0], dp[1][0][1]);
	if(ans == inf) {
	    cout << "impossible\n";
	}
	else {
	    cout << ans << '\n';
	}
	
	return 0;
}

详细

Subtask #1:

score: 0
Accepted

Test #1:

score: 0
Accepted
time: 2ms
memory: 7520kb

input:

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

output:

4

result:

ok single line: '4'

Test #2:

score: 0
Accepted
time: 0ms
memory: 7480kb

input:

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

output:

impossible

result:

ok single line: 'impossible'

Subtask #2:

score: 5
Accepted

Dependency #1:

100%
Accepted

Test #3:

score: 5
Accepted
time: 1ms
memory: 7620kb

input:

17
2 7
3 17
9 16
15 8
6 13
7 10
12 17
12 4
1 11
7 15
3 14
11 17
8 17
1 5
13 7
8 16
0 1 1 0 1 0 0 0 1 0 0 0 0 1 1 0 1

output:

8

result:

ok single line: '8'

Test #4:

score: 0
Accepted
time: 1ms
memory: 7588kb

input:

14
5 13
4 1
2 1
7 2
6 14
10 14
12 3
2 6
5 11
12 2
6 8
10 11
12 9
1 1 1 0 1 1 0 1 0 1 0 1 0 1

output:

10

result:

ok single line: '10'

Test #5:

score: 0
Accepted
time: 1ms
memory: 7536kb

input:

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

output:

6

result:

ok single line: '6'

Test #6:

score: 0
Accepted
time: 1ms
memory: 7536kb

input:

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

output:

11

result:

ok single line: '11'

Test #7:

score: 0
Accepted
time: 1ms
memory: 7476kb

input:

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

output:

impossible

result:

ok single line: 'impossible'

Subtask #3:

score: 15
Accepted

Test #8:

score: 15
Accepted
time: 0ms
memory: 7472kb

input:

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

output:

13

result:

ok single line: '13'

Test #9:

score: 0
Accepted
time: 1ms
memory: 7536kb

input:

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

output:

19

result:

ok single line: '19'

Test #10:

score: 0
Accepted
time: 1ms
memory: 7484kb

input:

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

output:

21

result:

ok single line: '21'

Test #11:

score: 0
Accepted
time: 1ms
memory: 7524kb

input:

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

output:

impossible

result:

ok single line: 'impossible'

Test #12:

score: 0
Accepted
time: 0ms
memory: 7536kb

input:

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

output:

14

result:

ok single line: '14'

Test #13:

score: 0
Accepted
time: 1ms
memory: 7520kb

input:

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

output:

13

result:

ok single line: '13'

Subtask #4:

score: 10
Accepted

Test #14:

score: 10
Accepted
time: 24ms
memory: 18824kb

input:

99481
19117 19116
39650 39651
69914 69913
6831 6830
32628 32629
47585 47586
9962 9963
43561 43562
65038 65037
89192 89191
55315 55314
67819 67820
62853 62852
37838 37839
13481 13482
79553 79552
13649 13648
42022 42023
40952 40953
53979 53980
31280 31281
52472 52473
4690 4691
659 660
34413 34412
6409...

output:

49772

result:

ok single line: '49772'

Test #15:

score: 0
Accepted
time: 26ms
memory: 18736kb

input:

98273
46112 46113
46912 46913
74330 74329
44926 44925
45873 45874
67146 67145
5397 5396
2561 2560
82735 82736
94041 94040
26762 26761
24535 24534
29483 29482
36116 36115
6390 6391
84795 84796
21112 21113
78994 78993
48299 48298
174 173
15717 15716
93544 93545
32500 32499
177 176
639 638
46383 46384
...

output:

impossible

result:

ok single line: 'impossible'

Test #16:

score: 0
Accepted
time: 23ms
memory: 18804kb

input:

100000
26307 26308
590 591
98899 98900
50854 50855
77753 77754
38014 38013
75156 75157
10027 10028
83934 83935
43862 43863
65101 65102
7784 7783
93163 93164
29841 29840
3862 3863
6542 6541
6432 6433
93756 93757
68690 68691
51050 51049
18593 18592
15431 15430
82511 82512
45462 45461
64205 64204
94833...

output:

49874

result:

ok single line: '49874'

Subtask #5:

score: 40
Accepted

Test #17:

score: 40
Accepted
time: 19ms
memory: 10620kb

input:

89310
15556 57000
19677 35349
9259 25855
43787 63864
64941 54366
20524 82369
74758 65181
26075 75148
76809 29415
64603 77798
60446 1000
86747 70876
65376 11036
2506 88761
45097 50529
45097 83913
33059 79620
54248 11298
37025 18974
7782 83068
63113 70024
69926 54332
21966 1572
79769 72650
24200 8844
...

output:

impossible

result:

ok single line: 'impossible'

Test #18:

score: 0
Accepted
time: 24ms
memory: 10988kb

input:

97913
60901 97087
58758 18416
94565 79381
52627 69968
79332 28132
89565 51130
90984 38208
62087 73972
29822 64941
67608 46225
644 81550
84132 50804
45068 71032
37455 7438
17667 9948
61523 4597
65924 91070
22443 25958
31160 14625
13587 2112
25093 77187
18779 6106
49481 75765
27 68731
49664 65562
5747...

output:

impossible

result:

ok single line: 'impossible'

Test #19:

score: 0
Accepted
time: 24ms
memory: 10988kb

input:

100000
4295 68473
92097 94209
57506 89966
61594 21263
43468 16856
26528 97633
11616 7895
91566 89927
92513 20274
32705 89318
9358 14599
89211 90918
37953 92203
53296 70865
58770 33236
52669 3248
81548 82487
62857 97586
633 88495
87068 7543
70408 70915
22405 88192
4700 57860
2102 58575
4690 48175
153...

output:

impossible

result:

ok single line: 'impossible'

Test #20:

score: 0
Accepted
time: 1ms
memory: 7588kb

input:

489
370 206
355 440
409 74
119 81
193 109
256 440
137 163
391 406
183 337
229 160
278 396
100 148
129 414
251 42
394 337
186 35
318 258
286 423
479 369
375 360
106 428
292 8
475 312
2 384
484 14
121 189
431 287
217 195
26 148
361 26
318 196
381 112
237 254
192 117
58 455
301 293
436 199
405 171
208 ...

output:

impossible

result:

ok single line: 'impossible'

Test #21:

score: 0
Accepted
time: 4ms
memory: 8752kb

input:

33015
15418 23360
4668 7924
16645 26717
17951 23465
11142 667
7557 10780
7606 30099
15114 6492
4564 28298
15451 2422
3409 26013
32382 16835
17083 30779
2940 26306
15689 21703
13789 23557
11954 7170
19696 29702
4215 24839
32580 30787
24785 22607
27747 13598
25853 29523
22282 599
22986 14068
4240 1064...

output:

impossible

result:

ok single line: 'impossible'

Test #22:

score: 0
Accepted
time: 23ms
memory: 11012kb

input:

98374
69 80221
33515 37515
86494 27854
81308 778
44462 43415
55710 50028
65094 73567
87006 88171
97819 24477
4645 23402
54901 76804
55599 36606
42426 25953
70106 36924
50723 75964
84800 97276
78457 67729
11888 51074
43110 2956
55007 15808
70905 47230
35496 83091
74080 17318
26289 80252
71084 67358
2...

output:

impossible

result:

ok single line: 'impossible'

Test #23:

score: 0
Accepted
time: 23ms
memory: 11160kb

input:

100000
84537 84238
74684 66651
3616 35955
74564 19702
17317 24588
56638 96514
28303 37186
19487 88194
65052 6877
82682 9889
50590 10934
38881 17555
63518 91566
29999 99309
73899 36549
95616 14122
57419 40633
58521 1396
9121 26409
71435 9509
46131 21457
78899 56135
79322 84823
7535 46220
71272 33613
...

output:

impossible

result:

ok single line: 'impossible'

Test #24:

score: 0
Accepted
time: 23ms
memory: 11560kb

input:

97129
67880 23023
52047 91456
60613 60455
80799 63726
41173 92308
7359 20324
34227 53556
39628 79032
97091 29349
76596 43855
68113 91452
15530 95457
79529 95995
58417 38134
63320 62816
88030 64504
20613 94575
15002 91174
70672 72919
58718 83725
19912 66568
61433 46377
42668 1789
273 963
84824 19685
...

output:

impossible

result:

ok single line: 'impossible'

Test #25:

score: 0
Accepted
time: 29ms
memory: 11712kb

input:

100000
62439 76409
95459 68478
20107 4685
27532 62113
92848 72835
54860 86728
66051 56643
2269 20555
7919 25817
53010 22929
55630 53209
94816 13964
28772 9971
64559 92028
42696 50041
46409 61841
15715 82777
45642 2509
99454 69078
6709 30403
73425 47062
34901 58963
72890 30783
5947 87873
85289 25969
...

output:

impossible

result:

ok single line: 'impossible'

Test #26:

score: 0
Accepted
time: 24ms
memory: 10780kb

input:

93749
44689 73457
25775 29184
44348 47456
33223 20237
10596 47456
39687 90032
9023 3104
75226 91414
49766 50441
8575 56785
35868 66876
50056 23168
8727 86092
8716 88971
27586 81685
67376 70224
32770 47040
80203 86109
614 84656
35993 22685
27225 43178
6667 74915
72029 65776
2893 43473
7746 70849
1715...

output:

46976

result:

ok single line: '46976'

Test #27:

score: 0
Accepted
time: 21ms
memory: 11108kb

input:

100000
31901 82127
85367 15698
42050 42581
90836 16099
39427 4619
43693 98513
76083 14774
91467 49103
39804 7027
57774 5521
13786 79920
44379 39932
57044 27945
17748 70732
849 69282
41040 31352
13971 81723
75355 61542
20289 11222
34817 8790
70355 83710
9652 99655
65504 97236
40789 85438
15233 91194
...

output:

49703

result:

ok single line: '49703'

Subtask #6:

score: 30
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

100%
Accepted

Test #28:

score: 30
Accepted
time: 4ms
memory: 8752kb

input:

33015
30539 20437
4949 10321
7969 21984
10226 7396
3596 1739
1234 9688
9685 28843
6534 28960
19727 4647
9411 31815
23876 24315
32174 27416
2714 501
30754 14191
23094 11754
19799 22065
5730 28999
26041 10273
6238 16977
10072 19271
23655 1021
6477 18634
28692 6558
1104 1531
18621 15574
4702 27563
1963...

output:

impossible

result:

ok single line: 'impossible'

Test #29:

score: 0
Accepted
time: 24ms
memory: 10744kb

input:

89310
41377 78814
81308 54209
84029 36456
31813 63647
69687 50845
37552 3725
30317 30630
70252 6
25553 45478
5385 24758
5218 75948
39402 71523
10542 38376
55513 40529
66176 29948
58422 47863
11444 67924
77248 30223
26602 4211
83661 39950
26857 35900
46471 15862
22358 81987
88192 88500
29053 49026
64...

output:

impossible

result:

ok single line: 'impossible'

Test #30:

score: 0
Accepted
time: 26ms
memory: 11120kb

input:

97913
11499 81030
82703 72265
29355 12609
94637 8508
77325 41683
23609 84470
96474 82545
71403 76776
81225 62329
17084 41088
28962 93836
32860 40967
68979 56229
53467 75399
55920 5504
49052 69526
96245 50633
94095 63192
61336 57729
78306 55444
84751 43615
41002 56175
36477 44631
86941 4639
23003 258...

output:

impossible

result:

ok single line: 'impossible'

Test #31:

score: 0
Accepted
time: 27ms
memory: 11128kb

input:

100000
19585 89988
24445 53796
23612 34882
29552 59138
40991 72580
21525 43844
26882 50960
60386 36122
29457 44882
60787 98064
96286 75395
35388 92501
53047 34596
35263 31930
86608 29928
31826 14891
18351 85597
83665 8734
26459 50736
16724 92570
99044 24360
96323 57074
71327 35235
94539 26630
61878 ...

output:

impossible

result:

ok single line: 'impossible'

Test #32:

score: 0
Accepted
time: 27ms
memory: 11136kb

input:

100000
85591 53276
51081 92907
13367 60746
3338 84233
98138 8677
44607 75808
59364 67386
3171 97125
174 27418
95096 80156
19695 5778
74642 30856
51889 56107
76394 23301
13619 27775
56835 98157
88712 96079
88409 94283
81284 44294
74287 3935
53142 16871
46934 40669
81048 19917
1554 37073
16151 46669
6...

output:

impossible

result:

ok single line: 'impossible'

Test #33:

score: 0
Accepted
time: 27ms
memory: 11192kb

input:

100000
75973 91366
5789 22165
42836 67278
91127 33109
51675 34725
15535 85185
33334 11300
34359 12630
16409 74752
17116 83434
19130 29696
23096 65907
16788 16576
42527 9586
41074 35870
52944 62025
99352 26369
66064 70209
37814 11195
2519 64751
50755 72435
87935 75680
63420 96040
33657 27460
35168 81...

output:

impossible

result:

ok single line: 'impossible'

Test #34:

score: 0
Accepted
time: 18ms
memory: 11540kb

input:

100000
2049 54989
47380 16401
27865 56857
68686 28575
21139 25822
97944 48869
16622 64307
72812 70217
7304 10844
88026 84934
66059 46267
7302 27100
80758 44496
53423 27354
87037 9666
61163 3624
97944 90833
7862 50541
30881 71739
41360 5939
46007 23496
86639 98394
87485 58601
94554 99826
89272 27064
...

output:

50001

result:

ok single line: '50001'

Test #35:

score: 0
Accepted
time: 19ms
memory: 11612kb

input:

100000
35539 95887
99118 92815
81826 70693
3777 14984
34354 22552
22371 29368
52207 99334
32346 63351
38711 5534
83142 25870
75935 39689
95062 22414
60908 82622
42462 88428
98660 38917
22082 96732
20054 56814
65127 39121
13977 23558
76786 24994
67307 41976
99804 10088
72266 76097
17934 17390
99964 6...

output:

impossible

result:

ok single line: 'impossible'

Test #36:

score: 0
Accepted
time: 26ms
memory: 11108kb

input:

100000
20000 56393
7756 20000
26452 20000
20000 76464
42155 20000
20000 42915
40536 20000
20000 31495
20000 90830
9093 20000
55490 20000
61380 20000
20000 85013
20000 57637
39904 20000
13635 20000
20000 60198
458 20000
20000 56555
96858 20000
20000 49842
20000 89525
20000 20312
85499 20000
20000 470...

output:

impossible

result:

ok single line: 'impossible'

Test #37:

score: 0
Accepted
time: 20ms
memory: 10996kb

input:

100000
53457 19821
53457 88471
53457 23581
53457 2562
53457 88919
18771 53457
14017 53457
53457 50650
22329 53457
53457 13934
53457 87374
53457 47682
34763 53457
89140 53457
83428 53457
53457 88394
53457 17497
53457 70633
53457 92042
53457 74633
53457 4586
53457 79153
6842 53457
90755 53457
53457 81...

output:

impossible

result:

ok single line: 'impossible'

Test #38:

score: 0
Accepted
time: 19ms
memory: 11036kb

input:

100000
27083 92855
47502 27083
66370 27083
27083 83087
27083 37155
27083 63527
40133 27083
57368 27083
27083 44291
28915 27083
43036 27083
27083 55661
27083 27561
27083 85900
9048 27083
27083 65135
27083 51740
47959 27083
27083 66749
8826 27083
27083 68134
27083 11414
80452 27083
62141 27083
27083 1...

output:

49948

result:

ok single line: '49948'

Test #39:

score: 0
Accepted
time: 20ms
memory: 11000kb

input:

100000
83373 3413
83373 90061
11880 83373
83373 16289
7873 83373
83373 35431
83373 93243
85738 83373
37408 83373
83373 81436
83373 28660
64788 83373
83373 46843
83373 95116
83373 43524
2349 83373
32638 83373
28003 83373
6294 83373
83373 21256
463 83373
83373 48446
83373 88665
84969 83373
83373 20889...

output:

49967

result:

ok single line: '49967'