QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#110060#2002. Racethenymphsofdelphi#100 ✓222ms146984kbC++202.9kb2023-05-31 13:21:552024-05-31 13:52:19

Judging History

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

  • [2024-05-31 13:52:19]
  • 评测
  • 测评结果:100
  • 用时:222ms
  • 内存:146984kb
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-31 13:21:55]
  • 提交

answer

#include "race.h"

#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (auto i = (l); i < (r); i++)
#define ForE(i, l, r) for (auto i = (l); i <= (r); i++)
#define FordE(i, l, r) for (auto i = (l); i >= (r); i--)
#define Fora(v, a) for (auto v: (a))
#define bend(a) (a).begin(), (a).end()
#define isz(a) ((signed)(a).size())

using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pii>;
using vvi = vector <vi>;

const int N = 2e5 + 5;

int k;
vpii adj[N];
int h[N];
ll d[N];
int sz[N];

void dfs_sz(int u, int p = -1){
    sz[u] = 1;
    for (auto [v, w]: adj[u]){
        if (v == p){
            continue;
        }
        h[v] = h[u] + 1;
        d[v] = d[u] + w;
        dfs_sz(v, u);
        sz[u] += sz[v];
    }
}

int ans = INT_MAX;
gp_hash_table <ll, int> mpp[N];

void dfs_mergeset(int u, int p = -1){
    int heavy = -1;
    for (auto [v, w]: adj[u]){
        if (v == p){
            continue;
        }
        dfs_mergeset(v, u);
        if (heavy == -1 or sz[heavy] < sz[v]){
            heavy = v;
        }
    }
    if (heavy != -1){
        mpp[u].swap(mpp[heavy]);
    }
    for (auto [v, w]: adj[u]){
        if (v == p or v == heavy){
            continue;
        }
        for (auto [dpath, hpath]: mpp[v]){
            auto itr = mpp[u].find(k + 2 * d[u] - dpath);
            if (itr != mpp[u].end()){
                ans = min(ans, hpath + itr->se - 2 * h[u]);
            }
        }
        for (auto [dpath, hpath]: mpp[v]){
            auto itr = mpp[u].find(dpath);
            if (itr != mpp[u].end()){
                itr->se = min(itr->se, hpath);
            }
            else{
                mpp[u][dpath] = hpath;
            }
        }
    }
    {
        auto itr = mpp[u].find(k + d[u]);
        if (itr != mpp[u].end()){
            ans = min(ans, itr->se - h[u]);
        }
        mpp[u][d[u]] = h[u];
    }
}

int best_path(int n, int _k, int edge[][2], int weight[]){
    k = _k;
    For(i, 0, n - 1){
        auto [u, v, w] = tuple{edge[i][0], edge[i][1], weight[i]};
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }
    dfs_sz(0);
    dfs_mergeset(0);
    if (ans == INT_MAX){
        ans = -1;
    }
    return ans;
}

/*
==================================================+
INPUT                                             |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
OUTPUT                                            |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
*/

詳細信息

Subtask #1:

score: 9
Accepted

Test #1:

score: 9
Accepted
time: 7ms
memory: 67236kb

input:

100 50
0 1 1
1 2 2
2 3 2
3 4 1
4 5 2
5 6 1
6 7 1
7 8 1
8 9 1
9 10 2
10 11 2
11 12 2
12 13 1
13 14 1
14 15 1
15 16 2
16 17 1
17 18 2
18 19 1
19 20 1
20 21 1
21 22 2
22 23 2
23 24 2
24 25 2
25 26 1
26 27 2
27 28 2
28 29 2
29 30 2
30 31 2
31 32 1
32 33 1
33 34 2
34 35 2
35 36 1
36 37 1
37 38 1
38 39 1
...

output:

Correct.

Test #2:

score: 0
Accepted
time: 7ms
memory: 68992kb

input:

100 100
0 1 39
1 2 26
2 3 27
3 4 43
4 5 18
5 6 25
6 7 29
7 8 32
8 9 32
9 10 9
10 11 10
11 12 1
12 13 38
13 14 26
14 15 12
15 16 11
16 17 19
17 18 34
18 19 19
19 20 8
20 21 42
21 22 15
22 23 21
23 24 13
24 25 24
25 26 18
26 27 45
27 28 5
28 29 12
29 30 11
30 31 2
31 32 31
32 33 31
33 34 50
34 35 7
35...

output:

Correct.

Test #3:

score: 0
Accepted
time: 23ms
memory: 68968kb

input:

100 100
0 1 48
1 2 1
2 3 42
3 4 37
4 5 29
5 6 35
6 7 49
7 8 26
8 9 11
9 10 4
10 11 3
11 12 46
12 13 42
13 14 35
14 15 42
15 16 16
16 17 9
17 18 49
18 19 4
19 20 15
20 21 40
21 22 0
22 23 21
23 24 40
24 25 49
25 26 6
26 27 2
27 28 19
28 29 35
29 30 39
30 31 15
31 32 16
32 33 40
33 34 44
34 35 36
35 3...

output:

Correct.

Test #4:

score: 0
Accepted
time: 11ms
memory: 68980kb

input:

100 100
0 1 27
1 2 28
2 3 0
3 4 18
4 5 40
5 6 12
6 7 6
7 8 29
8 9 37
9 10 39
10 11 6
11 12 32
12 13 34
13 14 30
14 15 39
15 16 39
16 17 46
17 18 23
18 19 43
19 20 47
20 21 46
21 22 34
22 23 31
23 24 28
24 25 12
25 26 13
26 27 19
27 28 25
28 29 44
29 30 25
30 31 9
31 32 29
32 33 11
33 34 45
34 35 30
...

output:

Correct.

Test #5:

score: 0
Accepted
time: 7ms
memory: 69012kb

input:

100 100
0 1 1
1 2 2
2 3 2
3 4 3
4 5 3
5 6 3
6 7 0
7 8 3
8 9 3
9 10 3
10 11 0
11 12 2
12 13 2
13 14 3
14 15 2
15 16 3
16 17 2
17 18 1
18 19 0
19 20 1
20 21 2
21 22 2
22 23 2
23 24 1
24 25 1
25 26 3
26 27 1
27 28 3
28 29 2
29 30 3
30 31 1
31 32 0
32 33 3
33 34 1
34 35 3
35 36 1
36 37 3
37 38 3
38 39 1...

output:

Correct.

Test #6:

score: 0
Accepted
time: 17ms
memory: 68980kb

input:

100 100
0 1 4
1 2 3
2 3 5
3 4 0
4 5 5
5 6 4
6 7 2
7 8 1
8 9 5
9 10 5
10 11 3
11 12 1
12 13 3
13 14 4
14 15 3
15 16 1
16 17 4
17 18 1
18 19 5
19 20 0
20 21 1
21 22 1
22 23 5
23 24 1
24 25 4
25 26 5
26 27 5
27 28 2
28 29 4
29 30 0
30 31 0
31 32 4
32 33 3
33 34 5
34 35 2
35 36 5
36 37 4
37 38 5
38 39 4...

output:

Correct.

Test #7:

score: 0
Accepted
time: 19ms
memory: 68972kb

input:

100 100
0 1 2
1 2 0
2 3 1
3 4 0
4 5 0
5 6 0
6 7 2
7 8 1
8 9 2
9 10 0
10 11 2
11 12 0
12 13 0
13 14 1
14 15 1
15 16 2
16 17 2
17 18 1
18 19 2
19 20 2
20 21 1
21 22 2
22 23 0
23 24 0
24 25 2
25 26 1
26 27 0
27 28 2
28 29 1
29 30 2
30 31 2
31 32 1
32 33 0
33 34 1
34 35 0
35 36 2
36 37 0
37 38 2
38 39 0...

output:

Correct.

Test #8:

score: 0
Accepted
time: 11ms
memory: 69032kb

input:

100 100
0 1 2
1 2 3
2 3 2
3 4 0
4 5 2
5 6 1
6 7 2
7 8 1
8 9 2
9 10 1
10 11 2
11 12 2
12 13 0
13 14 3
14 15 0
15 16 3
16 17 3
17 18 0
18 19 2
19 20 0
20 21 3
21 22 1
22 23 0
23 24 3
24 25 3
25 26 0
26 27 1
27 28 1
28 29 0
29 30 2
30 31 3
31 32 3
32 33 2
33 34 0
34 35 3
35 36 2
36 37 3
37 38 1
38 39 2...

output:

Correct.

Test #9:

score: 0
Accepted
time: 12ms
memory: 69036kb

input:

100 100
0 1 3
1 2 0
2 3 1
3 4 3
4 5 2
5 6 0
6 7 3
7 8 3
8 9 2
9 10 3
10 11 2
11 12 3
12 13 3
13 14 3
14 15 1
15 16 1
16 17 1
17 18 0
18 19 0
19 20 0
20 21 0
21 22 2
22 23 0
23 24 0
24 25 0
25 26 2
26 27 0
27 28 3
28 29 3
29 30 0
30 31 0
31 32 2
32 33 0
33 34 0
34 35 3
35 36 2
36 37 0
37 38 0
38 39 2...

output:

Correct.

Test #10:

score: 0
Accepted
time: 17ms
memory: 69032kb

input:

100 100
0 1 0
1 2 3
2 3 1
3 4 3
4 5 1
5 6 1
6 7 0
7 8 0
8 9 0
9 10 2
10 11 1
11 12 1
12 13 0
13 14 2
14 15 0
15 16 1
16 17 1
17 18 2
18 19 0
19 20 3
20 21 2
21 22 2
22 23 0
23 24 0
24 25 3
25 26 1
26 27 2
27 28 3
28 29 0
29 30 3
30 31 3
31 32 2
32 33 1
33 34 3
34 35 3
35 36 2
36 37 0
37 38 2
38 39 1...

output:

Correct.

Test #11:

score: 0
Accepted
time: 8ms
memory: 69032kb

input:

100 90
0 1 7
1 2 7
2 3 8
3 4 8
4 5 7
5 6 8
6 7 7
7 8 7
8 9 7
9 10 7
10 11 8
11 12 8
12 13 7
13 14 7
14 15 7
15 16 8
16 17 7
17 18 7
18 19 8
19 20 8
20 21 8
21 22 7
22 23 8
23 24 8
24 25 8
25 26 8
26 27 8
27 28 7
28 29 7
29 30 7
30 31 7
31 32 7
32 33 7
33 34 8
34 35 7
35 36 8
36 37 7
37 38 7
38 39 8
...

output:

Correct.

Test #12:

score: 0
Accepted
time: 12ms
memory: 66996kb

input:

100 78
0 1 18
1 2 19
2 3 17
3 4 15
4 5 16
5 6 15
6 7 19
7 8 17
8 9 15
9 10 15
10 11 17
11 12 18
12 13 19
13 14 16
14 15 17
15 16 18
16 17 17
17 18 15
18 19 19
19 20 19
20 21 17
21 22 18
22 23 19
23 24 16
24 25 17
25 26 19
26 27 17
27 28 17
28 29 19
29 30 15
30 31 16
31 32 16
32 33 18
33 34 15
34 35 ...

output:

Correct.

Test #13:

score: 0
Accepted
time: 15ms
memory: 67040kb

input:

100 100
1 0 0
2 1 0
3 2 0
4 3 0
5 4 0
6 5 0
7 6 0
8 7 0
9 8 0
10 9 0
11 10 0
12 11 0
13 12 0
14 13 0
15 14 0
16 15 0
17 16 0
18 17 0
19 18 0
20 19 0
21 20 0
22 21 0
23 22 0
24 23 0
25 24 0
26 25 0
27 26 0
28 27 0
29 28 0
30 29 0
31 30 0
32 31 0
33 32 0
34 33 0
35 34 0
36 35 0
37 36 0
38 37 0
39 38 0...

output:

Correct.

Test #14:

score: 0
Accepted
time: 19ms
memory: 69076kb

input:

100 100
1 0 1000000
2 1 1000000
3 2 1000000
4 3 1000000
5 4 1000000
6 5 1000000
7 6 1000000
8 7 1000000
9 8 1000000
10 9 1000000
11 10 1000000
12 11 1000000
13 12 1000000
14 13 1000000
15 14 1000000
16 15 1000000
17 16 1000000
18 17 1000000
19 18 1000000
20 19 1000000
21 20 1000000
22 21 1000000
23 ...

output:

Correct.

Test #15:

score: 0
Accepted
time: 17ms
memory: 66856kb

input:

100 100
0 1 1
1 2 1
2 3 0
3 4 0
4 5 1
5 6 1
6 7 0
7 8 1
8 9 0
9 10 1
10 11 1
11 12 0
12 13 0
13 14 0
14 15 1
15 16 1
16 17 0
17 18 1
18 19 1
19 20 0
20 21 0
21 22 0
22 23 1
23 24 0
24 25 0
25 26 0
26 27 1
27 28 0
28 29 1
29 30 0
30 31 1
31 32 0
32 33 1
33 34 0
34 35 0
35 36 1
36 37 1
37 38 1
38 39 1...

output:

Correct.

Test #16:

score: 0
Accepted
time: 15ms
memory: 68916kb

input:

100 100
0 1 101
1 2 85
2 3 68
3 4 25
4 5 87
5 6 30
6 7 87
7 8 37
8 9 14
9 10 18
10 11 4
11 12 36
12 13 27
13 14 101
14 15 80
15 16 29
16 17 7
17 18 8
18 19 31
19 20 51
20 21 0
21 22 22
22 23 40
23 24 28
24 25 7
25 26 48
26 27 74
27 28 20
28 29 59
29 30 23
30 31 34
31 32 75
32 33 48
33 34 19
34 35 85...

output:

Correct.

Test #17:

score: 0
Accepted
time: 7ms
memory: 69272kb

input:

100 100
0 1 90
1 2 38
2 3 31
3 4 72
4 5 4
5 6 36
6 7 45
7 8 23
8 9 73
9 10 92
10 11 71
11 12 5
12 13 26
13 14 92
14 15 35
15 16 86
16 17 2
17 18 3
18 19 53
19 20 82
20 21 17
21 22 58
22 23 7
23 24 89
24 25 84
25 26 8
26 27 96
27 28 9
28 29 24
29 30 48
30 31 30
31 32 18
32 33 56
33 34 58
34 35 14
35 ...

output:

Correct.

Test #18:

score: 0
Accepted
time: 17ms
memory: 69044kb

input:

100 100
0 1 3
1 2 6
2 3 1
3 4 9
4 5 8
5 6 0
6 7 6
7 8 10
8 9 4
9 10 5
10 11 1
11 12 1
12 13 9
13 14 4
14 15 5
15 16 7
16 17 7
17 18 5
18 19 6
19 20 8
20 21 1
21 22 5
22 23 1
23 24 2
24 25 3
25 26 7
26 27 8
27 28 3
28 29 9
29 30 9
30 31 3
31 32 1
32 33 8
33 34 5
34 35 6
35 36 5
36 37 5
37 38 2
38 39 ...

output:

Correct.

Subtask #2:

score: 12
Accepted

Dependency #1:

100%
Accepted

Test #19:

score: 12
Accepted
time: 15ms
memory: 69244kb

input:

10 7
5 0 1
2 0 1
8 0 2
9 5 2
3 9 1
1 9 3
4 8 3
7 3 3
6 8 1
3

output:

Correct.

Test #20:

score: 0
Accepted
time: 15ms
memory: 69128kb

input:

1000 199112
762 339 28482
749 762 227
319 749 53263
552 762 12523
716 339 46366
613 319 74345
249 339 72086
42 249 2870
589 552 5725
179 42 53677
760 249 5715
298 552 163
67 179 2902
573 319 2
219 573 10621
539 749 4024
335 219 254
727 42 6119
429 298 8518
825 219 17484
248 249 43205
244 67 11387
31...

output:

Correct.

Test #21:

score: 0
Accepted
time: 15ms
memory: 67184kb

input:

1000 324823
854 731 3848
755 731 22202
116 731 82580
306 116 38
985 755 21493
894 755 75174
769 306 7726
382 731 69175
848 985 30471
954 755 7233
249 894 9073
370 854 1356
408 249 51635
227 370 3175
792 370 3593
496 985 80557
428 227 21
301 854 4598
60 954 6099
827 60 44025
37 954 35890
945 731 8090...

output:

Correct.

Test #22:

score: 0
Accepted
time: 15ms
memory: 69480kb

input:

1000 366977
448 502 61189
568 502 12171
32 448 470
182 32 57463
409 448 63075
159 409 57598
901 568 1262
599 568 53
353 901 96550
912 32 16190
217 568 3427
60 448 10526
799 353 1175
549 409 2572
57 159 34913
743 549 2126
293 409 5579
849 60 17348
357 32 11329
477 502 53441
516 477 2105
260 599 84783...

output:

Correct.

Test #23:

score: 0
Accepted
time: 16ms
memory: 69192kb

input:

1000 653406
75 813 588
943 75 95226
449 943 27576
655 943 7287
656 943 48742
138 656 75413
373 138 60
285 449 44721
211 285 16387
699 75 1862
74 813 95942
86 813 35501
723 656 6301
861 373 15368
27 699 53373
492 813 97529
97 699 10036
728 75 77032
781 74 2862
124 728 16153
944 656 23013
745 74 99720...

output:

Correct.

Test #24:

score: 0
Accepted
time: 12ms
memory: 69180kb

input:

1000 709447
236 940 32176
915 940 37864
828 915 4407
537 828 42618
37 940 1193
454 537 61661
209 37 67522
200 209 17413
565 454 42932
433 565 81882
148 37 36134
4 209 92927
467 828 88968
163 148 71394
403 467 96051
749 433 98105
423 537 53373
294 163 52687
165 209 9587
824 148 3534
637 403 97839
685...

output:

Correct.

Test #25:

score: 0
Accepted
time: 15ms
memory: 69244kb

input:

1000 782099
83 140 49127
178 83 5651
988 178 72207
735 178 75496
152 735 2616
453 735 47873
499 152 86016
31 152 65924
548 31 21058
613 31 28790
400 31 28539
225 400 64668
907 613 2098
27 548 91168
668 27 22662
160 27 37531
436 400 11586
440 225 48126
718 440 59242
984 718 73379
922 27 56416
728 668...

output:

Correct.

Test #26:

score: 0
Accepted
time: 12ms
memory: 69156kb

input:

921 590007
171 474 42940
474 831 16568
831 304 14707
304 588 47559
588 873 484
873 248 44533
248 778 30660
778 423 13081
423 757 39197
757 858 31373
858 31 5651
31 326 47096
326 43 12437
43 367 8017
367 175 37267
175 711 20278
711 868 32767
868 166 1147
166 483 20699
483 694 17553
694 343 31933
343 ...

output:

Correct.

Test #27:

score: 0
Accepted
time: 11ms
memory: 67404kb

input:

892 812365
150 547 47626
547 211 8069
211 450 5073
450 83 15844
83 463 32533
463 162 18136
162 616 38946
616 208 46311
208 426 13486
426 711 1563
711 5 34500
5 732 14509
732 348 5191
348 143 41434
143 434 36868
434 129 13120
129 333 2262
333 215 28924
215 504 27493
504 519 45708
519 752 9209
752 798...

output:

Correct.

Test #28:

score: 0
Accepted
time: 12ms
memory: 69164kb

input:

826 930612
414 268 18141
268 369 44539
369 418 21069
418 65 22682
65 269 23679
269 626 2522
626 538 23730
538 705 3402
705 701 27463
701 20 6363
20 513 49707
513 78 44688
78 379 6114
379 386 16315
386 56 159
56 88 19145
88 430 4537
430 743 44073
743 794 16188
794 603 24946
603 480 37555
480 420 2342...

output:

Correct.

Test #29:

score: 0
Accepted
time: 15ms
memory: 67124kb

input:

826 795916
373 680 3800
680 395 1305
395 658 3185
658 795 2839
795 605 139
605 283 2268
283 455 1725
455 451 3782
451 117 277
117 193 4895
193 103 4497
103 254 1140
254 416 384
416 628 4296
628 738 2279
738 275 4969
275 689 2906
689 514 1281
514 396 3635
396 108 2925
108 232 3781
232 306 524
306 293...

output:

Correct.

Test #30:

score: 0
Accepted
time: 15ms
memory: 69220kb

input:

100 22
25 78 3
21 78 1
63 78 2
72 21 1
77 21 2
57 77 3
70 21 3
5 21 3
95 72 2
34 78 3
84 25 1
27 72 3
52 84 2
66 70 1
4 72 1
90 78 3
20 95 3
89 95 1
17 20 3
58 25 3
8 34 3
16 90 1
9 27 3
39 34 3
3 20 2
1 95 3
47 25 3
80 84 1
62 21 3
54 1 3
98 63 1
38 34 3
69 62 1
42 58 3
86 17 1
48 57 2
19 48 2
94 6...

output:

Correct.

Test #31:

score: 0
Accepted
time: 15ms
memory: 69152kb

input:

925 508606
242 124 4984
124 859 874
859 674 26
674 153 626
153 551 977
551 841 2598
841 429 3246
429 610 4421
610 739 4795
739 821 2179
821 508 3127
508 432 2882
432 923 3375
923 308 8
308 842 3669
842 133 4866
133 3 766
3 186 3762
186 80 4224
80 82 4814
82 426 390
426 818 1502
818 147 1092
147 682 ...

output:

Correct.

Test #32:

score: 0
Accepted
time: 12ms
memory: 69116kb

input:

1000 764
518 191 46
805 518 52
381 518 29
422 518 40
4 191 18
817 422 38
894 422 11
821 191 25
896 381 16
349 191 42
39 349 34
179 349 25
772 179 30
912 191 29
323 805 3
636 894 6
228 821 14
197 381 20
255 821 5
91 422 27
162 228 2
781 805 36
352 323 5
417 197 34
559 255 63
994 91 63
7 559 22
784 38...

output:

Correct.

Test #33:

score: 0
Accepted
time: 11ms
memory: 69208kb

input:

1000 920236
750 950 557320
814 750 987579
858 814 966276
143 814 866618
403 858 284391
598 143 125262
536 143 125701
626 598 161758
889 536 330196
396 889 548743
177 889 863105
818 396 751812
271 396 101375
792 177 760904
414 396 710344
661 818 318258
270 818 400012
495 271 667454
653 270 153771
754...

output:

Correct.

Test #34:

score: 0
Accepted
time: 7ms
memory: 69444kb

input:

1000 753860
227 458 21111
570 227 84533
611 570 150029
786 570 269774
412 611 379594
805 412 887270
565 412 317425
367 412 107659
558 565 642786
784 558 978539
780 558 555471
683 784 905071
643 784 169983
802 558 851006
557 784 445461
774 784 708696
179 643 390915
174 683 267650
452 174 368580
806 7...

output:

Correct.

Test #35:

score: 0
Accepted
time: 11ms
memory: 67460kb

input:

1000 864337
468 266 72959
913 266 824883
130 468 336929
397 130 481568
810 913 144973
234 468 65791
174 130 639277
226 266 414771
853 397 519231
561 130 825789
988 130 609107
968 266 494692
443 810 685016
292 810 709882
980 810 663969
876 853 171846
826 226 530930
33 968 725219
514 810 512667
993 39...

output:

Correct.

Test #36:

score: 0
Accepted
time: 7ms
memory: 67460kb

input:

1000 841712
299 962 22090
305 299 45982
29 305 9920
106 962 9594
822 106 52591
357 299 32937
302 29 55377
307 302 78108
278 305 63036
244 106 29944
654 278 59540
418 822 60315
314 106 26572
789 357 31618
49 29 24141
497 418 64807
178 49 69975
111 789 3552
695 178 39397
513 789 53867
129 178 35932
72...

output:

Correct.

Test #37:

score: 0
Accepted
time: 11ms
memory: 69256kb

input:

1000 337882
544 223 336251
299 223 158955
355 223 3643
585 544 157536
351 355 160555
233 351 171262
999 355 273403
651 233 31864
425 585 332969
16 223 191669
758 351 181423
872 223 177793
939 355 154493
8 16 202646
511 872 100159
23 511 257639
279 223 127215
984 999 317347
358 23 205878
473 425 3280...

output:

Correct.

Test #38:

score: 0
Accepted
time: 18ms
memory: 69060kb

input:

1000 801624
832 556 1000000
916 832 1000000
407 916 1000000
383 407 1000000
640 556 1000000
532 407 1000000
347 407 1000000
952 640 1000000
135 832 1000000
577 556 1000000
771 577 1000000
236 347 1000000
587 577 1000000
888 587 1000000
125 347 1000000
156 125 1000000
79 771 1000000
445 156 1000000
2...

output:

Correct.

Subtask #3:

score: 22
Accepted

Test #39:

score: 22
Accepted
time: 68ms
memory: 85228kb

input:

100000 100
1 0 1
2 1 10
3 1 1
4 3 5
5 3 6
6 5 6
7 3 10
8 5 9
9 8 7
10 9 9
11 6 7
12 6 3
13 10 10
14 9 1
15 14 7
16 15 5
17 10 1
18 14 9
19 12 8
20 18 10
21 10 9
22 12 7
23 14 9
24 15 5
25 15 2
26 20 4
27 19 10
28 17 8
29 16 8
30 24 10
31 17 2
32 28 7
33 27 8
34 21 4
35 28 7
36 22 4
37 18 6
38 27 6
3...

output:

Correct.

Test #40:

score: 0
Accepted
time: 112ms
memory: 130456kb

input:

200000 100
192164 110199 93
47882 192164 72
146145 47882 33
126329 146145 51
179411 126329 12
64302 179411 54
149999 64302 60
68743 149999 54
6947 68743 48
34108 6947 96
153071 34108 21
124245 153071 27
80021 124245 78
35586 80021 33
63565 35586 99
146479 63565 78
112365 146479 87
66626 112365 18
16...

output:

Correct.

Test #41:

score: 0
Accepted
time: 107ms
memory: 129056kb

input:

200000 97
124561 2131 18
168021 124561 90
65536 168021 96
130830 65536 6
58340 130830 6
118024 58340 42
104437 118024 36
67532 104437 54
104313 67532 24
132363 104313 96
140771 132363 30
2297 140771 18
82285 2297 48
87437 82285 12
55493 87437 72
179845 55493 90
26917 179845 24
53910 26917 48
129657 ...

output:

Correct.

Test #42:

score: 0
Accepted
time: 95ms
memory: 90108kb

input:

198766 86
38130 38131 5
155346 155639 6
180745 180746 3
185908 185909 7
107946 108231 9
144465 144477 9
176974 176975 7
133125 133389 5
194088 194089 8
188165 188439 4
72065 72340 4
80346 80629 7
52493 52494 7
44364 44365 4
132787 132788 1
111621 111853 3
161345 161508 6
41753 41754 4
78755 78756 7
...

output:

Correct.

Test #43:

score: 0
Accepted
time: 89ms
memory: 93160kb

input:

198766 86
38130 38131 4
155346 155639 3
180745 180746 7
185908 185909 3
107946 108231 1
144465 144477 5
176974 176975 4
133125 133389 3
194088 194089 6
188165 188439 5
72065 72340 4
80346 80629 1
52493 52494 3
44364 44365 9
132787 132788 3
111621 111853 6
161345 161508 4
41753 41754 5
78755 78756 6
...

output:

Correct.

Test #44:

score: 0
Accepted
time: 120ms
memory: 92812kb

input:

198451 99
42497 158805 16
83677 171918 6
164409 16480 4
65700 172431 6
20132 33243 6
19027 39931 18
180642 188093 20
110506 2223 12
48861 83975 4
193291 6277 16
37431 41363 6
115876 83987 12
109068 107907 14
167322 157730 8
19357 121205 6
37871 144561 2
158240 55090 4
60419 103727 10
93041 64438 12
...

output:

Correct.

Test #45:

score: 0
Accepted
time: 102ms
memory: 96536kb

input:

198991 100
196029 70769 1
70769 151830 1
151830 124833 1
124833 168683 1
168683 153063 1
153063 78481 1
78481 126030 1
126030 79598 1
79598 57434 1
57434 135918 1
135918 167763 1
167763 73281 1
73281 66913 1
66913 54923 1
54923 109906 1
109906 77105 1
77105 61892 1
61892 79098 1
79098 22614 1
22614 ...

output:

Correct.

Test #46:

score: 0
Accepted
time: 164ms
memory: 132256kb

input:

198277 100
34664 176620 1
176620 27592 1
27592 122762 1
122762 9726 1
9726 171935 1
171935 110727 1
110727 107016 1
107016 90375 1
90375 45336 1
45336 122311 1
122311 136516 1
136516 171571 1
171571 58056 1
58056 106150 1
106150 165523 1
165523 125382 1
125382 88774 1
88774 95100 1
95100 89056 1
890...

output:

Correct.

Test #47:

score: 0
Accepted
time: 78ms
memory: 87688kb

input:

100000 100
1 0 10
2 1 6
3 1 6
4 3 8
5 4 5
6 5 3
7 6 5
8 6 2
9 6 9
10 6 9
11 10 6
12 8 1
13 7 5
14 9 2
15 10 7
16 15 2
17 11 2
18 15 2
19 12 8
20 15 6
21 13 1
22 13 7
23 18 10
24 15 3
25 17 3
26 17 4
27 14 3
28 20 4
29 23 3
30 19 3
31 28 3
32 16 9
33 28 5
34 30 7
35 32 10
36 29 8
37 24 3
38 29 7
39 2...

output:

Correct.

Test #48:

score: 0
Accepted
time: 77ms
memory: 84852kb

input:

100000 100
1 0 1
2 1 7
3 1 6
4 2 1
5 2 9
6 3 1
7 4 9
8 6 3
9 3 8
10 8 8
11 10 8
12 11 8
13 7 3
14 10 9
15 11 1
16 11 2
17 10 2
18 13 1
19 13 4
20 10 8
21 20 5
22 11 8
23 7 6
24 11 9
25 12 7
26 9 7
27 13 10
28 15 10
29 18 9
30 17 7
31 18 6
32 28 3
33 23 2
34 27 9
35 34 1
36 22 7
37 34 10
38 21 6
39 1...

output:

Correct.

Test #49:

score: 0
Accepted
time: 80ms
memory: 87420kb

input:

100000 100
73221 58566 10
60747 73221 8
16080 58566 12
14740 73221 1
82191 58566 10
34172 58566 5
17344 60747 9
67648 14740 14
83814 14740 12
71932 73221 12
60181 58566 5
60372 14740 4
32835 71932 2
98403 73221 4
18187 17344 14
63623 82191 6
10653 98403 8
18961 60372 1
29161 32835 1
642 34172 6
1568...

output:

Correct.

Test #50:

score: 0
Accepted
time: 97ms
memory: 98508kb

input:

100000 100
31968 17836 43
85028 31968 69
74374 31968 89
49590 85028 59
84942 85028 94
51035 74374 16
96575 74374 35
41094 49590 16
53465 49590 97
75329 84942 95
49720 84942 73
95018 51035 6
32483 51035 51
76446 96575 2
24981 96575 4
86313 41094 31
63589 41094 7
19275 53465 62
50220 53465 52
74546 75...

output:

Correct.

Test #51:

score: 0
Accepted
time: 70ms
memory: 91256kb

input:

100000 100
45711 72653 7
53948 72653 38
76311 72653 65
41227 72653 2
59700 72653 53
21851 72653 75
39855 45711 8
46996 45711 65
37844 45711 15
76367 45711 81
73372 45711 37
47330 45711 1
58077 45711 73
44463 53948 10
48748 53948 79
3178 53948 1
22756 53948 79
91555 53948 8
40575 53948 97
11675 53948...

output:

Correct.

Test #52:

score: 0
Accepted
time: 56ms
memory: 84020kb

input:

100000 100
85906 80909 0
79756 85906 1
9781 79756 1
9499 9781 0
95054 9499 0
59745 95054 0
11616 59745 1
78949 11616 0
90875 78949 0
6148 90875 0
8988 6148 0
62677 8988 0
53035 62677 0
13446 53035 0
60312 13446 1
93179 60312 0
29344 93179 0
93942 29344 0
77047 93942 0
74181 77047 0
67308 74181 0
265...

output:

Correct.

Test #53:

score: 0
Accepted
time: 27ms
memory: 89304kb

input:

100000 100
1 0 0
2 1 0
3 2 0
4 3 0
5 4 0
6 5 0
7 6 0
8 7 0
9 8 0
10 9 0
11 10 0
12 11 0
13 12 0
14 13 0
15 14 0
16 15 0
17 16 0
18 17 0
19 18 0
20 19 0
21 20 0
22 21 0
23 22 0
24 23 0
25 24 0
26 25 0
27 26 0
28 27 0
29 28 0
30 29 0
31 30 0
32 31 0
33 32 0
34 33 0
35 34 0
36 35 0
37 36 0
38 37 0
39 3...

output:

Correct.

Test #54:

score: 0
Accepted
time: 93ms
memory: 93048kb

input:

198766 86
38130 38131 1
155346 155639 1
180745 180746 5
185908 185909 7
107946 108231 8
144465 144477 9
176974 176975 6
133125 133389 3
194088 194089 3
188165 188439 3
72065 72340 7
80346 80629 8
52493 52494 10
44364 44365 9
132787 132788 5
111621 111853 10
161345 161508 6
41753 41754 9
78755 78756 ...

output:

Correct.

Subtask #4:

score: 57
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Test #55:

score: 57
Accepted
time: 21ms
memory: 71140kb

input:

10000 4821
4378 9504 442
7818 9504 950
5086 7818 302
2434 7818 597
1849 5086 692
1627 4378 953
1400 5086 432
8525 1627 459
4702 8525 354
5239 4702 714
1395 4378 630
6637 4702 477
8187 1849 157
6422 4378 94
7585 1849 767
8399 4378 690
1115 5086 805
707 1395 190
2311 7818 324
7376 1400 530
7307 8525 1...

output:

Correct.

Test #56:

score: 0
Accepted
time: 222ms
memory: 146984kb

input:

200000 512359
21579 163986 2487
2182 21579 8140
195102 21579 1591
108589 2182 1838
194795 108589 820
127288 194795 6643
82339 195102 6176
143711 82339 3602
92942 143711 6552
138855 82339 799
103941 82339 8474
198114 82339 7066
152569 92942 562
138065 138855 9272
38794 103941 4828
45098 143711 51
691...

output:

Correct.

Test #57:

score: 0
Accepted
time: 209ms
memory: 144084kb

input:

200000 451
75877 48059 831415
19519 48059 349338
182818 75877 942626
145028 75877 283153
66417 19519 656806
53786 48059 444947
92192 53786 278776
161226 75877 114214
80190 145028 289201
52521 75877 365270
16162 161226 93896
8155 92192 764177
25956 92192 210050
52264 161226 902578
185734 52521 288665...

output:

Correct.

Test #58:

score: 0
Accepted
time: 116ms
memory: 125764kb

input:

200000 1000000
123077 116449 980
52428 123077 651
104986 52428 917
19778 104986 343
186528 19778 924
55555 186528 98
31822 55555 623
150652 31822 966
105211 150652 567
182251 105211 378
132472 182251 126
82035 132472 931
48008 82035 343
114577 48008 161
27657 114577 693
190532 27657 770
135132 19053...

output:

Correct.

Test #59:

score: 0
Accepted
time: 99ms
memory: 85648kb

input:

200000 1000000
12410 121574 728
167667 121574 980
119177 121574 763
68104 119177 692
116190 121574 595
99244 121574 378
62905 121574 399
70753 121574 924
47909 121574 637
145133 121574 217
49461 121574 651
46237 121574 63
132184 46237 312
106356 121574 217
93602 121574 938
16135 121574 665
178822 12...

output:

Correct.

Test #60:

score: 0
Accepted
time: 148ms
memory: 117544kb

input:

195856 990993
85209 25896 888
165976 120562 662
179699 172526 336
46435 163787 799202
15243 170817 970
59419 177426 705898
21363 32148 744912
167971 103441 727234
75131 96740 728030
28454 147407 753742
109907 175907 780424
103598 7999 669940
82149 109071 743526
169496 80990 330
66850 143468 689870
9...

output:

Correct.

Test #61:

score: 0
Accepted
time: 147ms
memory: 117672kb

input:

197989 990993
24391 186431 768632
135970 20225 760
16697 194195 94
152645 92413 769524
143931 160939 612
80240 72183 694522
135627 54541 880
53497 34711 58
148837 144124 628
111369 84815 428
195048 167259 314
58020 166567 826
63479 58139 763084
20581 155479 654
137647 101461 668964
193511 105600 687...

output:

Correct.

Test #62:

score: 0
Accepted
time: 135ms
memory: 115228kb

input:

186823 990993
14767 22295 741510
43665 67860 794
186633 60017 798790
61225 138636 364
50199 16920 792938
152603 92062 788
18769 128244 775370
36946 68775 748656
46377 89774 338
137471 96108 668400
78861 119122 712984
176299 70084 144
181901 116205 682750
94585 85371 769122
12580 5478 954
101726 5493...

output:

Correct.

Test #63:

score: 0
Accepted
time: 19ms
memory: 70396kb

input:

10000 123
1 0 3
2 1 2
3 2 1
4 2 3
5 4 2
6 3 2
7 4 3
8 5 3
9 4 1
10 5 3
11 6 1
12 7 1
13 6 3
14 12 3
15 10 3
16 9 1
17 8 2
18 11 1
19 13 3
20 16 3
21 16 1
22 17 3
23 14 1
24 16 3
25 14 3
26 23 1
27 24 3
28 27 2
29 15 3
30 22 2
31 17 2
32 18 2
33 17 2
34 26 3
35 30 1
36 34 2
37 22 3
38 25 3
39 23 3
40...

output:

Correct.

Test #64:

score: 0
Accepted
time: 42ms
memory: 85820kb

input:

100000 50
1 0 2
2 1 1
3 1 1
4 2 2
5 2 2
6 3 2
7 3 1
8 4 1
9 4 3
10 5 3
11 5 3
12 6 3
13 6 3
14 7 1
15 7 1
16 8 3
17 8 3
18 9 3
19 9 3
20 10 1
21 10 3
22 11 3
23 11 1
24 12 1
25 12 2
26 13 3
27 13 3
28 14 2
29 14 1
30 15 2
31 15 3
32 16 2
33 16 3
34 17 3
35 17 3
36 18 2
37 18 2
38 19 2
39 19 3
40 20 ...

output:

Correct.

Test #65:

score: 0
Accepted
time: 32ms
memory: 78264kb

input:

100000 107
1 0 77
2 0 16
3 0 21
4 0 9
5 0 30
6 0 29
7 0 70
8 0 30
9 0 60
10 0 18
11 0 76
12 0 69
13 0 23
14 0 33
15 0 89
16 0 79
17 0 62
18 0 25
19 0 86
20 0 89
21 0 3
22 0 1
23 0 63
24 0 5
25 0 98
26 0 23
27 0 19
28 0 66
29 0 3
30 0 49
31 0 8
32 0 91
33 0 32
34 0 16
35 0 42
36 0 2
37 0 22
38 0 32
3...

output:

Correct.

Test #66:

score: 0
Accepted
time: 39ms
memory: 100800kb

input:

100000 185710
1 0 2
2 1 1
3 2 1
4 3 2
5 4 1
6 5 3
7 6 3
8 7 3
9 8 1
10 9 1
11 10 1
12 11 2
13 12 2
14 13 1
15 14 3
16 15 3
17 16 2
18 17 3
19 18 2
20 19 1
21 20 1
22 21 2
23 22 2
24 23 2
25 24 2
26 25 3
27 26 2
28 27 2
29 28 1
30 29 2
31 30 2
32 31 1
33 32 1
34 33 2
35 34 3
36 35 2
37 36 3
38 37 1
3...

output:

Correct.

Test #67:

score: 0
Accepted
time: 106ms
memory: 129636kb

input:

200000 1000000
11214 56331 8
91349 11214 3
152442 91349 4
68890 152442 5
105377 68890 9
185245 105377 4
36322 185245 6
106874 36322 3
83324 106874 6
97046 83324 5
98137 97046 9
93206 98137 6
16177 93206 4
83390 16177 4
194622 83390 8
83749 194622 3
166730 83749 7
168778 166730 5
30409 168778 7
18834...

output:

Correct.

Test #68:

score: 0
Accepted
time: 109ms
memory: 97104kb

input:

198766 4768
38130 38131 32
155346 155639 65
180745 180746 79
185908 185909 48
107946 108231 12
144465 144477 82
176974 176975 74
133125 133389 70
194088 194089 82
188165 188439 84
72065 72340 31
80346 80629 79
52493 52494 100
44364 44365 12
132787 132788 93
111621 111853 21
161345 161508 27
41753 41...

output:

Correct.

Test #69:

score: 0
Accepted
time: 74ms
memory: 92240kb

input:

198451 999999
32003 32271 6
30099 30322 20
9372 9436 6
32967 33263 2
185908 185909 14
75527 75532 14
63016 63017 2
124947 125071 10
114158 114159 6
74259 74518 12
15612 15660 4
132575 132576 4
71124 71438 6
76164 76416 14
85664 85665 10
47844 47882 8
19347 19507 6
74196 74197 8
171255 171256 6
18415...

output:

Correct.

Test #70:

score: 0
Accepted
time: 131ms
memory: 92828kb

input:

198451 999999
169840 51436 2
140041 139400 18
60506 188274 14
143076 113770 18
122106 141071 2
144214 113337 16
62428 27143 16
71359 92740 4
75400 45988 6
146619 39570 8
185244 137373 4
84923 106963 18
175412 48203 2
143854 138440 8
22204 70204 18
112057 180164 4
63552 147921 16
41826 15963 18
17991...

output:

Correct.