QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#641255#9165. Petrol stationsnot_amir55 2821ms1586824kbC++144.4kb2024-10-14 19:28:482024-10-14 19:28:51

Judging History

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

  • [2024-10-14 19:28:51]
  • 评测
  • 测评结果:55
  • 用时:2821ms
  • 内存:1586824kb
  • [2024-10-14 19:28:48]
  • 提交

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%