QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #291279 | #2426. The Xana coup | 1437vszombies | 100 ✓ | 29ms | 20768kb | C++14 | 1.2kb | 2023-12-26 09:58:48 | 2023-12-26 09:58:48 |
Judging History
answer
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<queue>
#include<random>
#include<ctime>
#include<map>
#include<cstring>
using namespace std;
const int maxn=100005;
const int inf=0x3f3f3f3f;
int n,dp[maxn][2][2],p[maxn],fa[maxn];
vector<int> tree[maxn];
void dfs(int s){
dp[s][0][p[s]]=p[s];
dp[s][1][p[s]^1]=(p[s]^1);
for(int j=0;j<tree[s].size();++j){
int s_=tree[s][j];
if(s_==fa[s])continue;
fa[s_]=s;
dfs(s_);
int tmp[2][2]={{dp[s][0][0],dp[s][0][1]},{dp[s][1][0],dp[s][1][1]}};
dp[s][1][0]=min(inf,min(dp[s_][0][1]+tmp[0][0],dp[s_][0][0]+tmp[1][0]));
dp[s][0][0]=min(inf,min(dp[s_][0][1]+tmp[1][0],dp[s_][0][0]+tmp[0][0]));
dp[s][1][1]=min(inf,min(dp[s_][1][1]+tmp[0][1],dp[s_][1][0]+tmp[1][1]));
dp[s][0][1]=min(inf,min(dp[s_][1][1]+tmp[1][1],dp[s_][1][0]+tmp[0][1]));
}
}
signed main(){
ios::sync_with_stdio(false);cin.tie(0);
cin>>n;
for(int i=1;i<n;++i){
int u,v;
cin>>u>>v;
tree[u].push_back(v);
tree[v].push_back(u);
}
for(int i=1;i<=n;++i)cin>>p[i];
memset(dp,0x3f,sizeof(dp));
dfs(1);
if(dp[1][0][1]>=inf&&dp[1][0][0]>=inf)cout<<"impossible";
else cout<<min(dp[1][0][1],dp[1][0][0]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Accepted
Test #1:
score: 0
Accepted
time: 1ms
memory: 8284kb
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: 2ms
memory: 8108kb
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: 2ms
memory: 8360kb
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: 0ms
memory: 8360kb
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: 8208kb
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: 0ms
memory: 8292kb
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: 8364kb
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: 1ms
memory: 7804kb
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: 8292kb
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: 8356kb
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: 8244kb
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: 8236kb
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: 0ms
memory: 8296kb
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: 21ms
memory: 20724kb
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: 29ms
memory: 20588kb
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: 22ms
memory: 20768kb
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: 21ms
memory: 11052kb
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: 22ms
memory: 11272kb
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: 28ms
memory: 11360kb
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: 0ms
memory: 8264kb
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: 10ms
memory: 9384kb
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: 26ms
memory: 11400kb
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: 24ms
memory: 11548kb
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: 28ms
memory: 12044kb
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: 27ms
memory: 12276kb
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: 25ms
memory: 11200kb
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: 26ms
memory: 11420kb
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: 6ms
memory: 9440kb
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: 21ms
memory: 11096kb
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: 23ms
memory: 11520kb
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: 19ms
memory: 11544kb
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: 11480kb
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: 11456kb
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: 15ms
memory: 12032kb
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: 17ms
memory: 11944kb
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: 16ms
memory: 11404kb
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: 11416kb
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: 12ms
memory: 11340kb
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: 22ms
memory: 11336kb
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'