QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#428475 | #4889. 愚蠢的在线法官 | _LAP_ | 16 | 195ms | 48216kb | C++14 | 1.3kb | 2024-06-01 19:43:02 | 2024-06-01 19:43:02 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10, M = 1e6 + 10, MOD = 998244353;
inline int Plus(int a, int b) {return a + b >= MOD ? a + b - MOD : a + b; }
inline int Minus(int a, int b) {return a - b < 0 ? a - b + MOD : a - b; }
int h[N], e[M], ne[M], idx;
inline void add(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx ++; }
int n, k, A[N], val[N];
bool key[N];
int f[N][2];
void dfs(int u, int fa) {
f[u][0] = 1;
for(int i = h[u]; i != -1; i = ne[i]) {
int v = e[i]; if(v == fa) continue;
dfs(v, u);
f[u][1] = Plus(1ll * f[u][1] * f[v][0] % MOD, 1ll * f[u][0] * f[v][1] % MOD);
f[u][0] = 1ll * f[u][0] * f[v][0] % MOD;
}
if(key[u])
f[u][1] = f[u][0], f[u][0] = 1ll * f[u][0] * Minus(val[u], val[fa]) % MOD;
else
f[u][0] = Plus(f[u][0], 1ll * f[u][1] * Minus(val[u], val[fa]) % MOD);
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
memset(h, -1, sizeof h);
cin >> n >> k;
for(int i = 1; i <= n; i ++) cin >> val[i];
for(int i = 1; i <= k; i ++) cin >> A[i];
for(int i = 1; i <= k; i ++) key[A[i]] = true;
for(int i = 1; i < n; i ++) {
int a, b; cin >> a >> b;
add(a, b), add(b, a);
}
dfs(1, 0);
cout << f[1][0] << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 185ms
memory: 21740kb
input:
499999 500000 879485015 176694934 629415436 677018935 33186863 696674214 19586946 878479076 318116264 823399347 140314195 715329843 996129441 446979068 600062488 847953138 978347569 865596472 147980317 199880680 187953368 989585254 457868128 466175307 381871948 369138343 826894839 963935318 36550896...
output:
386964321
result:
wrong answer 1st numbers differ - expected: '0', found: '386964321'
Subtask #2:
score: 0
Wrong Answer
Test #2:
score: 6
Accepted
time: 0ms
memory: 14148kb
input:
10 1 663730929 273617752 74933376 562874267 346105266 779139305 198742356 291012786 227170675 127136999 2 10 8 5 10 1 5 9 8 6 10 4 6 3 1 2 4 7 3
output:
273617752
result:
ok 1 number(s): "273617752"
Test #3:
score: 6
Accepted
time: 0ms
memory: 15240kb
input:
10 10 144077216 482507381 588297929 801675226 21569141 816295251 425507414 150613951 822735519 802838587 7 10 9 2 1 6 8 3 5 4 10 9 6 10 5 6 2 5 8 5 3 5 1 10 4 2 7 1
output:
816324383
result:
ok 1 number(s): "816324383"
Test #4:
score: 6
Accepted
time: 0ms
memory: 14324kb
input:
10 2 136932305 774891472 782708047 361400653 241613404 206577781 241535900 917672952 105332067 165467540 2 5 2 4 5 4 1 4 7 2 3 5 10 5 8 3 6 10 9 10
output:
830180673
result:
ok 1 number(s): "830180673"
Test #5:
score: 6
Accepted
time: 0ms
memory: 15908kb
input:
10 3 106669121 934163752 505411505 487296100 135689018 776930268 130240777 167200291 726820445 449323201 10 5 2 9 5 3 5 2 9 1 3 7 1 8 7 6 2 4 9 10 6
output:
516982188
result:
ok 1 number(s): "516982188"
Test #6:
score: 6
Accepted
time: 3ms
memory: 14936kb
input:
10 4 554115046 86946870 492346089 759285688 597393634 534292327 742418751 40866289 456853511 777192624 6 10 1 4 3 4 5 4 7 4 2 7 9 4 10 2 8 7 1 7 6 10
output:
525980396
result:
ok 1 number(s): "525980396"
Test #7:
score: 6
Accepted
time: 0ms
memory: 14456kb
input:
10 5 156072097 743398614 639218862 297252114 250194624 291963313 870909501 644015194 402352389 623034872 7 2 6 5 8 3 7 10 7 5 7 4 3 6 4 9 4 1 10 2 6 8 10
output:
971134438
result:
ok 1 number(s): "971134438"
Test #8:
score: 6
Accepted
time: 1ms
memory: 15072kb
input:
10 6 58754522 928459597 174632208 377936445 469281312 236879760 214372862 700076292 513613148 778426835 2 9 6 8 7 10 1 3 9 3 10 9 7 9 8 7 5 7 4 9 6 4 2 10
output:
383720205
result:
ok 1 number(s): "383720205"
Test #9:
score: 6
Accepted
time: 0ms
memory: 15412kb
input:
10 7 168762354 271736588 761917216 86643499 677986829 885713846 696532784 435399905 113862203 798130316 10 6 8 5 2 1 4 6 1 7 1 3 7 8 6 9 3 5 9 2 9 10 8 4 5
output:
336844044
result:
ok 1 number(s): "336844044"
Test #10:
score: 6
Accepted
time: 0ms
memory: 17560kb
input:
10 8 727643452 96661577 109323043 94391368 943841820 772388814 620778403 424167899 950821917 236642846 6 2 8 1 7 3 10 4 4 6 1 4 10 6 3 4 7 3 2 6 9 10 5 1 8 2
output:
180649465
result:
ok 1 number(s): "180649465"
Test #11:
score: 6
Accepted
time: 0ms
memory: 13852kb
input:
10 9 117163394 156945447 136708770 224773742 105988662 323714230 608540583 786406145 376690056 848998167 5 3 1 8 9 4 2 10 7 2 5 3 5 10 2 7 2 4 3 6 3 1 4 9 5 8 7
output:
199480877
result:
ok 1 number(s): "199480877"
Test #12:
score: 6
Accepted
time: 3ms
memory: 15820kb
input:
10 1 310390327 26621492 98419973 106234069 846950161 118046850 174859624 961989377 51668388 989751256 10 7 1 9 1 2 7 5 7 10 9 6 9 8 2 4 2 3 5
output:
989751256
result:
ok 1 number(s): "989751256"
Test #13:
score: 6
Accepted
time: 3ms
memory: 14576kb
input:
10 10 455951699 832766533 368655882 274544983 630176565 149197662 125666866 811780187 718334218 758563081 6 4 8 5 7 1 2 10 9 3 7 1 10 1 4 7 9 7 6 10 8 10 5 4 2 4 3 9
output:
859352350
result:
ok 1 number(s): "859352350"
Test #14:
score: 6
Accepted
time: 3ms
memory: 14384kb
input:
10 2 987594303 113921174 60526162 363948313 953235693 442146116 239088362 970808700 672708631 266329194 1 7 3 1 5 1 7 3 4 3 9 5 6 5 10 7 2 7 8 4
output:
670634365
result:
ok 1 number(s): "670634365"
Test #15:
score: 6
Accepted
time: 0ms
memory: 17844kb
input:
10 3 816651453 62348752 681535935 116805607 955973251 476700964 874368097 579852140 368797919 88107985 3 8 9 2 1 4 1 10 2 3 2 7 4 5 4 9 10 8 10 6 3
output:
384680534
result:
ok 1 number(s): "384680534"
Test #16:
score: 6
Accepted
time: 0ms
memory: 14880kb
input:
10 4 58528783 12671113 11126837 192243188 969173998 711355158 552139230 134986041 320297780 856214300 4 10 2 5 6 1 9 1 2 6 4 6 5 9 8 9 3 2 10 2 7 4
output:
935582164
result:
ok 1 number(s): "935582164"
Test #17:
score: 6
Accepted
time: 0ms
memory: 17516kb
input:
10 5 918601200 505156312 418368340 295664939 184721209 379115481 848903082 880171694 194423672 240200865 3 4 10 1 9 5 1 6 1 9 5 10 5 2 6 4 6 7 9 3 9 8 10
output:
939502688
result:
ok 1 number(s): "939502688"
Test #18:
score: 6
Accepted
time: 0ms
memory: 15348kb
input:
10 6 533004017 920499852 255505289 485140854 915061638 943663314 522785302 422180206 691568926 180303165 4 8 6 7 2 9 10 1 4 1 9 10 8 10 3 4 5 4 7 9 6 9 2 8
output:
245402078
result:
ok 1 number(s): "245402078"
Test #19:
score: 6
Accepted
time: 0ms
memory: 14964kb
input:
10 7 352055946 828848449 193657266 250426731 531119954 123361593 818336280 448454352 385509919 877884505 4 8 1 2 3 7 5 6 1 8 1 9 6 4 6 7 8 5 8 3 9 10 9 2 4
output:
437134755
result:
ok 1 number(s): "437134755"
Test #20:
score: 6
Accepted
time: 2ms
memory: 17584kb
input:
10 8 222505897 729863884 642300093 102527485 464137817 473460079 845548391 73579791 864520933 350567502 3 8 6 5 1 4 7 2 9 1 6 1 5 9 3 9 10 6 8 6 2 5 4 5 7 3
output:
362729610
result:
ok 1 number(s): "362729610"
Test #21:
score: 6
Accepted
time: 0ms
memory: 15292kb
input:
10 9 310531917 121040796 201720207 819345654 577591809 36619321 65407253 957660104 168632846 972191988 3 2 4 10 1 8 5 7 6 8 1 3 1 9 8 4 8 2 3 5 3 6 9 10 9 7 4
output:
7616320
result:
ok 1 number(s): "7616320"
Test #22:
score: 6
Accepted
time: 0ms
memory: 13816kb
input:
10 1 176826797 993104097 437228475 200083350 883358996 226269431 774694002 958882177 761126249 319383560 1 5 10 4 5 9 4 6 9 8 6 2 8 1 2 3 1 7 3
output:
176826797
result:
ok 1 number(s): "176826797"
Test #23:
score: 6
Accepted
time: 0ms
memory: 17708kb
input:
10 10 30079784 360490012 614575707 114958413 538017501 766980081 227243229 64074734 143317951 384396094 2 6 7 8 5 1 4 10 3 9 4 6 1 4 10 1 2 10 9 2 3 9 7 3 8 7 5 8
output:
392261918
result:
ok 1 number(s): "392261918"
Test #24:
score: 6
Accepted
time: 0ms
memory: 15856kb
input:
10 2 15319105 320956351 16097549 796607736 925606797 701963523 564229119 389994811 268587770 568257143 6 5 9 3 6 9 4 6 1 4 5 1 7 5 8 7 2 8 10 2
output:
603533874
result:
ok 1 number(s): "603533874"
Test #25:
score: 6
Accepted
time: 0ms
memory: 17600kb
input:
10 3 44467062 848254409 944037739 214010122 199987320 42351578 71741265 869158293 181319317 473381037 5 2 6 8 2 10 8 9 10 1 9 3 1 4 3 6 4 5 6 7 5
output:
545061818
result:
ok 1 number(s): "545061818"
Test #26:
score: 6
Accepted
time: 0ms
memory: 17808kb
input:
10 4 190443107 301626916 303642985 164619167 499088700 93817253 975100330 262829154 978166486 288412971 10 8 2 4 8 3 6 8 2 6 10 2 5 10 9 5 7 9 4 7 1 4
output:
594401130
result:
ok 1 number(s): "594401130"
Test #27:
score: 6
Accepted
time: 0ms
memory: 17796kb
input:
10 5 110793878 310328709 227166902 980758502 554847856 359024344 463071742 292118656 631555660 980587509 9 3 6 1 7 4 9 7 4 10 7 3 10 5 3 6 5 8 6 2 8 1 2
output:
753066803
result:
ok 1 number(s): "753066803"
Test #28:
score: 6
Accepted
time: 0ms
memory: 15256kb
input:
10 6 408680647 280087657 455789909 955735280 548605911 478765573 226976310 231047820 377968528 425761364 4 10 2 5 7 8 3 9 8 3 10 8 4 10 1 4 2 1 5 2 6 5 7 6
output:
308535888
result:
ok 1 number(s): "308535888"
Test #29:
score: 6
Accepted
time: 0ms
memory: 15224kb
input:
10 7 153452208 742977622 213209346 805345546 844591057 833352142 885290602 332667906 121009427 370665044 6 4 1 5 8 9 2 5 4 3 5 8 3 9 8 2 9 1 2 7 1 6 7 10 6
output:
308496735
result:
ok 1 number(s): "308496735"
Test #30:
score: 6
Accepted
time: 0ms
memory: 14776kb
input:
10 8 935213254 97676917 940161417 449680462 488762117 149428956 53538771 149098863 224101629 296182299 3 9 7 2 4 10 5 8 9 1 3 9 6 3 7 6 5 7 2 5 4 2 10 4 8 10
output:
652166784
result:
ok 1 number(s): "652166784"
Test #31:
score: 6
Accepted
time: 3ms
memory: 14648kb
input:
10 9 456742144 553041375 5867236 530066976 785298902 317844948 748554302 641854054 754601526 830217622 3 7 6 8 5 4 1 2 10 6 4 2 6 5 2 9 5 1 9 3 1 8 3 7 8 10 7
output:
287008023
result:
ok 1 number(s): "287008023"
Test #32:
score: 6
Accepted
time: 2ms
memory: 14156kb
input:
10 1 654029472 298153105 209351017 117803612 39983728 918790970 82428460 281708618 597736551 939830393 8 3 8 4 8 2 8 5 8 10 8 9 8 1 8 7 8 6 8
output:
281708618
result:
ok 1 number(s): "281708618"
Test #33:
score: 6
Accepted
time: 2ms
memory: 14276kb
input:
10 10 815031204 504027511 420973193 443230724 60015324 629020761 198129478 973455912 667696713 81705176 4 10 1 2 6 8 9 3 5 7 1 2 5 2 10 2 8 2 6 2 7 2 9 2 3 2 4 2
output:
965712618
result:
ok 1 number(s): "965712618"
Test #34:
score: 6
Accepted
time: 0ms
memory: 14536kb
input:
10 2 810912843 321442222 167408147 150459017 319505790 205482194 434032701 915771345 32570479 46068323 4 10 6 4 1 4 5 4 10 4 9 4 8 4 3 4 2 4 7 4
output:
192345387
result:
ok 1 number(s): "192345387"
Test #35:
score: 6
Accepted
time: 0ms
memory: 15280kb
input:
10 3 28606805 992656838 409799793 284693896 665536294 735549707 385528702 709032715 127474148 628237946 1 3 10 2 8 3 8 5 8 7 8 9 8 6 8 1 8 10 8 4 8
output:
5032130
result:
ok 1 number(s): "5032130"
Test #36:
score: 6
Accepted
time: 0ms
memory: 13976kb
input:
10 4 838731516 902989484 984968609 231223629 691996501 634243912 628250615 2314503 251145300 660804486 8 2 4 1 3 7 1 7 8 7 10 7 4 7 9 7 6 7 5 7 2 7
output:
393189683
result:
ok 1 number(s): "393189683"
Test #37:
score: 6
Accepted
time: 0ms
memory: 14464kb
input:
10 5 103358211 987438369 172995049 181914491 650269872 961462921 148532141 506079325 420012385 411301164 9 7 5 1 8 1 2 6 2 7 2 4 2 8 2 5 2 10 2 9 2 3 2
output:
243389542
result:
ok 1 number(s): "243389542"
Test #38:
score: 6
Accepted
time: 0ms
memory: 14916kb
input:
10 6 738939095 462022763 568173107 500905679 321356488 753819583 159648909 619473204 606464394 19394894 5 10 6 1 3 9 9 4 1 4 2 4 6 4 5 4 3 4 7 4 8 4 10 4
output:
123685535
result:
ok 1 number(s): "123685535"
Test #39:
score: 6
Accepted
time: 0ms
memory: 14660kb
input:
10 7 202547886 646401736 93164326 422174119 436766865 666557482 142214475 72224229 969751790 188142466 4 8 3 10 6 7 2 7 1 8 1 5 1 2 1 10 1 4 1 9 1 6 1 3 1
output:
171412495
result:
ok 1 number(s): "171412495"
Test #40:
score: 6
Accepted
time: 0ms
memory: 17868kb
input:
10 8 342750163 757047550 6702148 786150699 919530550 866064379 196212597 270399055 646964848 71988965 4 9 1 2 5 6 7 8 5 10 6 10 1 10 9 10 8 10 4 10 7 10 3 10 2 10
output:
410117969
result:
ok 1 number(s): "410117969"
Test #41:
score: 6
Accepted
time: 0ms
memory: 14688kb
input:
10 9 708468107 852623868 230491853 68750332 475802506 803976211 334452286 841322432 721667182 67588114 2 1 3 4 7 9 10 6 5 3 5 7 5 1 5 6 5 2 5 4 5 10 5 8 5 9 5
output:
391675231
result:
ok 1 number(s): "391675231"
Test #42:
score: 0
Wrong Answer
time: 0ms
memory: 13832kb
input:
10 5 323063351 730481512 370548177 802215316 911918467 914669598 543857289 821891818 548953740 960792658 10 6 7 3 3 3 4 10 4 9 10 7 3 5 4 1 9 8 7 2 10 6 2
output:
767162193
result:
wrong answer 1st numbers differ - expected: '0', found: '767162193'
Subtask #3:
score: 0
Wrong Answer
Test #43:
score: 11
Accepted
time: 173ms
memory: 21792kb
input:
500000 600 375999961 486674339 753591626 263678997 153496902 843204506 294273913 59353025 80121537 938426018 309354784 359915003 480316315 880954496 544396164 478808641 583197144 202111021 277512785 193266475 511298159 750302398 30978705 278891583 701736665 516664158 47658598 456194527 517690925 870...
output:
739558267
result:
ok 1 number(s): "739558267"
Test #44:
score: 11
Accepted
time: 165ms
memory: 21752kb
input:
500000 600 144424234 822427316 300192847 7262228 210896294 454472658 15628508 599308527 39208834 748087468 100403532 861554271 440434658 207763150 960826231 405540153 513306322 903562629 19659973 24682032 339889038 859238787 933505007 113096874 144805990 391745221 750054096 992392845 976030209 54069...
output:
144059750
result:
ok 1 number(s): "144059750"
Test #45:
score: 11
Accepted
time: 153ms
memory: 21740kb
input:
500000 600 331840935 487267543 141846510 959026554 23406702 924114236 382412574 498288136 278551271 468110673 889355705 280620460 293234713 915880082 112280963 634256130 769027328 297590919 844224351 761851954 220242868 91163991 403705643 47533012 401410594 110156291 810282175 26989897 18481764 8392...
output:
483838047
result:
ok 1 number(s): "483838047"
Test #46:
score: 11
Accepted
time: 133ms
memory: 21804kb
input:
500000 600 53862718 259806630 150158643 181217331 113064043 454111950 428452164 976639831 608516063 26785656 323722935 479978164 897653034 385776962 891522660 805681141 668633845 682173127 425775925 152860757 661118323 78766810 557465765 279838691 263662634 788444774 35025549 657163252 525195519 667...
output:
571994801
result:
ok 1 number(s): "571994801"
Test #47:
score: 11
Accepted
time: 143ms
memory: 48216kb
input:
500000 600 503473613 365243138 600037485 794034899 794552034 774168344 213632833 222607873 840997672 209089919 507182333 932583841 952032419 58613852 251087250 669879021 47148034 550524618 392246249 639068987 776360220 40611378 480234261 470879368 887158649 370114946 968903569 166932590 98362078 781...
output:
113780969
result:
ok 1 number(s): "113780969"
Test #48:
score: 11
Accepted
time: 125ms
memory: 21736kb
input:
500000 600 607381480 855257322 86837613 746292682 784437716 57828253 965602864 73366173 773343611 613090636 974259882 306344413 101762602 561276318 273649470 372936825 332131006 195006635 706694602 206926288 569775417 575506863 69587689 306273511 861134280 539359231 514955013 395790534 233435991 109...
output:
706488870
result:
ok 1 number(s): "706488870"
Test #49:
score: 0
Wrong Answer
time: 185ms
memory: 21736kb
input:
500000 600 47276203 913060613 450816229 609126980 959139016 643131397 323632377 809345946 695036059 311699768 499433533 464837625 20916653 253473039 272974046 144202520 759240782 322252624 597886217 304390498 467405890 162800240 73662318 67080226 221733451 123656796 186936776 424886406 794288225 915...
output:
351389208
result:
wrong answer 1st numbers differ - expected: '0', found: '351389208'
Subtask #4:
score: 0
Skipped
Dependency #2:
0%
Subtask #5:
score: 16
Accepted
Test #77:
score: 16
Accepted
time: 181ms
memory: 21728kb
input:
500000 500000 200910665 704700912 664276 824905098 512233060 623259142 478040808 509760810 756074623 387351466 261683363 140331101 135736712 184881987 425557684 61914673 951508934 787260914 386285199 40458274 175322609 429002885 606957721 742057849 342942076 104844271 656874266 826513447 76400873 55...
output:
771496320
result:
ok 1 number(s): "771496320"
Test #78:
score: 16
Accepted
time: 195ms
memory: 21756kb
input:
500000 500000 393325784 423307620 769839934 488701594 34980277 797798611 971252417 460892286 567253464 767364025 93413829 75786578 256363071 217722512 645295877 510711584 480877049 428293642 214340569 818013745 26677511 669553845 89063601 534123295 248791524 138950624 251295359 636455647 417371091 7...
output:
439789184
result:
ok 1 number(s): "439789184"
Test #79:
score: 16
Accepted
time: 155ms
memory: 21732kb
input:
500000 500000 304834659 23334136 281137008 195895112 196794218 9096321 550195738 251406926 794310053 392944702 896889429 377202988 383812779 855411433 996638204 176946965 14610588 31326580 287865536 285356776 15181214 721975103 7479393 923265076 700703478 244253830 13595300 191060192 506315015 82731...
output:
386763205
result:
ok 1 number(s): "386763205"
Test #80:
score: 16
Accepted
time: 186ms
memory: 38608kb
input:
500000 500000 963769621 792032953 548743692 812303224 806859822 107106153 670071669 457532666 516564922 867509289 563112863 620766458 971804950 533739313 126272905 817695615 569475276 227580608 323342974 375310982 265196242 579298928 82855065 820284887 873105018 906167288 489289717 472219706 8127735...
output:
490477004
result:
ok 1 number(s): "490477004"
Test #81:
score: 16
Accepted
time: 148ms
memory: 21792kb
input:
500000 500000 934825416 221317375 979103615 273478171 355638257 208592783 254723141 463073783 405970022 680755268 266037075 931070258 928975898 442231376 471302244 364395206 266480387 284288074 707928785 957518641 526274338 899411209 442421594 13370142 383410592 249354068 255747031 99288455 18754772...
output:
809226100
result:
ok 1 number(s): "809226100"
Subtask #6:
score: 0
Skipped
Dependency #1:
0%