QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#641255 | #9165. Petrol stations | not_amir | 55 | 2821ms | 1586824kb | C++14 | 4.4kb | 2024-10-14 19:28:48 | 2024-10-14 19:28:51 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define INF 1e15
struct Vertex {
Vertex* l, * r;
ll sum;
Vertex(ll val) : l(nullptr), r(nullptr), sum(val) {}
Vertex(Vertex* l, Vertex* r) : l(l), r(r), sum(0) {
if (l) sum += l->sum;
if (r) sum += r->sum;
}
void extend(){
if(!l)
l = new Vertex(0);
if(!r)
r = new Vertex(0);
}
};
ll get_sum(Vertex* v, ll tl, ll tr, ll l, ll r) {
if (l + 1 > r)
return 0;
if (l == tl && tr == r)
return v->sum;
if(v->l == nullptr)
return 0;
ll tm = (tl + tr) / 2;
return get_sum(v->l, tl, tm, l, min(r, tm))
+ get_sum(v->r, tm, tr, max(l, tm), r);
}
void update(Vertex* v, ll tl, ll tr, ll pos, ll new_val) {
if (tl + 1 == tr){
v->sum += new_val;
return;
}
v->extend();
ll tm = (tl + tr) / 2;
if (pos < tm)
update(v->l, tl, tm, pos, new_val);
else
update(v->r, tm, tr, pos, new_val);
v->sum = v->l->sum + v->r->sum;
}
vector<vector<pii>> G;
vector<bool> is_removed;
vector<int> subsize;
int get_subtree_size(int v, int p = -1) {
subsize[v] = 1;
for (auto [u, w] : G[v]) {
if (u == p || is_removed[u]) { continue; }
subsize[v] += get_subtree_size(u, v);
}
return subsize[v];
}
int get_centroid(int v, int S, int p = -1) {
for (auto [u, w] : G[v]) {
if (u == p || is_removed[u]) { continue; }
if (subsize[u] * 2 > S) {
return get_centroid(u, S, v);
}
}
return v;
}
int k;
vector<ll> ans, res, jump, jumpw, par, parw, depth;
vector<Vertex*> st;
void dfs1(Vertex* stt, int v, int p, int d, int child, int S) {
depth[v] = d;
res[v] = 0;
if(p != -1) {
if(depth[jump[p]] - depth[p] == depth[jump[jump[p]]] - depth[jump[p]])
jump[v] = jump[jump[p]], jumpw[v] = jumpw[jump[p]] + jumpw[p] + parw[v];
else
jump[v] = p, jumpw[v] = parw[v];
}
for(auto [u, w] : G[v]) {
if(u == p || is_removed[u])
continue;
par[u] = v, parw[u] = w;
if(p == -1)
st[u] = new Vertex(0);
dfs1(stt, u, v, d + 1, p==-1?u:child, S);
}
if(p != -1) {
int a = v, s = 0;
ans[v] += res[v] * (S - subsize[child]);
while(jump[a] != a && s + parw[a] <= k) {
if(jumpw[a] + s <= k)
s += jumpw[a], a = jump[a];
else
s += parw[a], a = par[a];
}
if(jump[a] == a) {
update(stt, 0, INF, k - s, res[v] + 1);
update(st[child], 0, INF, k - s, res[v] + 1);
}
else
res[a] += res[v] + 1;
}
}
void dfs2(Vertex* stt, int v, int p, int s, int child) {
for(auto [u, w] : G[v]) {
if(u == p || is_removed[u])
continue;
if(p == -1)
child = u;
int refuel = get_sum(stt, 0, INF, s, s + w);
refuel -= get_sum(st[child], 0, INF, s, s + w);
ans[v] += refuel * subsize[u];
update(stt, 0, INF, s + k, refuel);
dfs2(stt, u, v, s + w, child);
update(stt, 0, INF, s + k, -refuel);
}
}
void centroid_decomp(int v = 0) {
int centroid = get_centroid(v, get_subtree_size(v));
Vertex* stt = new Vertex(0);
jump[centroid] = centroid;
jumpw[centroid] = 0;
dfs1(stt, centroid, -1, 0, 0, get_subtree_size(centroid));
update(stt, 0, INF, k, 1);
dfs2(stt, centroid, -1, 0, 0);
is_removed[centroid] = true;
for (auto [u, w] : G[centroid]) {
if (is_removed[u]) { continue; }
centroid_decomp(u);
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n >> k;
G.resize(n);
is_removed.resize(n);
subsize.resize(n);
par.resize(n);
parw.resize(n);
jump.resize(n);
jumpw.resize(n);
ans.resize(n);
res.resize(n);
depth.resize(n);
st.resize(n);
for(int i = 0; i < n - 1; i++) {
int u, v, l;
cin >> u >> v >> l;
G[u].push_back({v, l});
G[v].push_back({u, l});
}
centroid_decomp();
for(int i = 0; i < n; i++)
cout << ans[i] << '\n';
}
詳細信息
Subtask #1:
score: 18
Accepted
Test #1:
score: 18
Accepted
time: 17ms
memory: 10792kb
input:
750 918 159 63 18 573 310 105 135 400 57 618 27 113 41 265 24 99 576 61 242 85 109 490 88 0 626 721 0 407 446 0 78 644 124 346 198 17 541 504 147 543 423 24 302 450 25 397 344 80 129 607 76 474 59 140 30 10 29 375 260 1 404 81 0 658 695 153 450 100 92 532 249 10 597 151 133 739 714 0 212 345 85 558 ...
output:
0 96 45 94 0 0 0 0 0 146 0 0 0 20 32 0 0 88 18 0 2 0 0 0 0 0 43 48 36 10 13 18 0 42 158 0 35 79 17 0 0 0 0 36 0 84 0 8 0 0 20 38 6 0 0 0 0 52 12 4 0 0 12 0 0 0 198 0 30 16 13 45 0 46 0 0 18 44 0 12 0 105 0 0 0 28 75 0 0 12 48 0 0 66 0 0 0 35 0 18 65 42 52 0 0 140 81 114 0 0 27 60 30 76 0 43 0 0 75 2...
result:
ok 750 lines
Test #2:
score: 18
Accepted
time: 21ms
memory: 10480kb
input:
967 334 285 176 1 648 431 1 493 893 2 261 165 1 158 512 2 675 881 1 232 200 2 452 380 2 961 35 1 831 131 1 424 458 1 807 835 2 154 855 1 524 513 2 448 27 1 82 331 2 454 190 2 469 210 2 15 445 2 860 1 2 901 47 0 496 572 2 227 122 1 141 223 2 214 924 1 4 381 2 394 703 2 859 611 2 63 688 1 197 674 1 59...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 967 lines
Test #3:
score: 18
Accepted
time: 10ms
memory: 11160kb
input:
1000 963 408 385 876 23 519 951 649 232 605 821 385 792 194 221 882 18 984 910 115 40 155 558 973 126 876 633 625 795 781 727 923 248 397 120 632 320 392 531 185 527 973 508 986 457 918 74 339 432 259 385 243 93 973 961 640 385 531 614 325 839 823 936 691 159 240 184 40 625 891 692 385 331 196 140 1...
output:
0 0 482612 0 912 0 0 766 0 0 0 24 989 0 493138 0 0 0 0 0 1996 979 890 1996 0 0 0 0 1996 0 0 0 0 0 0 0 254507 0 997 2 450646 0 244035 727 0 2043 0 0 0 0 0 0 0 0 0 0 0 0 19929 1996 0 0 0 0 997 0 0 0 0 1994 0 2 0 0 0 0 0 0 0 0 1962 0 0 0 0 3990 493900 0 0 0 0 0 0 3988 0 940 0 0 0 0 0 1996 0 2366 0 1989...
result:
ok 1000 lines
Test #4:
score: 18
Accepted
time: 25ms
memory: 13996kb
input:
1000 396 412 257 190 290 965 25 399 938 174 980 459 117 874 575 124 386 912 40 666 164 124 97 680 49 589 442 197 451 649 109 893 648 134 975 733 198 121 966 63 346 775 94 381 246 169 507 319 159 333 287 101 127 682 118 48 784 34 708 170 0 142 723 148 836 766 185 277 711 188 512 974 68 658 404 136 95...
output:
215160 138947 196491 47632 103775 128657 26093 195362 2694 0 234548 3952 120001 175260 489004 1998 9576 0 97602 2334 86553 18629 5792 57931 251700 122745 0 33115 227964 190106 203868 102592 1290 440 0 9054 79 1620 2166 496039 28992 169701 102833 9701 218081 1463 999 433548 7728 4935 882 817 87200 36...
result:
ok 1000 lines
Test #5:
score: 18
Accepted
time: 19ms
memory: 10052kb
input:
1000 333 896 853 0 28 756 0 658 183 0 488 17 0 475 283 0 587 6 0 979 607 0 918 95 0 247 848 0 799 23 0 815 685 0 580 58 0 724 192 0 398 209 0 140 526 0 966 397 0 595 468 0 827 19 0 866 666 0 62 329 0 599 799 0 13 972 0 526 481 0 593 170 0 312 809 0 106 584 0 670 945 0 602 62 0 765 731 0 756 935 0 33...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 1000 lines
Test #6:
score: 18
Accepted
time: 0ms
memory: 3644kb
input:
2 31 0 1 31
output:
0 0
result:
ok 2 lines
Test #7:
score: 18
Accepted
time: 17ms
memory: 11576kb
input:
1000 847 24 298 474 208 141 485 789 89 60 1 809 437 936 670 449 254 938 364 796 766 340 114 453 609 656 474 374 522 795 378 80 518 279 220 648 619 643 924 191 267 499 288 483 382 643 270 949 816 284 146 481 861 706 686 103 642 631 626 136 294 642 687 407 30 253 603 149 923 502 396 637 762 0 715 67 5...
output:
16 1080 1966 5980 1856 0 5980 0 0 0 0 0 0 0 0 1992 4702 0 0 968 1996 0 0 0 0 1996 0 0 58 0 61453 0 9874 64 3990 41198 11458 13818 1952 59099 17820 1 0 0 0 0 50596 0 0 0 0 0 0 37219 1215 0 7960 1996 175610 3990 0 31526 21 3988 1996 0 0 8953 11926 0 6980 1302 0 23237 0 0 0 0 0 0 0 1996 0 0 0 0 1996 19...
result:
ok 1000 lines
Test #8:
score: 18
Accepted
time: 12ms
memory: 11656kb
input:
1000 767 476 799 361 271 239 215 447 941 269 219 664 600 904 6 264 154 82 98 711 836 437 7 75 381 922 557 741 61 413 505 87 839 548 389 87 504 634 81 393 428 214 8 812 243 511 492 17 761 765 29 129 617 879 355 251 267 554 8 21 380 505 443 235 427 97 416 678 666 313 342 93 397 145 614 179 991 113 322...
output:
1017 997 3988 1996 0 0 2 0 0 971 1996 1996 0 2983 0 1996 19530 13742 0 0 13888 5015 0 997 0 0 0 0 0 996 0 2 0 78 1996 0 0 0 7948 1 6 0 0 1996 3 0 0 0 0 997 1996 0 0 75588 51097 1996 3988 0 0 0 40284 91174 1996 0 0 0 0 26 11 5976 112650 1996 1996 0 0 12837 0 31468 0 0 0 2967 159 0 9940 0 0 40883 1000...
result:
ok 1000 lines
Test #9:
score: 18
Accepted
time: 14ms
memory: 11836kb
input:
1000 1000 574 351 479 444 634 559 531 70 113 180 828 194 123 521 790 295 646 79 539 462 598 362 736 541 673 23 185 363 906 34 859 258 777 921 726 216 504 760 725 787 64 629 314 245 98 412 361 306 636 841 287 40 818 247 674 267 783 838 903 50 175 509 177 96 46 8 56 775 113 117 762 45 511 718 69 527 4...
output:
17839 4922 3988 0 0 0 0 0 0 0 1996 1996 0 0 0 0 0 2938 958 0 0 0 0 0 0 33 0 0 1097 50763 11918 0 0 4931 4942 0 0 0 1996 0 0 3988 1996 26430 0 3 997 15 0 0 0 61525 11 2971 1974 7960 1996 7783 0 0 0 11 17 4927 3994 0 0 3957 2968 8947 986 0 0 0 0 0 0 0 0 0 5976 0 2985 0 0 0 5974 6879 40013 45110 0 1872...
result:
ok 1000 lines
Test #10:
score: 18
Accepted
time: 17ms
memory: 11720kb
input:
1000 1000 680 881 340 73 368 929 303 239 219 861 605 561 243 667 531 357 96 797 561 264 569 267 59 169 146 639 660 161 931 423 209 525 524 406 689 275 544 504 153 296 406 735 245 144 706 806 165 557 444 234 477 614 437 682 503 628 205 539 636 135 219 202 863 938 665 376 983 452 512 841 241 924 664 9...
output:
88 3990 9954 0 0 1996 8458 0 0 5974 0 0 0 0 9952 2 9954 0 1996 6915 978 1996 989 0 31481 1996 157 1996 0 0 988 1996 0 17140 7960 0 1919 928 268 0 0 0 0 0 0 0 0 14876 0 1996 43 59135 983 0 0 0 0 0 1996 76302 0 0 4592 5976 2 0 0 0 0 43971 990 0 0 0 0 0 3972 1996 0 0 1915 0 1994 1996 997 0 0 0 138 0 0 ...
result:
ok 1000 lines
Test #11:
score: 18
Accepted
time: 17ms
memory: 11604kb
input:
1000 1000 164 378 963 934 141 358 866 915 598 341 220 55 598 757 654 149 668 202 215 502 818 439 618 693 55 873 554 927 190 748 976 487 779 402 411 89 732 990 641 557 432 734 515 574 638 491 907 217 217 556 332 483 614 81 25 106 975 245 635 724 902 208 219 211 722 209 390 738 587 748 602 338 216 14 ...
output:
1996 0 1147 1996 18739 2976 0 0 0 0 0 1995 3990 0 13587 0 0 5982 1 0 997 0 1996 1996 0 0 0 0 2953 1994 1996 16 664 0 0 0 0 1996 30 3986 0 6932 3988 173897 1358 0 8907 0 0 0 1996 0 0 0 1996 1996 0 0 11938 1163 136386 1996 0 411 0 0 0 0 7903 29433 9084 3988 0 331 9940 23743 1996 0 0 3957 0 0 0 991 0 0...
result:
ok 1000 lines
Test #12:
score: 18
Accepted
time: 8ms
memory: 10088kb
input:
1000 537 276 155 470 533 155 391 175 155 343 553 155 270 24 155 447 614 155 239 927 155 314 899 155 188 398 155 344 18 155 501 937 155 413 671 155 184 808 155 418 200 155 501 491 155 374 717 155 245 692 155 476 313 155 455 0 155 232 702 155 275 544 155 498 66 155 237 245 155 233 865 155 188 574 155 ...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 1000 lines
Subtask #2:
score: 8
Accepted
Test #13:
score: 8
Accepted
time: 0ms
memory: 3720kb
input:
2 1 0 1 1
output:
0 0
result:
ok 2 lines
Test #14:
score: 8
Accepted
time: 2290ms
memory: 481180kb
input:
70000 1 50913 18377 1 33894 11911 1 61940 7863 1 61602 33470 1 26341 35575 1 30813 50301 1 2994 67214 1 38527 61714 1 37381 3396 1 43274 14867 1 59352 12066 1 68877 40750 1 44756 43671 1 57921 17977 1 10879 47719 1 26878 13556 1 27329 23697 1 45109 11513 1 21307 12312 1 27202 27807 1 7250 14810 1 27...
output:
2128187656 1918647796 1539693556 1198079316 2227641388 537651676 1566795636 1713609688 462341800 403913520 1372196836 2449371376 2448661176 226085260 2289814488 2374543080 1462250988 2446901740 2288343736 788226400 1802397916 2219170356 2367201616 130103388 1927347880 2324936140 630135880 1489088716...
result:
ok 70000 lines
Subtask #3:
score: 0
Wrong Answer
Dependency #2:
100%
Accepted
Test #15:
score: 0
Wrong Answer
time: 2821ms
memory: 1586824kb
input:
70000 517272873 57335 18148 62837135 28239 56484 253183094 23004 59130 129215861 558 17489 52424960 55884 27928 150784869 35390 18538 216587635 31618 4121 168195328 49409 13677 142007449 61001 39616 40892641 67336 21612 185484704 34486 9556 246576628 4933 23924 201603991 57035 5529 29829254 38668 21...
output:
2421406845 212731760 -2318971726 1311179637 1712103614 -1335709821 2259503119 4131750920 1712823141 -1097015519 1351707704 2042710577 1643349620 -46141888 -572969531 945102804 914764383 -6716978 -3595432392 2616667841 -1972650919 187282847 2328552134 3087482678 1933894426 441029632 -866208895 197267...
result:
wrong answer 1st lines differ - expected: '450859', found: '2421406845'
Subtask #4:
score: 12
Accepted
Test #17:
score: 12
Accepted
time: 2019ms
memory: 469600kb
input:
69973 4 44281 27162 1 15299 61302 1 19250 66379 1 45970 65938 1 23683 4445 2 62232 40589 1 37028 58991 2 58769 32024 0 41860 69672 2 14687 10058 2 7874 6780 2 60579 37047 2 739 4096 2 53137 22114 2 35060 21464 0 42597 11591 2 68051 23473 2 61458 35690 2 38719 6601 2 57406 26025 1 38192 41521 0 47941...
output:
769608 34960 1162375 626228 2 419792 493364 419754 1817301 15 838740 515085 769584 0 0 659707 915948 209895 208656 69972 1251384 277968 1231290 517455 825285 560784 417892 349256 489692 979020 139930 139938 209902 1518040 1146693 287344 403088 1 279861 209896 699603 732904 723193 769575 140252 10391...
result:
ok 69973 lines
Test #18:
score: 12
Accepted
time: 2164ms
memory: 510728kb
input:
70000 6 12580 20937 2 31244 33335 1 62095 66946 0 2558 64306 2 38762 111 2 64974 13699 1 43807 54819 1 20265 66474 3 56426 21940 0 17487 26140 2 11417 36996 2 640 46428 0 45138 54845 1 50554 13418 3 66554 43463 0 54345 51628 2 50263 55697 1 11292 25053 1 29900 10115 2 54500 17279 1 54173 57033 3 608...
output:
95678 275287413 81937227 47960445 176569 64768 441678666 980093268 490395803 549945 2442380991 572294079 0 1210579335 0 23682745 0 901519414 203750140 923453439 104544 293252454 0 514830 915152602 1023643716 710424 0 1138664466 696145940 2080089300 0 0 589624 1220178831 51949 2340422751 193419 90424...
result:
ok 70000 lines
Test #19:
score: 12
Accepted
time: 2100ms
memory: 457896kb
input:
70000 10 45546 20793 0 44801 49720 0 54732 9736 0 64375 18647 0 5128 61973 0 43544 39499 0 7553 64059 0 52671 60698 0 3856 66222 0 22937 53710 0 37212 17625 0 4088 60067 0 4594 67707 0 43329 36060 0 16713 10870 0 26623 56853 0 52301 6112 0 4772 42600 0 30359 51840 0 15979 7826 0 18168 47506 0 25681 ...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 70000 lines
Test #20:
score: 12
Accepted
time: 0ms
memory: 3628kb
input:
2 6 0 1 6
output:
0 0
result:
ok 2 lines
Test #21:
score: 12
Accepted
time: 1741ms
memory: 482460kb
input:
70000 10 36906 67900 2 51465 24882 0 65531 32406 0 49018 50640 10 42030 45698 6 69965 51752 0 25375 7403 6 45919 32863 10 10559 50362 9 61538 32462 10 4894 61305 8 12033 10357 2 13580 31068 4 36014 69454 9 58156 22466 10 64024 60212 2 9152 1600 3 16154 3971 7 37873 60499 4 27813 67775 4 34467 20550 ...
output:
0 0 1141061037 69997 0 0 419980 17435495 279988 0 0 0 7973500 0 70179 0 7694762 70276 0 0 0 0 0 559960 0 2659276 0 69925 0 217273336 0 0 0 0 839916 69996 699940 140005 839839 2868360 0 1679688 139996 139996 139992 0 0 70000 1671612030 0 0 1049703 2869077 0 0 419980 2659240 1119845 0 1539768 0 279990...
result:
ok 70000 lines
Test #22:
score: 12
Accepted
time: 1775ms
memory: 482540kb
input:
70000 10 40966 26929 6 15381 7596 3 53090 61576 3 6976 65087 2 33827 1931 10 24176 10778 3 43080 33467 2 48511 56217 5 59872 11525 0 18555 36157 1 16496 55674 5 28719 22937 6 52693 5381 8 36164 21449 3 37134 19737 7 27759 33516 7 30601 40021 1 62084 45831 10 42930 25137 2 26293 21275 9 48210 36338 6...
output:
279988 0 0 56174160 0 0 23323888 0 2099071 0 2659455 419980 139994 559960 139990 0 69993 139992 84379456 0 0 70128 0 1819660 7756014 38765430 0 209987 3358890 4617812 419976 139996 419970 1399520 6715296 0 2 139764 0 979888 0 139996 3638596 244188220 0 0 279990 0 279988 0 209964 209964 0 0 0 139992 ...
result:
ok 70000 lines
Test #23:
score: 12
Accepted
time: 1768ms
memory: 482464kb
input:
70000 10 47111 32841 10 510 5994 10 1362 44478 8 61688 30984 5 30611 58931 7 23371 48692 10 53702 58334 5 45242 64087 9 62520 46584 7 18984 64865 8 19484 69056 6 67745 9899 8 64611 28448 7 28716 36915 4 28330 65755 5 23587 61603 3 2434 30883 6 22277 19653 8 68776 65367 2 6483 42009 10 21878 32298 5 ...
output:
419980 0 979765 0 1679710 139996 419872 139996 699954 0 3569329 0 11462313 3778488 0 559934 1889317 140023 5592560 0 0 0 489930 0 2308713 139996 0 1889620 2659240 1399812 0 139996 0 0 0 1539193 3 0 139996 0 3707927 2659240 0 559929 4056462 0 1049593 0 0 893806 139996 1 139996 279988 349971 0 0 16493...
result:
ok 70000 lines
Subtask #5:
score: 17
Accepted
Dependency #4:
100%
Accepted
Test #24:
score: 17
Accepted
time: 1019ms
memory: 464244kb
input:
70000 7 12257 45873 7 53771 24407 7 67182 59338 2 68981 59097 6 57729 48126 5 1721 59097 2 3199 59097 3 60691 12829 0 58194 66702 5 33633 67496 7 58727 15878 1 17536 52190 3 50970 48111 4 29987 50799 4 13575 50151 3 60967 6663 2 47883 59097 3 6045 45021 4 30432 47041 3 42998 48111 7 30822 48111 3 11...
output:
0 0 0 0 56749 139996 0 0 2273252787 0 0 0 0 0 0 0 0 0 58877 0 139996 0 0 419976 0 0 2225944862 0 2420326158 0 0 0 559960 0 0 0 643497 0 139996 0 0 139996 0 0 0 0 0 0 0 279988 0 17043 0 0 60317 32887 0 0 2264012956 0 0 0 0 0 0 0 0 139996 349939 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 144979 0 0 0 0 0 0 2441897...
result:
ok 70000 lines
Test #25:
score: 17
Accepted
time: 1259ms
memory: 463156kb
input:
70000 7 60987 29710 2 40235 14667 3 49803 36218 0 1256 23603 0 9202 12636 0 67422 31567 1 54648 38680 2 62637 37872 2 10743 6822 6 53418 48397 1 51738 49375 3 19681 19949 3 36445 50369 3 19712 38063 3 26633 52347 0 23152 59256 2 10977 15333 5 65517 1515 5 25199 50076 6 3371 68446 2 10983 59644 2 684...
output:
559942 0 69996 0 0 139996 0 0 0 139996 1119890 0 0 559934 0 0 139996 0 0 0 0 0 69999 279988 419976 0 0 279988 559966 0 1399780 2099472 0 0 0 0 0 0 0 0 0 139983 0 0 0 0 0 0 0 0 0 0 209973 0 559960 0 0 699940 0 0 0 69996 69996 0 279990 21314538 279988 0 0 419956 0 0 0 0 0 0 69997 559960 0 2 1418 13999...
result:
ok 70000 lines
Test #26:
score: 17
Accepted
time: 1318ms
memory: 460620kb
input:
70000 4 29827 12474 3 52717 68608 1 26411 5022 3 66140 68360 2 27054 15938 3 383 51864 4 52370 63324 3 49124 25159 4 42556 47177 1 59874 25843 0 18502 25342 2 7574 23971 4 35758 28101 2 14031 55753 2 50487 50114 4 33386 45120 1 33450 31191 4 695 3466 0 3269 56502 1 67089 56967 0 56892 30196 1 5116 5...
output:
419970 0 0 202 0 0 279984 0 0 280018 139996 349980 139996 0 23 139996 279988 139996 139996 0 559947 209963 0 0 0 0 0 0 0 0 1539806 0 0 0 139996 0 2440548 279988 699954 279988 0 0 2379703 0 0 2309506 0 209979 3987926 0 419976 979648 0 0 0 0 0 0 279988 0 13 0 0 139996 0 0 279988 0 0 139996 139996 0 36...
result:
ok 70000 lines
Test #27:
score: 17
Accepted
time: 1363ms
memory: 471404kb
input:
70000 10 41642 65096 7 14235 28073 6 48132 705 7 23384 33897 0 13953 22709 0 27316 52036 3 26123 8861 10 3391 7044 10 1747 10038 10 8948 54554 8 6958 62827 0 58607 65096 1 28063 67423 3 31692 57358 5 62966 15760 8 66029 36119 0 19762 15328 5 65551 25282 10 66353 19368 5 58541 32650 10 53625 52235 1 ...
output:
139996 279988 0 0 0 1399787 0 0 0 0 0 0 0 0 69996 0 0 0 0 139996 769901 0 0 0 141 2659434 139996 0 0 0 232 0 0 0 32 0 0 0 0 0 0 69997 0 70008 5527464 209942 699954 279986 1189644 839914 0 139974 0 28903966 0 0 0 0 4548535 0 699942 0 101 0 0 0 0 0 0 0 2519482 0 0 0 0 0 0 69992 0 0 139996 9089021 0 0 ...
result:
ok 70000 lines
Test #28:
score: 17
Accepted
time: 1324ms
memory: 471444kb
input:
70000 10 44002 46661 10 16351 40057 10 62342 69569 2 277 38372 1 40658 58988 7 15832 23305 8 39381 63632 8 55316 55953 2 4871 40228 6 57312 52025 0 24200 29040 9 32283 24421 9 65203 10297 10 28846 27662 6 46750 32115 8 55937 947 4 32984 11601 10 57523 29674 5 35949 53510 9 56657 8539 8 43913 29333 4...
output:
0 0 559966 0 0 0 0 1259820 769916 0 279988 0 0 69954 0 0 279978 839920 139996 0 139982 139972 0 0 0 139916 139992 769903 139996 193 70134 1049708 0 0 0 839934 0 0 0 0 0 0 139996 839926 699956 0 0 0 419980 840675 139996 0 69995 0 0 0 0 11812190 0 279980 8 0 0 0 139996 0 0 0 0 0 0 0 945265 0 0 0 13999...
result:
ok 70000 lines
Test #29:
score: 17
Accepted
time: 1358ms
memory: 471564kb
input:
70000 10 11173 32861 3 13926 50906 10 18305 60850 3 13279 836 9 3466 26666 4 67810 66996 8 67739 2252 2 14556 38643 7 68973 45279 0 32154 29076 10 46391 19237 3 10836 54751 1 23291 45139 6 45366 68190 0 41164 61188 3 7519 11337 6 30900 58457 7 10220 41616 2 37816 59990 7 42226 8216 4 45323 64040 4 2...
output:
0 139996 2 0 0 0 139994 0 15575 69993 0 0 0 0 0 0 0 0 0 2325854 0 0 139994 0 0 17191 279988 0 0 0 1539632 141441 0 0 0 2659336 0 0 1119870 139996 489943 279988 0 0 0 139996 559968 0 139974 0 50059 0 0 209737 279988 419978 0 15101910 1259876 559960 0 909802 1679722 0 0 0 0 0 0 0 3 28485088 0 3918 489...
result:
ok 70000 lines
Test #30:
score: 17
Accepted
time: 488ms
memory: 452576kb
input:
70000 3 18748 12670 2 56209 12670 2 4918 12670 1 26713 12670 2 66342 12670 1 35963 12670 3 41257 12670 3 32775 12670 2 623 12670 3 32333 12670 1 15905 12670 1 63177 12670 3 25408 12670 3 44826 12670 2 28656 12670 2 14547 12670 2 68707 12670 1 12229 12670 1 41434 12670 2 58731 12670 3 1018 12670 1 63...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 70000 lines
Subtask #6:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
0%