QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#386670#3045. Minimum Diameter Spanning Treejames1BadCreeperAC ✓177ms13184kbC++142.4kb2024-04-11 19:14:072024-04-11 19:14:08

Judging History

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

  • [2024-04-11 19:14:08]
  • 评测
  • 测评结果：AC
  • 用时：177ms
  • 内存：13184kb
查看
  • [2024-04-11 19:14:07]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long i64; 
const int N = 505; 

int n, m; 
int u[N * N], v[N * N]; 
int rk[N][N], is[N][N]; 
i64 d[N][N], g[N][N], w[N * N], dis[N]; 
bool vis[N]; 

int main(void) {
    ios::sync_with_stdio(0); 
    cin >> n >> m; memset(d, 0x3f, sizeof d); memset(g, 0x3f, sizeof g); 
    for (int i = 1; i <= n; ++i) d[i][i] = g[i][i] = 0; 
    for (int i = 1; i <= m; ++i) {
        cin >> u[i] >> v[i] >> w[i]; is[u[i]][v[i]] = is[v[i]][u[i]] = 1; 
        w[i] *= 2; 
        d[u[i]][v[i]] = d[v[i]][u[i]] = min(d[u[i]][v[i]], w[i]); 
        g[u[i]][v[i]] = g[v[i]][u[i]] = min(g[u[i]][v[i]], w[i]); 
    }
    for (int k = 1; k <= n; ++k) for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) d[i][j] = min(d[i][j], d[i][k] + d[k][j]); 
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) rk[i][j] = j; 
        sort(rk[i] + 1, rk[i] + n + 1, [i](int x, int y) { return d[i][x] < d[i][y]; }); 
    }
    int x, y; i64 ans = 1e18, wx = 0; 
    for (int i = 1; i <= n; ++i)
        if (d[i][rk[i][n]] * 2 < ans) ans = d[i][rk[i][n]] * 2, x = y = i; 
    for (int i = 1; i <= m; ++i) {
        int u = ::u[i], v = ::v[i], w = ::w[i]; 
        for (int p = n, i = n - 1; i >= 1; --i)
            if (d[v][rk[u][i]] > d[v][rk[u][p]]) {
                i64 val = d[u][rk[u][i]] + w + d[v][rk[u][p]]; 
                if (val < ans) ans = val, x = u, y = v, wx = (d[v][rk[u][p]] - d[u][rk[u][i]] + w) / 2; 
                p = i; 
            }
    }
    cout << ans / 2 << "\n"; 

    memset(dis, 0x3f, sizeof dis); i64 INF = dis[0]; 
    #define pli pair<i64, int> 
    priority_queue<pli, vector<pli>, greater<pli>> q; 
    q.emplace(dis[x] = wx, x); q.emplace(dis[y] = g[x][y] - wx, y); 
    
    while (!q.empty()) {
        int u = q.top().second; q.pop(); 
        if (vis[u]) continue; vis[u] = 1; 
        for (int v = 1; v <= n; ++v) if (v != u) 
            if (dis[v] > dis[u] + g[u][v]) q.emplace(dis[v] = dis[u] + g[u][v], v); 
    }
    // for (int i = 1; i <= n; ++i) cout << dis[i] << " \n"[i == n]; 

    if (x != y) cout << x << " " << y << "\n"; 
    for (int i = 1; i <= n; ++i) if (i != x && i != y)
        for (int j = 1; j <= n; ++j) if (i != j && dis[i] == dis[j] + g[i][j]) {
            if (i < j) cout << i << " " << j << "\n"; 
            else cout << j << " " << i << "\n"; 
            break; 
        }
    return 0;
}
源文件, 语言: C++14

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 11848kb

input:

3 3
1 2 1
2 3 1
3 1 1

output:

2
1 2
1 3

result:

ok

Test #2:

score: 0
Accepted
time: 2ms
memory: 11860kb

input:

6 7
1 2 10
2 3 20
1 3 30
3 4 1000
4 5 30
5 6 20
4 6 10

output:

1060
3 4
1 2
2 3
4 5
4 6

result:

ok

Test #3:

score: 0
Accepted
time: 0ms
memory: 12080kb

input:

16 120
11 4 2
3 10 2
12 4 1
16 9 3
2 7 4
16 3 1
3 2 2
13 15 2
9 1 1
13 1 2
14 15 2
16 8 1
1 15 2
5 1 3
7 4 3
8 13 1
4 13 2
9 4 1
1 3 3
13 6 2
13 2 1
3 9 4
7 6 1
10 14 1
3 14 3
12 5 2
15 16 2
2 5 2
15 11 4
10 8 2
2 14 3
10 16 1
11 1 2
5 10 4
14 11 2
6 4 2
13 10 3
14 1 2
1 4 2
5 7 2
12 6 1
13 11 2
6 5...

output:

7
11 4
1 2
2 11
3 11
4 5
3 6
3 7
1 8
4 9
10 11
11 12
2 13
10 14
4 15
3 16

result:

ok

Test #4:

score: 0
Accepted
time: 25ms
memory: 12004kb

input:

256 32640
142 82 7
78 125 3
66 149 6
31 236 2
226 136 3
167 225 3
120 135 5
124 79 3
138 17 5
1 90 1
128 38 4
44 190 3
38 43 6
46 12 6
32 232 4
137 7 2
58 139 3
40 13 5
29 181 5
184 205 1
171 186 4
135 237 5
173 163 3
98 4 2
248 97 5
99 93 4
139 247 5
205 144 5
38 194 5
108 144 4
222 67 5
104 77 5
2...

output:

15
142 82
1 90
2 26
3 31
4 26
2 5
6 37
1 7
8 26
9 82
3 10
11 26
12 31
1 13
6 14
4 15
1 16
17 37
2 18
3 19
1 20
21 31
6 22
1 23
1 24
1 25
26 142
27 49
1 28
21 29
30 31
31 142
1 32
2 33
31 34
4 35
2 36
37 142
31 38
17 39
1 40
1 41
26 42
8 43
26 44
1 45
11 46
37 47
1 48
49 90
2 50
1 51
30 52
1 53
1 54
...

result:

ok

Test #5:

score: 0
Accepted
time: 5ms
memory: 11952kb

input:

125 7750
17 50 7
72 112 7
92 14 4
18 99 5
115 55 9
96 10 5
98 16 4
116 76 9
58 28 8
37 80 4
10 102 3
20 92 7
12 104 5
92 106 7
109 48 6
125 56 6
20 47 3
40 80 6
67 32 2
37 21 7
48 117 6
33 41 7
93 10 3
13 114 6
68 25 1
109 94 2
36 118 6
58 3 7
40 104 6
40 76 1
118 91 7
55 93 2
44 48 2
27 99 8
79 10 ...

output:

12
1 12
2 14
3 4
4 89
5 18
6 18
7 10
8 12
9 18
10 14
2 11
12 14
13 14
14 125
2 15
16 108
3 17
18 125
14 19
20 89
18 21
4 22
23 39
2 24
18 25
14 26
6 27
28 39
4 29
12 30
12 31
5 32
12 33
14 34
10 35
18 36
4 37
38 108
39 125
8 40
5 41
12 42
1 43
16 44
12 45
18 46
18 47
4 48
14 49
16 50
2 51
3 52
4 53
...

result:

ok

Test #6:

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

input:

343 58653
54 265 9
188 61 10
120 35 7
35 12 9
315 68 3
188 334 7
22 2 7
138 28 9
194 314 9
39 87 8
162 291 2
224 79 7
271 331 6
271 38 2
260 343 14
41 204 1
48 295 2
53 195 9
322 332 10
53 38 4
9 257 9
293 119 7
281 149 10
209 177 10
290 57 6
127 124 6
317 201 3
215 109 6
182 195 3
75 276 8
168 92 7...

output:

18
1 8
2 145
3 12
4 10
2 5
6 42
7 42
8 42
9 52
10 145
11 12
12 62
12 13
14 92
12 15
1 16
17 32
12 18
19 21
10 20
21 42
9 22
8 23
24 42
24 25
2 26
12 27
7 28
2 29
6 30
31 52
32 40
2 33
2 34
24 35
2 36
9 37
10 38
12 39
40 62
41 105
42 145
12 43
10 44
12 45
2 46
7 47
10 48
42 49
10 50
42 51
52 145
10 5...

result:

ok

Test #7:

score: 0
Accepted
time: 170ms
memory: 12812kb

input:

500 124750
443 468 569963
305 222 835365
55 98 5648875
17 483 6871804
249 387 957143
262 188 5962213
276 44 1213886
113 429 5230975
25 336 3434848
489 27 8708218
446 126 6079086
430 164 4406225
12 85 4614009
153 346 633874
316 368 5101625
236 369 2292881
387 66 5274904
220 278 3980069
146 303 544564...

output:

9960452
25 336
1 5
2 63
3 25
3 4
5 6
6 10
2 7
3 8
2 9
10 13
2 11
3 12
13 26
1 14
6 15
2 16
3 17
6 18
3 19
1 20
21 25
6 22
6 23
2 24
26 40
1 27
6 28
26 29
3 30
2 31
3 32
1 33
3 34
1 35
1 36
2 37
13 38
1 39
40 54
2 41
3 42
2 43
1 44
3 45
6 46
25 47
5 48
2 49
2 50
2 51
2 52
2 53
54 98
3 55
40 56
1 57
3...

result:

ok

Test #8:

score: 0
Accepted
time: 24ms
memory: 12148kb

input:

256 32640
67 46 8826982
212 207 5853106
75 245 11953237
34 125 17259394
17 120 10969533
155 3 6675664
141 92 13332413
244 88 7639683
137 79 3970040
73 176 19125293
169 201 4299143
73 163 12142015
14 6 12113321
75 256 9291130
63 157 12832584
228 29 6772645
68 175 13691783
5 89 4302943
16 103 6727852
...

output:

26131854
138 155
1 75
2 10
3 19
4 14
5 10
6 138
6 7
3 8
5 9
10 128
11 58
3 12
13 14
14 19
15 61
10 16
17 72
5 18
19 61
17 20
21 24
22 75
2 23
24 50
25 47
10 26
10 27
6 28
15 29
30 32
25 31
32 50
6 33
25 34
35 75
1 36
37 91
19 38
10 39
40 47
22 41
40 42
17 43
6 44
45 91
46 61
47 61
21 48
37 49
50 65
...

result:

ok

Test #9:

score: 0
Accepted
time: 21ms
memory: 12456kb

input:

243 29403
29 23 3131302
11 3 4511503
12 185 16507040
115 35 13690920
31 170 6850162
116 51 4745664
144 112 14201854
39 63 10109135
120 78 11204668
183 78 7290363
40 107 16689635
67 136 93441
67 55 15947263
39 143 4693652
154 107 10604580
127 183 10496797
208 122 13041508
11 26 6647372
126 229 985041...

output:

21457553
148 120
1 6
2 46
3 120
4 10
3 5
6 120
4 7
3 8
9 15
10 57
11 120
12 59
13 57
6 14
15 148
3 16
17 120
6 18
11 19
20 115
11 21
15 22
23 36
24 120
3 25
15 26
27 36
15 28
12 29
30 58
6 31
10 32
3 33
15 34
4 35
36 148
3 37
3 38
6 39
40 83
6 41
15 42
6 43
11 44
6 45
46 56
11 47
24 48
6 49
6 50
6 5...

result:

ok

Test #10:

score: 0
Accepted
time: 171ms
memory: 11868kb

input:

499 124251
461 265 336966683
376 414 284212683
366 413 337970820
9 149 355258271
325 156 315832696
113 375 354577875
32 433 345627841
376 161 335785529
366 42 319451479
385 172 321004557
98 236 360767420
444 326 313089369
36 115 337424941
392 238 340807288
85 347 336353275
116 372 371769911
391 13 3...

output:

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

result:

ok

Test #11:

score: 0
Accepted
time: 171ms
memory: 12860kb

input:

500 124750
493 130 351043307
208 348 326179963
83 94 342055956
163 348 373258823
197 409 325293509
261 88 324333155
23 100 321384496
344 479 358400743
260 100 342652394
448 3 317675245
283 349 361779182
414 197 327194724
37 459 389772936
401 126 344352426
60 46 312990080
313 242 318912361
198 98 325...

output:

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

result:

ok

Test #12:

score: 0
Accepted
time: 166ms
memory: 13076kb

input:

500 124750
263 149 823
1 65 751
53 409 870
292 352 762
379 122 767
484 74 812
115 497 832
297 334 823
210 41 809
420 268 807
95 216 752
186 423 791
427 358 776
118 223 775
459 211 808
162 343 751
210 119 809
439 195 844
154 221 822
363 390 822
339 270 807
153 15 837
426 330 773
354 315 762
317 303 7...

output:

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

result:

ok

Test #13:

score: 0
Accepted
time: 177ms
memory: 12784kb

input:

500 124750
24 277 336609231
189 48 329957751
130 307 334562839
150 5 350299699
130 306 338627627
391 416 326018518
297 489 326045958
156 153 333330346
154 482 339034861
492 259 323077166
370 5 333649013
258 204 324978731
64 228 352908115
58 244 340587477
429 419 321475204
151 143 325381408
248 38 33...

output:

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

result:

ok

Test #14:

score: 0
Accepted
time: 172ms
memory: 13100kb

input:

500 124750
384 14 425038468
192 260 675657326
292 198 23251605
1 463 124292609
231 2 178513186
300 408 50265695
320 78 81387545
90 190 923582754
498 409 916628446
420 166 299413262
23 339 542251129
5 237 493710510
251 6 12885827
444 8 440135613
242 173 686046528
30 301 61808439
264 60 642406301
248 ...

output:

40740713
204 246
1 441
2 230
3 417
4 440
5 394
6 161
7 161
8 138
9 39
10 129
11 283
12 296
13 120
14 449
15 39
16 213
17 101
18 275
19 287
20 459
21 412
22 230
23 148
24 224
25 408
26 349
27 132
28 320
29 293
30 228
31 239
32 220
33 200
34 321
35 274
36 388
37 350
38 353
39 103
38 40
41 253
42 383
4...

result:

ok

Test #15:

score: 0
Accepted
time: 166ms
memory: 12816kb

input:

500 124750
202 447 336741012
92 270 663436926
89 41 309047741
345 240 587182923
14 358 303518613
107 72 624877592
270 468 280136986
256 150 719953302
451 155 767165840
99 256 496809180
24 72 326743318
199 127 228787790
326 143 349499492
326 358 965377787
7 404 903718497
52 100 838914124
219 233 6663...

output:

46749755
132 408
1 285
2 330
3 295
4 85
5 182
6 111
7 252
8 100
9 318
10 451
11 361
12 206
2 13
14 67
15 228
16 121
17 249
18 450
19 203
20 172
21 321
22 215
23 322
24 324
25 453
26 39
27 466
28 206
29 380
30 434
31 232
32 348
33 208
34 389
35 83
36 465
37 431
38 220
39 490
40 434
41 253
42 261
43 8...

result:

ok

Test #16:

score: 0
Accepted
time: 168ms
memory: 12664kb

input:

500 124750
473 261 267443376
438 59 540452305
197 481 350240182
99 51 255230904
235 459 810428481
153 287 364214007
316 333 252023630
141 84 602938702
390 38 840115034
80 121 768116227
188 336 316269065
246 63 532812842
159 9 600703944
39 5 983000839
342 140 197843308
377 410 592004365
15 135 203770...

output:

37971004
192 137
1 286
2 69
3 370
4 122
5 246
6 356
7 179
8 56
9 499
10 218
11 166
12 356
13 105
14 20
15 53
16 443
17 383
18 141
19 485
20 455
21 272
22 122
23 435
24 356
25 459
26 64
27 307
28 86
29 94
30 211
31 213
32 46
33 192
34 100
35 119
36 178
37 438
38 479
39 128
40 269
41 476
42 372
43 61
...

result:

ok

Test #17:

score: 0
Accepted
time: 167ms
memory: 13172kb

input:

500 124750
326 216 865974032
342 145 899173929
326 17 95028303
270 362 420387995
495 164 932329585
69 201 348342984
189 89 860429924
171 314 195039912
302 399 8710790
495 328 336795245
227 164 322999677
49 444 746557
349 7 208544655
134 150 54925387
305 347 75313895
367 143 447473444
485 95 28555430...

output:

41635892
291 226
1 257
2 324
3 96
4 202
5 238
6 183
7 367
8 76
9 211
10 44
11 204
12 224
13 52
14 256
15 290
16 245
17 294
18 351
19 268
20 122
21 378
22 357
23 251
24 151
25 440
26 221
27 286
28 349
29 318
30 359
31 354
32 470
33 287
31 34
35 400
36 344
37 128
38 287
39 484
40 409
41 133
42 187
43 ...

result:

ok

Test #18:

score: 0
Accepted
time: 167ms
memory: 13184kb

input:

500 124750
50 103 169644033
350 25 733427517
360 329 325740461
491 358 863234848
246 109 425224534
3 106 362191273
495 24 283250521
375 458 893528294
364 423 711146313
150 15 835762784
150 331 623176965
405 70 386196999
65 177 211037895
445 279 242692580
340 109 410272265
173 268 334368275
263 447 7...

output:

42973111
1 192
2 461
3 182
4 26
5 491
6 61
7 192
8 279
9 437
10 134
11 154
12 227
13 133
14 377
15 93
16 410
17 196
18 186
19 383
20 249
21 282
22 169
23 380
24 59
25 432
26 457
27 71
28 414
29 37
30 170
31 292
32 268
33 220
34 79
35 472
36 468
37 176
38 387
39 412
40 422
41 107
42 236
43 73
44 428
...

result:

ok

Test #19:

score: 0
Accepted
time: 2ms
memory: 12048kb

input:

10 45
1 8 852386547
1 6 896725964
1 7 398330288
10 7 745956332
4 3 77447028
7 9 397520615
8 6 802361809
4 7 772673968
1 2 174055957
10 5 103665853
4 9 485247227
4 2 258249623
9 2 728388812
7 8 106246975
8 10 888960723
8 2 598923263
7 6 905994898
4 5 576321126
3 8 770589879
10 1 496876256
1 5 8349896...

output:

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

result:

ok

Test #20:

score: 0
Accepted
time: 0ms
memory: 11852kb

input:

10 45
2 8 114030772
9 6 370138763
4 1 649979236
9 10 595837331
1 3 398896234
3 4 916893101
7 2 927242800
9 8 85375078
6 4 628048978
10 1 62710986
10 8 198495177
2 9 620688683
3 2 817822965
1 7 475778205
2 6 444985984
7 4 791328882
5 10 714881954
2 4 92374685
9 3 509479385
7 5 472012838
8 6 515456030...

output:

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

result:

ok

Test #21:

score: 0
Accepted
time: 0ms
memory: 11792kb

input:

10 45
3 2 411603519
2 1 530222805
5 8 401884056
2 8 629138281
9 4 279043576
2 7 355714714
9 1 16302019
2 4 366691234
3 6 641321323
9 2 102923145
5 10 471322247
9 3 276998611
4 5 140929491
10 3 625579125
1 4 525865610
6 7 200122395
7 8 412320889
10 7 215063702
1 6 950279547
5 9 122526015
10 2 4510894...

output:

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

result:

ok

Test #22:

score: 0
Accepted
time: 81ms
memory: 9932kb

input:

500 499
489 250 911816417
42 183 576360685
413 27 603166565
340 6 740155781
282 267 886335166
202 36 846414216
70 273 536335885
94 400 679118131
186 292 325240258
68 99 356682437
93 324 130056528
202 490 975232337
374 459 608441376
3 217 840906454
40 367 175667143
306 120 471709580
120 215 691146618...

output:

32760257077
211 378
1 55
2 54
3 334
4 335
5 22
6 340
7 308
8 53
9 75
10 194
11 67
12 426
13 111
14 123
15 381
16 357
17 153
18 325
19 445
20 152
21 489
22 350
23 71
24 452
25 299
26 272
27 413
28 81
29 447
30 311
31 129
32 461
33 497
34 465
35 91
36 202
37 357
38 275
39 325
40 428
41 55
42 226
43 48...

result:

ok

Test #23:

score: 0
Accepted
time: 81ms
memory: 12100kb

input:

499 498
115 438 632124054
265 323 590854058
205 408 640558868
144 190 863488857
496 129 397594428
70 111 349959309
263 29 495455138
401 358 394611413
489 425 957892531
142 332 389151686
133 38 15576349
228 379 52447487
320 283 49471342
437 390 652438631
51 37 41057275
473 6 599793848
313 450 3796515...

output:

33794638693
63 279
1 216
2 143
3 321
4 55
5 351
6 473
7 83
8 454
9 11
10 453
11 51
12 476
13 444
14 175
15 365
16 149
17 124
18 231
19 385
15 20
16 21
22 449
23 151
24 408
25 435
2 26
27 418
28 355
29 263
30 64
3 31
32 365
33 317
34 252
35 90
5 36
37 51
38 133
15 39
40 58
41 372
42 440
43 162
44 420...

result:

ok

Test #24:

score: 0
Accepted
time: 0ms
memory: 12052kb

input:

3 2
2 3 255741785
2 1 160496570

output:

416238355
2 3
1 2

result:

ok

Test #25:

score: 0
Accepted
time: 0ms
memory: 11820kb

input:

100 99
65 34 441414148
22 95 527003384
74 85 80656954
10 64 893508913
32 42 110880114
91 74 519216315
68 70 233703686
20 92 370689334
39 48 209550382
52 1 846701392
94 10 214278326
84 99 574671008
21 43 936333553
92 75 889270962
55 69 989214957
67 83 121514850
21 87 989248231
2 26 935422061
80 65 95...

output:

14316191893
43 80
1 52
2 68
3 22
4 35
5 75
6 40
7 97
8 26
9 80
10 94
11 67
9 12
13 45
14 72
15 81
16 40
17 67
18 34
19 47
20 92
21 43
22 89
23 29
24 97
7 25
2 26
27 75
28 54
25 29
30 82
2 31
2 32
33 75
34 65
34 35
36 84
37 57
17 38
18 39
40 63
41 56
32 42
2 44
11 45
28 46
37 47
39 48
49 91
11 50
21 ...

result:

ok

Test #26:

score: 0
Accepted
time: 81ms
memory: 11832kb

input:

500 499
84 429 1000000000
221 147 1000000000
32 342 1000000000
215 314 1000000000
119 179 1000000000
108 435 1000000000
387 152 1000000000
205 212 1000000000
269 394 1000000000
275 474 1000000000
448 350 1000000000
359 365 1000000000
296 402 1000000000
224 73 1000000000
109 499 1000000000
349 351 10...

output:

499000000000
428 401
1 394
2 181
3 393
4 284
5 141
6 190
7 232
8 294
9 275
10 39
11 492
12 437
13 282
14 79
15 34
16 224
17 304
18 137
19 462
17 20
21 98
22 30
23 52
24 40
25 135
26 230
27 192
28 120
29 445
30 337
31 418
32 382
33 333
34 293
35 311
36 389
37 363
38 58
39 217
40 267
41 160
42 196
43 ...

result:

ok

Test #27:

score: 0
Accepted
time: 0ms
memory: 9996kb

input:

2 1
1 2 1000000000

output:

1000000000
1 2

result:

ok

Test #28:

score: 0
Accepted
time: 160ms
memory: 12808kb

input:

500 112375
215 411 405573103
483 202 429632204
49 152 641147973
424 223 313115211
102 480 37625732
135 498 287528728
11 372 755681501
60 331 159823988
227 78 518118983
185 167 755911454
130 269 191205737
55 152 445920241
152 407 834003692
113 185 512296966
396 177 680449942
371 473 23006247
125 47 6...

output:

46093603
18 162
1 477
2 401
3 60
4 162
5 142
6 374
7 427
8 105
9 355
10 60
11 255
6 12
13 359
14 251
15 162
16 75
17 240
19 38
20 345
21 108
22 212
23 96
24 358
25 88
4 26
27 207
28 54
29 82
30 309
31 246
32 357
33 312
3 34
35 266
36 397
37 127
38 162
39 334
40 318
41 117
42 226
43 333
44 299
45 157...

result:

ok

Test #29:

score: 0
Accepted
time: 127ms
memory: 12780kb

input:

500 62254
428 55 673055918
215 410 148588730
75 376 213490326
263 232 596161560
64 398 839662234
170 473 426273328
221 214 725162854
8 382 656895268
407 251 472418635
285 64 454705591
238 432 602541117
340 392 788352611
68 108 508348843
328 297 694088955
25 51 861300749
255 242 119135283
270 496 758...

output:

93031648
209 256
1 82
2 269
3 35
4 407
5 189
6 319
7 406
8 254
9 241
10 155
11 170
12 336
13 208
14 33
15 225
16 145
17 352
18 42
19 214
20 100
21 336
22 482
23 375
24 189
25 88
26 479
27 321
28 51
21 29
30 125
31 121
32 433
33 174
34 407
35 165
36 328
37 85
38 236
39 104
40 312
39 41
42 101
43 230
...

result:

ok

Test #30:

score: 0
Accepted
time: 96ms
memory: 12112kb

input:

500 24926
202 335 87826903
145 367 249043133
296 266 234995839
400 252 908643196
247 365 670330835
365 312 417431159
400 490 824592807
403 123 901931953
226 363 926551074
453 488 215017578
144 225 960418940
205 69 506382361
489 133 278874199
468 146 198386148
222 216 496678072
349 342 300581775
158 ...

output:

195696372
35 144
1 245
2 3
3 398
4 233
5 471
6 419
7 387
8 70
9 109
10 144
11 397
12 256
13 98
14 318
15 225
16 160
17 44
18 34
19 281
20 156
21 326
22 291
23 482
24 216
2 25
26 383
27 133
28 317
29 247
30 126
31 303
32 97
33 427
34 309
36 115
37 41
38 341
39 294
40 335
41 148
42 156
43 253
18 44
45...

result:

ok

Test #31:

score: 0
Accepted
time: 84ms
memory: 12232kb

input:

500 7425
81 342 810238489
27 14 908239231
273 373 287258613
253 432 563166711
278 199 932063977
373 100 814478323
426 105 374600399
60 251 16098593
166 201 655716982
456 168 66673197
30 121 595035829
170 431 817407488
173 126 660336891
226 220 24714054
386 278 322211588
16 12 54069814
406 341 169888...

output:

635007062
314 392
1 101
2 304
3 384
4 193
5 409
6 377
7 345
8 414
9 205
10 145
11 125
12 16
13 471
14 311
15 215
16 38
3 17
18 409
19 146
20 317
21 488
22 220
23 278
24 49
25 312
26 494
27 61
28 215
29 412
30 414
31 108
32 409
33 76
34 211
35 261
36 83
37 97
38 487
39 193
40 144
41 497
42 381
43 90
...

result:

ok

Test #32:

score: 0
Accepted
time: 86ms
memory: 11804kb

input:

500 3780
366 95 394951594
6 366 802428678
87 202 504216135
478 261 621604711
108 261 136061971
119 31 234424551
265 405 267843581
403 307 789242971
80 208 9360049
23 151 536803184
35 208 113064121
17 442 868266027
419 438 844536791
32 31 683803313
420 211 824670471
13 227 45871642
312 124 865431657
...

output:

1442276057
69 97
1 8
2 307
3 262
4 470
5 471
6 419
7 470
8 455
9 88
10 246
11 399
12 289
13 28
14 224
15 399
16 189
17 237
18 51
19 219
20 183
21 399
22 318
23 345
24 302
25 147
26 314
27 320
28 136
29 399
30 279
31 467
32 247
33 491
34 121
35 298
36 222
37 314
38 173
39 73
40 264
41 174
42 403
43 2...

result:

ok

Test #33:

score: 0
Accepted
time: 84ms
memory: 11832kb

input:

499 7413
453 253 365177445
73 82 676484140
472 167 572434873
292 454 881725762
351 448 816134721
11 74 99817392
3 152 899527423
343 267 283437304
317 368 658958165
302 12 545721809
25 252 826963352
238 102 653491178
49 405 499572039
7 95 632608197
337 427 400888272
291 307 41716753
97 222 154670567
...

output:

649053601
17 109
1 267
2 47
3 391
4 140
5 346
6 89
6 7
8 452
9 248
10 362
11 487
12 278
13 167
14 433
15 260
16 225
18 411
19 273
20 353
21 196
22 377
23 380
24 366
25 212
26 234
27 88
28 294
29 483
30 374
31 246
32 71
33 225
34 170
35 209
36 391
37 350
38 92
39 340
40 379
41 162
42 93
40 43
44 336
...

result:

ok

Test #34:

score: 0
Accepted
time: 83ms
memory: 11852kb

input:

500 998
357 37 615878375
355 220 158580531
459 81 359502925
464 212 517883144
423 87 670629712
144 226 399414281
138 360 72111835
317 390 728659672
445 53 690042117
451 15 711431052
279 52 747492925
292 177 846356995
468 170 50253940
282 237 706952552
336 337 720468410
259 156 356422088
170 428 7889...

output:

4441235878
247 443
1 55
2 247
3 152
4 335
5 241
6 285
7 333
8 53
9 75
10 194
11 159
12 426
13 111
14 263
15 263
16 114
17 54
18 54
19 445
20 152
21 49
22 434
23 266
24 112
25 299
26 272
27 413
28 81
29 447
30 311
31 263
32 461
33 477
34 465
35 98
36 473
37 224
38 275
39 237
40 328
41 55
42 422
23 43...

result:

ok

Test #35:

score: 0
Accepted
time: 84ms
memory: 12116kb

input:

500 1489
251 283 336346626
268 345 197720766
140 346 368809904
481 154 810739392
283 82 466080515
316 88 398780699
337 220 873542149
220 300 789681082
495 292 836172158
122 274 642176095
310 404 583796616
78 397 116645447
112 95 526153997
252 242 538439401
199 155 108445198
221 142 170150171
14 123 ...

output:

3335034921
294 392
1 140
2 247
3 152
4 133
5 251
6 285
7 333
8 53
9 491
10 179
11 451
12 33
13 111
14 263
15 315
16 114
17 389
18 54
19 445
20 310
21 49
22 434
23 404
24 83
25 379
26 272
27 286
28 81
29 72
30 327
31 133
32 494
33 477
34 229
35 98
36 473
37 224
38 115
39 237
40 444
41 382
42 226
23 4...

result:

ok

Test #36:

score: 0
Accepted
time: 81ms
memory: 11844kb

input:

500 1983
390 46 325419612
352 173 956124303
21 49 87118967
434 293 181309943
1 322 966816097
374 363 405786700
387 462 663285952
221 431 114079525
386 364 919848935
364 377 588992539
64 111 763731869
239 380 467883942
37 62 914591429
299 194 812634844
41 352 774415821
166 259 622646113
439 393 67889...

output:

2538508929
284 91
1 39
2 247
3 152
4 158
5 22
6 110
7 278
8 53
9 33
10 91
11 159
12 33
13 111
14 263
15 198
16 101
17 389
18 138
19 337
20 87
21 49
22 35
23 266
24 425
25 368
26 272
27 286
28 81
29 447
30 91
31 263
32 461
33 78
34 208
35 91
36 473
37 224
38 177
39 325
40 328
41 286
42 226
43 482
44 ...

result:

ok

Test #37:

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

input:

500 2472
26 259 300350996
483 172 113333131
223 2 360381923
291 42 637617104
350 300 449910518
26 163 611186507
472 365 189750058
343 110 448614498
28 77 642365375
65 5 815239874
76 259 900880611
371 17 711438797
489 79 89712650
476 225 198266248
277 357 648844147
29 235 887755827
343 90 437780951
1...

output:

1987249621
91 35
1 454
2 247
3 152
4 305
5 22
6 285
7 240
8 53
9 491
10 91
11 159
12 33
13 285
14 263
15 198
16 101
17 389
18 240
19 445
20 310
21 49
22 35
23 266
24 112
25 379
26 272
27 458
28 182
29 72
30 91
31 263
32 461
33 78
34 180
36 473
37 224
38 177
1 39
40 500
41 286
42 395
43 482
44 500
45...

result:

ok

Test #38:

score: 0
Accepted
time: 84ms
memory: 11928kb

input:

500 2957
465 121 968799590
205 395 23464769
131 186 292946801
138 399 632201011
404 23 254378437
13 40 610881364
389 61 43222378
118 164 621828299
380 310 876201865
393 260 582208954
360 43 303515652
278 449 587854697
204 107 450595359
312 165 693035862
239 311 426200604
368 347 875502366
456 215 23...

output:

1720003538
417 285
1 454
2 247
3 51
4 259
5 272
6 285
7 157
8 293
9 121
10 194
11 159
12 33
13 256
14 263
15 263
16 114
17 389
18 138
19 445
20 87
21 49
22 314
23 266
24 83
25 335
26 272
27 458
28 424
29 388
30 224
31 263
32 333
33 477
34 208
35 91
36 448
37 370
38 115
1 39
40 500
41 114
42 59
43 36...

result:

ok

Test #39:

score: 0
Accepted
time: 85ms
memory: 11852kb

input:

500 3445
260 191 387557630
460 96 437785661
414 157 788571963
467 204 422896812
275 38 82565240
154 319 186508009
400 94 679118131
347 180 401381454
98 147 462666191
112 84 164496728
122 77 698092305
217 295 71771915
430 403 650087807
156 396 553244458
357 16 110311943
467 130 833512070
38 352 62662...

output:

1483608654
454 379
1 454
2 247
3 51
4 335
5 272
6 110
7 157
8 293
9 193
10 194
11 451
12 33
13 470
14 109
15 413
16 114
17 389
18 138
19 445
20 310
21 49
22 314
23 266
24 421
25 379
26 272
27 361
28 379
29 388
30 193
31 129
32 333
33 477
12 34
35 91
36 448
37 370
38 115
1 39
40 328
41 80
42 59
43 48...

result:

ok

Test #40:

score: 0
Accepted
time: 0ms
memory: 12012kb

input:

17 30
16 4 554374432
9 2 215208399
5 3 513409742
6 14 506215306
7 13 537124830
16 15 143014337
17 10 816248153
1 7 242153020
6 2 37119022
12 8 137831502
16 11 237336357
9 1 881761968
14 12 318095050
8 1 208032501
6 10 190870607
15 14 346948152
13 3 846045895
3 11 694053968
14 17 419599539
6 5 208704...

output:

1817998100
1 3
2 12
3 4
3 5
2 6
1 7
1 8
2 9
6 10
11 17
8 12
3 13
14 17
15 16
11 16
3 17

result:

ok

Test #41:

score: 0
Accepted
time: 0ms
memory: 9776kb

input:

17 43
4 3 506147731
2 6 37119022
3 5 513409742
6 12 516377635
4 15 675716898
17 11 219922878
7 1 242153020
13 4 133275785
16 3 940198937
8 4 956435856
4 16 554374432
17 14 419599539
14 16 933384890
14 4 298309896
2 12 8225926
5 2 713365483
14 12 318095050
12 8 225374527
17 3 189766466
7 13 537124830...

output:

1381676961
14 12
1 8
2 12
3 17
4 14
5 14
2 6
7 9
8 12
2 9
6 10
11 17
4 13
14 15
15 16
15 17

result:

ok

Test #42:

score: 0
Accepted
time: 1ms
memory: 9744kb

input:

17 56
15 12 174616807
14 12 318095050
4 8 956435856
8 1 208032501
6 14 506215306
7 9 112445395
3 16 940198937
9 1 881761968
15 16 143014337
17 10 816248153
5 3 513409742
13 5 110880114
12 8 225374527
2 16 286986530
14 16 441504628
7 1 242153020
6 10 190870607
2 9 215208399
6 13 116383718
15 14 34694...

output:

793723258
15 12
1 12
2 12
3 17
4 6
5 6
2 6
7 9
8 12
2 9
6 10
11 17
6 13
12 14
15 16
15 17

result:

ok

Test #43:

score: 0
Accepted
time: 0ms
memory: 12084kb

input:

17 65
6 17 197550393
15 14 346948152
17 5 893508913
12 15 174616807
7 16 324584324
9 12 973708325
16 11 237336357
3 11 436207833
3 1 389872647
7 2 580944484
13 7 537124830
11 17 833923911
15 4 675716898
14 17 419599539
12 11 905778941
14 4 298309896
6 2 37119022
16 15 143014337
11 7 519216315
4 5 45...

output:

679248086
6 2
1 12
3 13
4 6
5 6
7 9
8 12
2 9
6 10
11 13
2 12
6 13
12 14
12 15
2 16
6 17

result:

ok

Test #44:

score: 0
Accepted
time: 1ms
memory: 9812kb

input:

10 44
7 1 517400951
10 3 471593384
1 3 547761444
7 8 791370537
4 5 369007550
2 5 564183890
3 9 965720849
2 6 130399919
6 4 756732023
9 8 902540844
6 9 760427451
10 5 162352859
3 2 908640945
10 8 531885690
10 2 113869678
9 5 196323620
5 1 460453279
1 10 660682369
1 2 359263377
8 5 112464084
6 8 17956...

output:

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

result:

ok

Test #45:

score: 0
Accepted
time: 169ms
memory: 13076kb

input:

500 124750
473 98 225
91 199 248
16 76 249
203 221 249
431 332 256
184 406 264
324 101 263
197 10 229
275 267 239
240 23 260
461 74 252
169 242 266
197 49 253
70 307 250
33 235 235
429 201 249
470 303 236
239 250 235
377 461 247
46 47 258
337 204 245
162 287 256
44 256 239
55 32 257
65 273 252
398 2...

output:

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

result:

ok

Test #46:

score: 0
Accepted
time: 171ms
memory: 13132kb

input:

500 124750
304 88 436
94 161 421
447 321 442
404 288 462
137 200 420
195 380 453
451 351 444
402 232 423
344 60 439
286 379 452
149 388 484
468 310 445
6 409 429
130 335 410
265 323 440
146 181 442
398 185 451
336 242 455
303 237 436
441 330 428
314 428 468
97 5 456
45 295 421
231 104 443
360 61 444...

output:

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

result:

ok
English 繁體中文 简体中文

伺服器時間: 2024-11-29 20:43:19 | 開源專案