QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#403403 | #8127. Slučajna Cesta | lfxxx# | 40 | 1951ms | 152220kb | C++14 | 2.0kb | 2024-05-02 10:47:57 | 2024-05-02 10:47:58 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pii pair<int, int>
#define all(x) (x).begin(), (x).end()
bool be;
constexpr int N = 1e6 + 5, mod = 1e9 + 7;
vector<int>e[N];
int n, a[N], dp[N], tp[N], ans[N];
inline int qpow(int b, int k)
{
int res = 1;
while (k) {
if (k & 1) res = (ll) res * b % mod;
b = (ll) b * b % mod;
k >>= 1;
}
return res;
}
void dfs1(int u, int f)
{
int c = e[u].size() - (u != f);
dp[u] = a[u];
for (int v : e[u]) {
if (v != f) {
dfs1(v, u);
dp[u] = (dp[u] + (ll) (tp[c] - 1) * qpow((ll) tp[c] * c % mod, mod - 2) % mod * dp[v]) % mod;
}
}
}
void hg(int u, int v)
{
int c = e[u].size();
dp[u] = (dp[u] - a[u]) % mod;
dp[u] = (dp[u] - (ll) (tp[c] - 1) * qpow((ll) tp[c] * c % mod, mod - 2) * dp[v]) % mod;
dp[u] = (ll) dp[u] * 2 % mod * (tp[c - 1] - 1) % mod * c % mod * qpow((ll) (tp[c] - 1) * (c - 1) % mod, mod - 2) % mod;
dp[u] = (dp[u] + a[u]) % mod;
c = e[v].size();
dp[v] = (dp[v] - a[v]) % mod;
dp[v] = (ll) dp[v] * (tp[c] - 1) % mod * (c - 1) % mod * qpow(2ll * (tp[c - 1] - 1) % mod * c % mod, mod - 2) % mod;
dp[v] = (dp[v] + (ll) (tp[c] - 1) * qpow((ll) tp[c] * c % mod, mod - 2) * dp[u]) % mod;
dp[v] = (dp[v] + a[v]) % mod;
}
void dfs2(int u, int f)
{
ans[u] = (dp[u] + mod) % mod;
for (int v : e[u]) {
if (v != f) {
hg(u, v);
dfs2(v, u);
hg(v, u);
}
}
}
bool en;
int main()
{
cerr << (&be - &en) / 1024.0 / 1024 << " MB\n--------------------------------" << endl;
#ifdef IAKIOI
freopen("in.in", "r", stdin);
// freopen("out.out", "w", stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 2; i <= n; ++i) {
int f;
cin >> f;
e[f].emplace_back(i);
e[i].emplace_back(f);
}
for (int i = 1; i <= n; ++i) cin >> a[i];
tp[0] = 1;
for (int i = 1; i <= n; ++i) {
tp[i] = tp[i - 1] * 2ll % mod;
}
dfs1(1, 1);
dfs2(1, 1);
for (int i = 1; i <= n; ++i) cout << ans[i] << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 6ms
memory: 27724kb
input:
2 1 307903 536004
output:
575905 500689959
result:
ok all correct
Test #2:
score: 10
Accepted
time: 8ms
memory: 29212kb
input:
3 1 2 992649 690492 637324
output:
1497226 876301738 251230734
result:
ok all correct
Test #3:
score: 10
Accepted
time: 3ms
memory: 29048kb
input:
4 1 2 3 826918 524416 30987 233038
output:
501126006 889825 375470082 250483002
result:
ok all correct
Test #4:
score: 10
Accepted
time: 4ms
memory: 29304kb
input:
5 1 2 3 4 859332 957641 552087 294350 114098
output:
126520100 939052817 751204107 938304296 125572709
result:
ok all correct
Test #5:
score: 10
Accepted
time: 3ms
memory: 27556kb
input:
6 1 2 2 4 5 91742 92552 191745 529457 181043 884683
output:
47206686 156670572 984787945 922712805 617936136 829257432
result:
ok all correct
Test #6:
score: 10
Accepted
time: 3ms
memory: 28780kb
input:
7 1 1 3 4 4 6 69032 207537 280790 889967 218886 618588 754535
output:
293473187 945792944 24287651 511768034 204044442 255223945 87278766
result:
ok all correct
Test #7:
score: 10
Accepted
time: 3ms
memory: 27576kb
input:
8 1 2 2 4 2 6 7 546075 347525 670520 983062 581593 336046 97830 706738
output:
334418635 329187863 605358267 243713478 246081337 164970462 770221487 347328072
result:
ok all correct
Test #8:
score: 10
Accepted
time: 0ms
memory: 27636kb
input:
9 1 2 3 3 5 1 7 8 817515 848951 198209 119142 819728 367379 501231 458709 804045
output:
778945070 884374888 701481221 254592128 137000383 674805839 311894676 750233527 417348933
result:
ok all correct
Test #9:
score: 10
Accepted
time: 0ms
memory: 27556kb
input:
10 1 1 1 4 5 4 1 8 8 874755 324368 592836 600006 266724 217696 423188 402322 557734 423393
output:
616715460 217237546 634133532 688080628 590912992 60727477 121167098 530612063 430789154 868180005
result:
ok all correct
Test #10:
score: 10
Accepted
time: 6ms
memory: 28424kb
input:
10 1 2 3 1 5 6 7 7 9 195744 206104 723327 114978 178292 190130 540646 250919 152931 940237
output:
158806482 79765837 290477198 526950480 317003915 633487763 313413032 531963588 860175194 157463149
result:
ok all correct
Test #11:
score: 10
Accepted
time: 3ms
memory: 28372kb
input:
10 1 2 2 4 5 4 7 1 9 160335 133086 186701 906673 561321 529327 813569 759454 327734 62760
output:
612909843 659626152 629535210 48467043 569673492 130085768 77772881 52282583 56718813 704471661
result:
ok all correct
Test #12:
score: 10
Accepted
time: 0ms
memory: 28964kb
input:
10 1 2 2 1 5 6 7 8 9 286342 884910 904819 108098 292165 78969 566381 587683 156711 111976
output:
821283130 567751781 374520609 61373271 149275061 51484565 229512794 771472918 448321820 132272409
result:
ok all correct
Test #13:
score: 10
Accepted
time: 0ms
memory: 29272kb
input:
10 1 1 3 3 5 6 6 6 9 820907 494966 187493 466984 150135 896410 388758 105418 191024 930665
output:
363066644 242278836 612403907 108326578 274335852 819650079 613004775 29429418 811535270 291689673
result:
ok all correct
Test #14:
score: 10
Accepted
time: 0ms
memory: 28772kb
input:
10 1 2 3 4 5 5 7 7 9 780617 360476 946142 170041 984436 863484 705401 759288 364152 323780
output:
792343871 562727727 562167115 91166936 840366602 290796618 770432943 924365902 661973330 774831032
result:
ok all correct
Test #15:
score: 10
Accepted
time: 0ms
memory: 28676kb
input:
10 1 2 2 1 5 5 1 1 9 996177 507917 928080 610241 428655 745973 313129 879790 3630 222636
output:
585661496 324752716 780879684 93121435 366439393 584327336 833975652 801152444 944125266 629583216
result:
ok all correct
Test #16:
score: 10
Accepted
time: 3ms
memory: 27740kb
input:
10 1 2 3 4 5 6 7 8 9 485357 872875 543104 252486 738854 873509 801028 59862 417026 867486
output:
739460169 733862443 778669222 462141515 876563208 978255004 317930623 65403099 345776883 397765700
result:
ok all correct
Test #17:
score: 10
Accepted
time: 3ms
memory: 29272kb
input:
10 1 1 3 1 5 6 6 8 5 405829 249733 974377 17147 381677 349987 698528 659718 383030 547497
output:
828512375 738117175 280840778 603744319 264086975 110768674 214583133 895570339 763890880 911231948
result:
ok all correct
Test #18:
score: 10
Accepted
time: 0ms
memory: 28604kb
input:
10 1 2 3 1 5 6 7 8 7 114148 888405 653482 324506 212949 908169 155568 180096 181076 166389
output:
809474092 686924034 656473190 604449927 836836772 782500753 768863726 321788284 881297985 199739646
result:
ok all correct
Test #19:
score: 10
Accepted
time: 0ms
memory: 28200kb
input:
10 1 1 3 4 5 6 7 6 9 878639 541255 25599 274902 119473 639010 97108 753448 96106 773930
output:
983622610 739341242 903019368 274169390 281959300 123432644 720471011 147529573 361101388 741298692
result:
ok all correct
Test #20:
score: 10
Accepted
time: 8ms
memory: 28624kb
input:
10 1 2 2 2 2 2 2 2 2 766887 885978 73938 216251 903006 615990 205756 890530 603065 506057
output:
671137547 284402329 811845161 839566505 932739803 157080025 982378930 332142162 366784703 464349985
result:
ok all correct
Test #21:
score: 10
Accepted
time: 7ms
memory: 27288kb
input:
10 1 2 3 4 5 6 7 8 9 733342 202778 673543 829195 415681 35504 602267 386331 559518 466392
output:
735524386 852512262 329450881 470194237 94855921 266434302 571422189 161172655 331123819 887672425
result:
ok all correct
Test #22:
score: 10
Accepted
time: 3ms
memory: 28268kb
input:
10 1 2 2 1 4 4 6 3 8 904213 323773 607336 184293 233574 392314 370246 454542 257726 448337
output:
590656244 75229314 856033476 756000651 60461972 354421829 289846343 833907290 404114388 639532023
result:
ok all correct
Subtask #2:
score: 0
Wrong Answer
Test #23:
score: 30
Accepted
time: 0ms
memory: 28340kb
input:
100 1 2 1 4 5 6 7 7 9 9 5 12 5 4 1 16 17 18 18 20 20 22 23 24 25 23 27 28 27 30 31 32 27 34 35 36 37 38 39 39 41 38 43 43 45 46 43 48 49 49 49 48 48 54 55 56 57 57 55 60 60 62 55 64 65 64 67 67 69 69 69 72 37 74 75 76 76 78 76 80 81 82 80 84 85 74 87 87 89 89 91 89 87 94 94 96 97 98 98 754341 720186...
output:
744419112 868534785 579276734 966426530 89470157 365627670 936462279 93017671 603359319 522390035 22343082 205462129 636979071 211558039 86006737 525095665 167727115 994038924 460586504 309146514 877389799 199845255 163729135 868507823 372639715 82379059 856574083 348017654 982070262 781505719 17297...
result:
ok all correct
Test #24:
score: 0
Wrong Answer
time: 4ms
memory: 28204kb
input:
200 1 1 3 4 5 6 7 8 8 5 11 12 13 13 15 16 16 18 19 20 21 22 23 16 25 25 27 28 29 30 31 28 33 28 35 35 37 35 13 40 41 42 40 44 45 46 47 45 49 50 50 52 53 52 52 56 56 58 58 60 56 62 62 62 65 65 67 68 65 70 71 65 73 73 75 75 77 77 79 80 79 82 83 84 83 86 87 87 89 90 91 92 92 94 92 96 97 98 96 92 101 10...
output:
725084368 983709498 824961909 336358280 709426657 297523596 426557566 767786580 119003107 931503705 534694332 425258617 150579774 654744506 642042232 884679319 138214497 181144455 893410053 52582794 987525977 416233639 552678811 618456103 941998026 784721349 218719610 952238453 248625961 515894278 7...
result:
wrong output format Extra information in the output file
Subtask #3:
score: 30
Accepted
Test #54:
score: 30
Accepted
time: 96ms
memory: 31272kb
input:
60000 1 2 2 1 3 4 5 6 9 6 11 11 13 8 4 10 7 10 3 16 12 9 19 15 24 24 27 25 8 16 13 7 20 15 22 28 33 31 20 27 41 17 25 35 39 5 22 34 19 14 49 34 51 31 39 56 55 48 48 14 47 50 58 12 61 41 66 21 62 64 57 32 54 30 30 50 45 40 56 38 38 43 76 44 84 49 59 84 66 45 57 60 47 42 33 54 74 37 59 26 18 101 80 67...
output:
117639703 505499720 217392232 736598231 5788082 222979475 58628278 88739356 483103427 892979427 656931297 35461225 221784125 595137445 234234213 853473537 107407778 44940167 361717910 789976791 248194725 446646737 186263945 267774449 772729813 812060700 185754119 449015622 598022002 922192272 822202...
result:
ok all correct
Test #55:
score: 30
Accepted
time: 203ms
memory: 33136kb
input:
120000 1 1 2 3 5 4 5 6 8 10 11 2 9 14 14 9 16 12 6 16 7 17 11 24 7 18 21 3 13 29 23 12 8 20 20 27 22 31 13 19 39 36 18 37 38 24 47 17 4 15 35 39 23 48 50 21 30 34 10 60 57 51 34 63 33 58 27 30 69 46 66 46 61 69 68 31 54 36 57 25 47 80 48 45 85 19 62 88 50 54 22 66 67 89 76 74 80 87 74 75 59 41 32 10...
output:
727304663 355472490 462617883 941694097 689986532 682263666 596099564 338032623 562772851 35982083 590846989 881365594 391629792 317015282 589762863 776424897 909838528 843612804 380282938 313086297 407902883 212259529 801943217 182623029 689219952 353093239 236302099 591906911 962503319 160318152 2...
result:
ok all correct
Test #56:
score: 30
Accepted
time: 325ms
memory: 37592kb
input:
180000 1 1 3 4 2 4 3 7 2 7 5 6 11 5 11 13 8 13 19 8 6 19 9 23 23 21 22 28 29 28 17 22 30 33 20 30 10 27 21 25 9 12 37 41 18 43 26 46 26 45 14 34 10 48 54 12 47 51 29 51 45 59 44 34 48 60 38 64 32 62 55 39 58 49 14 76 68 54 49 32 52 37 56 25 38 84 43 59 83 42 36 33 83 84 90 78 77 79 80 62 68 53 53 31...
output:
125624698 360269195 114163212 992829457 128973868 205567918 398511928 424245128 617616178 338012939 388814477 136437309 974141592 873753113 615303295 276644353 979489222 581900833 113888039 595032785 723652701 756348240 194868716 12907458 314952980 236658151 109587921 487328299 606906709 954726517 3...
result:
ok all correct
Test #57:
score: 30
Accepted
time: 435ms
memory: 39748kb
input:
240000 1 1 3 2 2 3 6 6 9 10 9 4 13 5 5 14 12 10 8 14 4 19 18 18 15 11 23 26 28 28 23 13 29 16 25 22 27 17 30 33 15 33 36 17 24 37 19 21 20 42 48 25 46 43 35 56 20 36 29 54 51 22 38 44 34 16 39 57 59 68 12 30 8 41 71 58 66 39 64 57 71 37 38 68 27 82 62 65 11 43 81 88 40 94 77 26 47 53 70 49 31 31 45 ...
output:
986214575 391879844 313769139 988788582 582063594 716604697 540446330 377443771 401533213 34492372 384982640 454445589 4911223 784449196 389188243 67548065 615696023 151585232 870808843 518761490 976218926 363166900 710605865 623467875 106211884 156736621 953691903 865467745 566135268 481648566 8743...
result:
ok all correct
Test #58:
score: 30
Accepted
time: 526ms
memory: 41684kb
input:
300000 1 2 2 1 4 6 6 7 7 3 5 11 3 12 5 9 13 12 18 17 9 18 8 13 11 4 8 23 26 28 14 21 17 28 21 23 20 26 14 33 35 29 40 36 25 16 36 24 10 44 40 27 20 51 15 41 57 55 32 46 56 60 51 24 33 54 16 45 27 42 46 34 60 31 75 31 15 72 10 57 25 78 59 39 75 34 77 55 74 59 74 53 42 32 91 81 68 81 38 49 61 101 90 5...
output:
750785761 597404924 673403925 751419134 10718579 518101741 555640497 907224986 51818674 590609771 635692320 790839775 212618588 469669457 492495732 174195963 271828353 946990353 669109837 230112420 935060851 833777315 347012220 194524388 420629072 729937293 452119488 441086334 668908114 135599074 90...
result:
ok all correct
Test #59:
score: 30
Accepted
time: 640ms
memory: 44996kb
input:
360000 1 2 3 3 2 5 7 4 8 9 11 7 11 4 5 1 8 17 12 20 21 14 14 12 19 23 27 10 28 21 30 16 23 10 35 19 25 25 39 32 26 40 24 34 44 39 9 22 36 40 31 41 37 42 55 56 32 55 42 54 45 41 16 52 52 37 33 56 65 44 54 17 48 30 18 36 70 43 61 38 26 20 6 72 22 76 35 83 89 49 80 81 65 70 79 31 89 13 67 61 81 80 103 ...
output:
386620302 980588341 347083394 562055862 711003035 91247448 375101956 618309877 238529758 636332258 821602603 419200136 89387071 856004473 597904191 719995083 636809473 656249909 23537711 645094972 449693725 609160582 628867140 181682789 493333037 393960661 295482619 474705141 979224777 245171838 226...
result:
ok all correct
Test #60:
score: 30
Accepted
time: 770ms
memory: 47696kb
input:
420000 1 1 2 2 5 4 4 5 9 6 3 8 11 9 8 7 13 6 12 19 7 19 22 20 14 11 16 20 3 24 29 14 21 23 12 16 13 30 23 21 37 24 35 38 18 40 32 35 26 10 17 34 25 47 53 53 31 26 50 31 48 45 28 40 49 15 38 65 44 63 63 72 37 60 18 62 45 48 22 57 66 39 33 46 73 56 74 85 61 80 36 51 78 75 46 39 10 32 75 55 87 77 42 44...
output:
891229885 715977939 775201734 92135714 117564002 662375025 78928908 783087500 425484239 891160431 337979819 524470979 178370469 39507541 790150020 265761028 408037199 815328686 305467051 634848592 829682279 934008008 704167771 354224802 556946345 677986837 994973169 466546761 101491208 107153811 522...
result:
ok all correct
Test #61:
score: 30
Accepted
time: 880ms
memory: 50348kb
input:
480000 1 2 2 3 5 4 3 6 9 8 10 11 10 7 14 14 8 13 6 15 9 17 11 13 5 12 1 19 7 21 22 22 4 33 20 35 31 18 38 40 26 32 30 44 12 34 16 16 37 24 32 21 51 50 43 29 41 42 20 18 35 30 48 41 15 50 19 24 33 64 59 53 47 51 42 72 39 49 44 48 27 66 77 74 59 85 53 81 85 67 26 86 68 65 74 40 77 66 47 87 45 23 76 86...
output:
838857188 211732915 728920916 6097501 938782381 536183407 998705590 865721770 42475800 444960229 697676495 519727799 90131383 956160093 686096369 142976790 401525146 31252886 558447952 626521606 847493338 635781162 221312136 954915783 453882044 705789487 691995058 446131558 862250891 775810264 60812...
result:
ok all correct
Test #62:
score: 30
Accepted
time: 1024ms
memory: 54416kb
input:
540000 1 2 3 3 4 6 6 8 4 10 9 9 2 11 11 7 8 15 12 10 19 16 16 23 15 14 5 17 23 26 7 12 20 30 30 22 25 28 35 40 17 20 18 42 13 40 19 21 24 28 41 50 24 5 14 55 33 58 54 55 18 22 29 50 64 52 35 37 29 65 58 43 59 51 36 53 31 49 33 44 49 63 80 54 25 32 76 48 87 66 83 92 89 91 36 87 59 84 80 34 57 60 82 7...
output:
218337709 753563758 104923237 853597343 610199775 527932517 423050899 872943619 844067878 157157109 265064222 9640148 180803610 560389679 29311807 689638170 210729350 929830888 812526249 433617466 584961517 327285862 528366577 367213417 884056647 674119278 642036710 158605346 620455729 799670799 561...
result:
ok all correct
Test #63:
score: 30
Accepted
time: 1135ms
memory: 56092kb
input:
600000 1 2 3 4 3 5 5 4 2 8 1 7 10 8 11 13 11 18 10 7 13 18 15 6 17 20 26 19 29 12 23 31 14 30 35 12 27 24 29 15 28 16 16 37 41 36 25 19 46 33 41 32 45 27 54 46 17 48 34 59 36 34 57 48 58 53 65 32 44 62 6 54 59 49 50 63 40 58 43 51 55 66 49 84 76 51 65 87 9 22 86 14 31 37 89 95 66 79 40 79 44 42 47 7...
output:
196442068 94265043 21185905 996554435 331677968 841401316 315757248 583719505 843795594 274428568 226525614 611186096 479764490 614142723 753645904 102164865 35884426 988725491 795832988 89602098 391893811 619300934 521896498 794855348 135080045 384168994 512148256 756525131 768995985 678776163 4456...
result:
ok all correct
Test #64:
score: 30
Accepted
time: 1245ms
memory: 59268kb
input:
660000 1 2 3 2 1 6 3 7 8 9 4 8 9 13 13 5 5 7 17 10 20 18 15 23 17 11 19 18 28 30 29 6 21 15 19 27 34 12 16 16 31 35 23 44 36 44 22 14 31 42 48 24 53 37 12 14 55 30 48 35 59 22 36 42 59 45 11 39 21 66 34 56 55 66 27 46 20 32 71 73 81 25 26 37 80 10 87 68 47 67 41 60 84 67 77 57 47 83 28 29 46 68 97 3...
output:
82497201 204545685 213359758 399221318 648402308 635979772 673147729 706839903 173507611 477877493 459286700 489835447 667589662 279609800 580658090 755183011 796467253 158535731 114750187 797576932 581185214 143687729 851002555 296518048 549851243 497717843 796647313 939179788 720862026 496958971 3...
result:
ok all correct
Test #65:
score: 30
Accepted
time: 1411ms
memory: 62152kb
input:
720000 1 2 1 4 2 5 6 5 9 9 11 12 12 7 10 6 7 14 17 13 20 3 22 11 20 17 3 4 15 8 8 26 25 27 14 24 13 31 10 40 21 34 37 16 35 26 38 37 21 15 31 25 23 27 45 19 56 52 24 23 43 36 22 49 35 41 32 52 61 56 47 50 42 72 69 69 63 48 33 79 42 39 50 53 44 68 63 87 88 88 49 38 58 43 18 62 55 75 39 84 55 71 84 96...
output:
87265428 865359809 148327093 136140816 484258955 60120768 556012702 104049494 364602462 792792536 911720400 189345432 471503359 94775099 89140870 109517796 137483052 450767960 780387000 657040118 696995820 575082934 96175124 621335972 629753557 531040277 487337146 559273507 843172395 908341509 91271...
result:
ok all correct
Test #66:
score: 30
Accepted
time: 1507ms
memory: 64436kb
input:
780000 1 2 1 4 4 3 2 8 7 10 9 12 7 6 10 5 3 6 8 12 14 5 18 21 16 17 15 17 20 26 29 31 9 20 15 31 34 23 34 26 13 35 27 11 30 30 27 18 46 42 32 22 23 24 37 35 38 24 22 58 42 44 19 47 49 13 37 46 11 55 64 48 51 60 40 54 75 78 58 63 64 41 66 76 77 65 63 54 49 69 60 77 62 72 59 83 68 98 76 50 57 16 87 41...
output:
234259462 427967239 24858221 685220800 820878610 909754379 561396953 240758520 900192838 429911668 995174805 94473548 569600040 324108297 533519341 521264412 774513909 622957365 223075028 883126656 728215019 603621688 802976417 747241693 863479524 490630917 338986110 574403379 875394705 26650146 335...
result:
ok all correct
Test #67:
score: 30
Accepted
time: 1612ms
memory: 66792kb
input:
840000 1 1 3 3 2 4 5 6 6 5 8 2 12 10 4 7 16 7 14 16 17 9 23 8 15 24 15 12 11 30 27 29 25 23 19 9 21 34 14 10 27 41 32 31 45 19 17 20 24 20 26 48 21 51 26 44 57 36 41 46 30 31 50 33 35 18 18 55 53 42 69 33 60 46 58 61 57 51 68 34 13 22 58 52 39 75 32 84 53 61 64 67 85 54 22 63 89 98 54 40 25 40 60 72...
output:
987197784 342456680 319823997 431926075 866411343 443551775 373086547 220232702 237671602 863991970 197952355 177132547 637579006 475284219 30633113 907318739 417012204 210861099 396733928 501544963 539961237 534945009 695353381 899608709 943147778 736515614 291604809 892740753 631496892 358900890 4...
result:
ok all correct
Test #68:
score: 30
Accepted
time: 1932ms
memory: 74164kb
input:
1000000 1 2 1 3 5 6 2 6 9 7 4 5 4 13 7 8 14 10 9 13 3 22 10 8 25 14 19 20 27 16 18 28 15 20 23 32 26 19 28 11 35 37 24 25 11 35 37 23 46 31 51 45 48 12 47 16 24 36 49 40 60 12 38 22 47 63 62 27 66 60 43 65 62 33 75 41 64 68 29 69 18 30 75 63 85 40 56 86 59 77 51 72 91 31 77 56 38 61 50 99 57 80 55 5...
output:
989758826 392422866 207860708 905829009 642358070 424613204 728743757 313003726 190170136 595367701 117581599 589819381 992585502 290877247 955744494 98657684 27097502 522025243 116146660 850174377 263392388 270426742 473854645 463113359 900032196 645557621 564993634 86610697 302318274 218742784 625...
result:
ok all correct
Test #69:
score: 30
Accepted
time: 1910ms
memory: 74104kb
input:
1000000 1 2 1 2 3 6 4 5 3 9 6 12 12 11 10 16 16 4 19 10 5 8 21 13 11 19 18 14 21 8 17 20 29 17 24 34 27 15 28 18 7 41 24 39 45 14 23 26 37 23 13 7 44 30 46 40 37 35 40 47 44 56 34 22 26 48 29 50 22 31 61 60 63 36 38 41 77 78 67 53 51 58 72 27 66 85 31 69 52 76 86 88 9 72 89 91 39 32 96 69 99 60 67 8...
output:
939691576 270087967 398551701 460750962 320278285 122589796 422807899 50902446 879588248 703642426 529777004 320137444 853273231 476849438 731759413 700413620 609060292 107515742 617554628 526359280 901927256 527856879 435355989 819965641 308106130 72818288 886447397 704167120 314358236 764502424 24...
result:
ok all correct
Test #70:
score: 30
Accepted
time: 1946ms
memory: 74160kb
input:
1000000 1 2 1 2 5 4 4 6 9 3 6 11 12 7 10 11 16 7 16 8 12 14 17 10 24 14 15 17 5 15 25 30 27 33 29 18 24 37 20 20 25 35 39 13 44 18 38 48 42 8 40 41 41 22 26 33 37 53 57 28 38 9 13 52 63 58 45 58 43 56 39 53 66 35 29 60 26 64 56 19 3 72 75 51 34 49 75 72 81 46 70 77 50 85 83 92 50 78 48 57 81 31 87 5...
output:
383876223 87291142 697610990 893654648 99298212 482017003 266553532 875966899 354573256 124295901 307087273 122001136 654284825 693472283 109217790 613732967 488047846 792183331 740795465 429164181 596655572 59192527 223841642 72951800 635181431 955643289 495630080 709217422 132967405 407166123 1318...
result:
ok all correct
Test #71:
score: 30
Accepted
time: 1951ms
memory: 74096kb
input:
1000000 1 1 3 2 3 2 4 7 5 10 10 6 4 11 5 8 17 17 9 18 12 16 21 24 9 8 22 19 14 11 27 24 26 31 20 31 15 38 32 36 32 14 39 35 42 40 12 44 41 36 6 43 40 27 35 45 15 57 16 29 52 37 46 28 23 56 50 67 49 7 21 71 44 70 58 29 58 37 19 42 66 50 20 18 54 86 84 45 22 64 23 43 82 79 13 77 97 46 64 100 55 55 13 ...
output:
582349369 473327294 459477094 449187099 4208838 454373588 721173656 795320261 757619240 334800448 756311332 563915859 360044024 279601093 15619971 745802699 104339322 467854613 981160979 190213874 712716512 809869630 381167195 170529655 487888563 551633941 522725924 378411543 686011249 944643034 426...
result:
ok all correct
Test #72:
score: 30
Accepted
time: 1946ms
memory: 73988kb
input:
1000000 1 1 2 2 5 6 3 4 9 9 7 12 10 7 12 5 16 18 17 11 6 8 17 24 10 26 3 21 28 29 23 28 4 16 13 31 27 29 24 11 27 19 21 33 40 46 26 13 23 31 35 44 37 52 34 54 33 46 42 30 51 48 57 52 34 35 20 43 45 14 20 53 72 53 40 30 15 41 56 66 8 57 14 38 84 80 41 78 58 75 69 90 58 36 93 61 78 81 45 87 95 80 49 2...
output:
553157904 602750160 249802084 989864943 51260138 270291998 500415106 152375685 393408657 495532630 343990114 365426907 132914255 415012218 975083327 518052793 995661124 587172808 78983230 984900044 280725837 926841842 629092240 780599718 214472739 174846700 673411652 356694849 830892678 745465027 83...
result:
ok all correct
Test #73:
score: 30
Accepted
time: 1950ms
memory: 74164kb
input:
1000000 1 1 3 2 4 4 7 5 5 9 2 7 3 9 15 14 16 8 17 19 21 20 10 20 8 16 21 22 26 28 18 19 11 32 30 34 24 35 26 35 32 39 38 38 25 15 14 46 17 41 46 23 34 48 11 49 54 30 39 44 27 55 12 36 18 24 61 57 45 62 23 59 47 48 69 50 12 70 36 71 73 57 72 80 50 53 52 78 77 27 59 85 66 53 80 76 51 42 85 13 22 29 45...
output:
930837522 874242280 779159954 230178465 358135420 435108819 126453091 971820094 899871140 170780424 410941701 88218777 520324844 753276415 861284468 297523687 515131203 339155469 963228706 502887458 647308287 819505193 945024153 590218863 283859745 742878093 135034305 831378737 861880079 475845937 9...
result:
ok all correct
Test #74:
score: 30
Accepted
time: 1910ms
memory: 74104kb
input:
1000000 1 2 2 1 5 4 6 7 9 8 10 10 6 14 4 5 12 16 15 19 14 7 18 20 18 13 22 11 28 22 27 26 21 33 25 29 13 19 17 38 35 29 36 24 35 42 44 36 11 41 42 23 34 40 55 39 41 3 40 15 24 60 31 51 12 38 51 52 39 27 58 47 53 53 74 31 58 73 60 68 25 43 63 66 55 37 76 65 70 80 61 75 87 61 73 90 77 83 16 32 47 102 ...
output:
700645453 307681413 389410778 807546743 908262184 631463146 413517827 378315557 159211696 429522633 466475068 410844207 286852143 688471134 138236704 495031002 209202855 356519399 163297609 974027138 746606004 651220283 403777282 243834590 494626207 63193487 872446106 705367194 634393016 987924424 3...
result:
ok all correct
Test #75:
score: 30
Accepted
time: 1892ms
memory: 74092kb
input:
1000000 1 2 2 4 1 6 6 7 3 7 3 12 4 13 5 5 15 15 18 19 18 16 21 20 8 26 23 25 25 10 22 22 27 11 19 8 10 26 29 37 32 16 33 29 21 36 32 20 30 27 45 37 24 52 23 50 38 39 33 52 55 60 31 40 61 47 38 44 14 61 48 54 43 72 70 41 73 12 79 69 49 17 13 30 51 77 17 11 58 80 91 69 35 34 71 34 54 83 74 75 62 57 67...
output:
170652372 437372204 877740954 306078560 168986759 417729276 829887323 211863573 726341898 306127020 288648294 351545406 735172866 35277771 289965197 690220310 566286466 118499866 38982936 496853144 642247065 978868341 338192866 454306969 729583333 127852713 916119868 272173867 338857258 169632874 19...
result:
ok all correct
Test #76:
score: 30
Accepted
time: 1922ms
memory: 74164kb
input:
1000000 1 2 3 3 2 4 6 7 7 8 6 1 13 5 9 11 8 11 16 15 9 19 21 19 14 21 16 12 17 22 30 32 15 22 33 14 13 20 26 18 10 42 36 34 4 27 27 29 26 45 50 50 25 46 53 24 24 41 54 10 20 18 33 44 23 36 5 63 32 65 70 39 52 45 57 58 58 41 75 51 47 67 57 31 25 29 38 81 71 61 53 65 55 61 17 70 73 77 71 94 87 62 64 8...
output:
743666168 187563892 611344118 215149766 198953410 200503702 405692720 684390242 340940837 93509131 715932581 659131190 383524706 628193586 393175754 244347980 131376137 226995034 963112455 488742395 834774230 430512463 908921446 837945594 679472220 349245334 815440200 699624112 249011494 523541709 8...
result:
ok all correct
Test #77:
score: 30
Accepted
time: 1941ms
memory: 74164kb
input:
1000000 1 1 2 3 3 2 6 5 8 4 9 9 5 13 8 14 6 16 13 16 10 21 17 24 23 25 24 20 20 4 17 31 23 31 26 29 22 27 10 39 18 11 34 26 33 35 32 46 7 12 21 22 39 25 38 18 32 42 44 46 7 48 15 63 62 12 59 57 49 43 52 14 53 37 72 57 49 66 43 55 67 51 41 44 80 55 37 61 88 70 52 89 40 40 80 73 63 75 67 75 65 93 77 7...
output:
5682824 500178271 930219512 325777491 526252587 364660630 715796977 661664179 825446483 353517059 587872133 482106145 145219684 319403134 75195296 985522907 589442488 110682554 19698576 816469516 115710286 144291761 28507260 426911102 130161060 218726919 822424268 987039229 542593635 267191025 41349...
result:
ok all correct
Test #78:
score: 30
Accepted
time: 1448ms
memory: 152220kb
input:
1000000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...
output:
178233829 766686767 281747303 687871177 936825299 404213876 322782339 652280006 307711708 367017646 359596735 531355648 717716814 13180532 313800835 20037394 735551888 568161516 684894649 644080970 924759754 667412845 993082727 814742884 292619948 415884347 496353547 824973183 65461822 837644555 278...
result:
ok all correct
Subtask #4:
score: 0
Wrong Answer
Test #79:
score: 0
Wrong Answer
time: 146ms
memory: 33188kb
input:
100000 1 1 3 4 5 6 7 8 9 10 9 12 13 14 15 14 12 8 19 20 21 20 19 24 24 26 26 28 29 26 31 26 33 34 26 36 36 38 39 40 41 36 4 44 45 46 47 47 49 44 51 52 53 54 53 52 57 58 59 60 61 61 63 61 65 66 67 67 69 70 69 72 59 74 74 76 76 78 79 78 81 82 83 84 85 82 87 87 58 90 91 92 93 91 95 51 97 98 99 99 101 1...
output:
736079324 657978221 595430141 440220745 849109682 291128321 127967213 916169355 473854641 262093747 675127246 942295678 513318668 117018684 40656034 777510525 834413159 623705754 678773095 899648692 551558006 117893600 891440155 904413463 37014957 664482432 944982499 639073421 725783142 900552661 26...
result:
wrong output format Extra information in the output file