QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#33521#4061. 垃圾回收Backlight100 ✓183ms34020kbC++172.1kb2022-06-03 00:07:032022-06-03 00:07:03

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-06-03 00:07:03]
  • 评测
  • 测评结果:100
  • 用时:183ms
  • 内存:34020kb
  • [2022-06-03 00:07:03]
  • 提交

answer

#include <bits/stdc++.h>

#define CPPIO std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
#define freep(p) p ? delete p, p = nullptr, void(1) : void(0)

#ifdef BACKLIGHT
#include "debug.h"
#else
#define logd(...) ;
#endif

using i64 = int64_t;
using u64 = uint64_t;

void solve_case(int Case);

int main(int argc, char* argv[]) {
  CPPIO;
  int T = 1;
  // std::cin >> T;
  for (int t = 1; t <= T; ++t) {
    solve_case(t);
  }
  return 0;
}

void solve_case(int Case) {
  int n, m, q;
  std::cin >> n >> m >> q;

  std::vector<std::pair<int, int>> e(m);
  for (int i = 0; i < m; ++i) {
    int x, y;
    std::cin >> x >> y;
    --x, --y;
    e[i] = {x, y};
  }

  std::vector<bool> flag(m, false);
  std::vector<std::pair<int, int>> op(q);
  for (int i = 0; i < q; ++i) {
    std::string s;
    std::cin >> s;
    if (s[0] == 'G') {
      op[i] = {1, -1};
    } else {
      int x;
      std::cin >> x;
      --x;
      op[i] = {2, x};
      flag[x] = true;
    }
  }

  std::vector<int> a(n);
  for (int i = 0; i < n; ++i) {
    std::cin >> a[i];
  }

  std::vector<int> f(n);
  std::vector<i64> sum(n);
  for (int i = 0; i < n; ++i) {
    f[i] = i;
    sum[i] = a[i];
  }
  std::function<int(int)> find = [&](int x) -> int {
    if (x != f[x])
      f[x] = find(f[x]);
    return f[x];
  };
  std::function<void(int, int)> merge = [&](int x, int y) -> void {
    x = find(x);
    y = find(y);
    if (x == y)
      return;
    f[x] = y;
    sum[y] += sum[x];
  };

  for (int i = 0; i < m; ++i) {
    if (!flag[i]) {
      merge(e[i].first, e[i].second);
    }
  }

  u64 ans = 0, cnt = 0;
  for (int i = q - 1; i >= 0; --i) {
    ++cnt;
    auto [t, x] = op[i];
    if (t == 1) {
      int rt = find(0);
      ans += sum[rt] * cnt;
      cnt = 0;
    } else {
      merge(e[x].first, e[x].second);
    }
  }
  ++cnt;
  int rt = find(0);
  ans += sum[rt] * cnt;

  for (int i = 0; i < n; ++i) {
    if (find(i) != find(0) && find(i) == i) {
      ans += sum[i] * cnt;
    }
  }

  std::cout << ans << "\n";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 5
Accepted
time: 3ms
memory: 3548kb

input:

500 500 500
184 185
77 98
113 112
26 19
204 205
17 39
62 87
175 176
116 115
89 77
230 228
96 77
55 87
52 70
26 5
28 24
101 205
101 192
17 7
92 54
86 85
101 190
55 73
159 158
50 44
125 124
51 100
101 210
8 31
61 87
65 68
146 145
21 9
101 211
82 74
86 63
18 8
56 88
172 173
76 84
101 240
117 116
101 21...

output:

2435016993570

result:

ok single line: '2435016993570'

Test #2:

score: 5
Accepted
time: 3ms
memory: 3664kb

input:

500 500 500
124 111
106 142
63 422
254 432
434 253
426 470
151 89
198 364
63 240
362 207
288 302
105 479
324 14
171 277
72 84
379 102
194 30
262 97
179 244
206 9
209 370
28 441
230 426
251 86
432 187
38 236
411 243
250 77
402 290
485 77
394 393
72 385
329 248
227 128
289 401
104 41
22 242
79 342
487...

output:

72036425

result:

ok single line: '72036425'

Test #3:

score: 5
Accepted
time: 3ms
memory: 3800kb

input:

3000 3000 3000
1395 1396
383 546
42 51
527 474
535 467
830 829
323 519
498 489
986 985
601 1422
876 875
957 956
1270 1268
672 671
496 457
410 370
899 898
369 347
214 17
159 176
1426 1424
601 1359
319 362
327 550
170 111
475 318
34 61
196 11
442 447
1190 1191
677 676
178 132
654 653
489 365
400 318
1...

output:

87606832984113

result:

ok single line: '87606832984113'

Test #4:

score: 5
Accepted
time: 3ms
memory: 3656kb

input:

3000 3000 3000
1299 2727
448 2363
319 2395
805 1068
2784 1395
1748 882
152 1297
555 871
1329 1218
2339 1964
622 671
818 1138
855 861
148 810
1657 773
70 1702
1724 2908
27 485
2899 68
983 2659
2527 194
2614 1318
1181 510
1462 682
2291 262
1872 222
2535 2778
1491 213
840 2681
105 494
283 188
2977 317
...

output:

1978325137

result:

ok single line: '1978325137'

Test #5:

score: 5
Accepted
time: 4ms
memory: 3800kb

input:

3000 3000 3000
2110 2691
2443 2360
1825 900
762 1411
589 477
248 2442
2164 2833
1482 2569
2205 1639
793 986
411 1980
1929 2507
1548 2703
2484 141
203 2332
1981 294
2623 402
1006 856
250 2589
1842 2992
954 332
283 2264
2843 1828
1181 37
2378 1763
1625 1697
1028 2438
1571 178
373 579
2677 161
970 472
...

output:

1571881597

result:

ok single line: '1571881597'

Test #6:

score: 5
Accepted
time: 4ms
memory: 3728kb

input:

5000 5000 5000
2062 2063
38 27
1141 1140
86 355
471 154
741 903
678 763
2295 2296
724 886
1430 1429
1894 1895
1789 1790
2229 2230
459 29
274 285
875 560
993 990
842 697
832 938
1001 2287
1244 1243
804 782
1911 1912
1001 2188
874 749
174 497
547 861
826 993
2470 2471
1776 1777
945 682
2143 2144
1148 ...

output:

239951095050347

result:

ok single line: '239951095050347'

Test #7:

score: 5
Accepted
time: 5ms
memory: 3872kb

input:

5000 5000 5000
832 755
45 87
1899 1900
2123 2121
1099 1098
259 271
612 581
2328 2329
2258 2256
283 148
2144 2142
2205 2206
665 860
991 976
1043 1042
1999 2000
689 696
937 641
1001 2199
14 297
549 501
691 957
688 508
613 566
1497 1496
301 262
1001 2490
348 219
213 400
50 423
625 799
37 416
1001 2005
...

output:

239965821763391

result:

ok single line: '239965821763391'

Test #8:

score: 5
Accepted
time: 5ms
memory: 3808kb

input:

5000 5000 5000
2109 650
3804 3479
2359 2973
1794 2953
2126 606
1835 4583
738 4577
628 3504
1768 2178
3828 2945
1217 2213
1949 1482
371 3559
3310 1016
4559 1692
4771 2433
3817 3638
3931 2666
3380 4181
3505 2868
1179 857
2789 4435
4777 3010
3232 70
4394 1417
1531 2394
1816 3084
2712 4679
1087 1238
442...

output:

6306644978

result:

ok single line: '6306644978'

Test #9:

score: 5
Accepted
time: 1ms
memory: 3772kb

input:

5000 5000 5000
1216 3614
4903 2284
353 4183
4046 3105
1931 4496
631 3359
1750 4305
556 10
2236 87
4474 1968
4711 1739
548 3147
64 2402
1646 347
105 59
978 1729
2205 132
4126 4845
3538 1702
2660 2306
1710 1996
4266 380
2631 1432
4464 1129
2289 2918
988 2381
308 1039
4385 1348
2428 4136
4291 916
223 3...

output:

2983376195

result:

ok single line: '2983376195'

Test #10:

score: 5
Accepted
time: 4ms
memory: 3800kb

input:

5000 5000 5000
117 2547
1076 4786
1861 4659
3521 2716
4095 2728
2203 1261
211 3895
2462 3405
390 1267
1016 4080
2202 1889
3022 662
4540 2412
3981 2931
3997 1937
3545 4480
1578 1068
481 232
4468 18
1000 2628
4377 2213
54 3624
2985 859
1950 2172
3825 1447
3502 2363
1828 2047
1793 3751
533 76
2952 3091...

output:

5456996068

result:

ok single line: '5456996068'

Test #11:

score: 5
Accepted
time: 82ms
memory: 9424kb

input:

200000 199999 200000
139560 136635
2663 2662
102213 1
35212 35211
175419 134038
174508 173163
84038 1
180209 138931
154049 145884
97045 1
165666 150113
194184 180687
110551 1
21818 21817
147687 137487
8572 8571
178911 157857
84569 1
16686 16685
28671 28670
117213 1
57327 57326
148424 136297
32693 32...

output:

537759496325925005

result:

ok single line: '537759496325925005'

Test #12:

score: 5
Accepted
time: 83ms
memory: 9472kb

input:

200000 199999 200000
1258 1257
155976 154044
148087 139901
105574 1
26878 26877
170352 147886
129165 1
113998 1
148014 147223
193002 157434
46266 46265
123282 1
27653 27652
146321 145772
180331 159312
60754 60753
79646 1
115529 1
54428 54427
16311 16310
79317 1
21424 21423
161699 146202
178343 14514...

output:

630004010321485712

result:

ok single line: '630004010321485712'

Test #13:

score: 5
Accepted
time: 76ms
memory: 9472kb

input:

200000 199999 200000
138746 136058
161958 157996
58435 58434
91366 1
199711 174617
24736 24735
67143 1
159451 138833
26636 26635
66990 1
4415 4414
59592 59591
125033 1
156469 136147
108134 1
166139 154638
43446 43445
65601 65600
134951 134735
158816 156286
28325 28324
112505 1
196228 161971
117580 1...

output:

642833233492616875

result:

ok single line: '642833233492616875'

Test #14:

score: 5
Accepted
time: 67ms
memory: 9548kb

input:

200000 199999 200000
130424 1
6086 6085
137523 133415
158998 135779
10603 10602
163913 155584
178632 160756
149845 138057
108897 1
20835 20834
197231 191596
156430 148442
163956 137927
68480 1
47437 47436
59429 59428
81504 1
175707 171695
88118 1
75064 1
112397 1
123087 1
83508 1
172526 163620
9298 ...

output:

601404746215544337

result:

ok single line: '601404746215544337'

Test #15:

score: 5
Accepted
time: 77ms
memory: 10088kb

input:

200000 200000 200000
24569 31567
86565 86566
40001 78742
46063 46062
40001 94992
15604 16778
24501 39366
18840 6406
66342 66341
14428 5004
97850 97848
79327 79328
40001 77106
34253 20873
35178 39404
34222 36420
18960 330
35989 29616
20152 38433
84535 84536
28646 38350
40001 87075
40001 80106
2975 11...

output:

380740304737962037

result:

ok single line: '380740304737962037'

Test #16:

score: 5
Accepted
time: 87ms
memory: 9420kb

input:

200000 200000 200000
57394 96464
95490 123487
36469 157938
22908 40433
169819 33255
34588 138652
89733 93538
94604 169647
50378 119404
71407 180747
164598 149983
118937 30439
108229 130923
141137 121035
82412 22292
122198 171477
54737 169394
98007 167351
152270 50671
185530 40246
7218 180429
185686 ...

output:

167665675

result:

ok single line: '167665675'

Test #17:

score: 5
Accepted
time: 171ms
memory: 15784kb

input:

400000 400000 400000
26709 119051
233279 190525
297453 104091
93960 191543
115102 144022
371016 304366
213391 164015
160523 232263
236749 224418
334334 123376
90695 375210
300787 280533
133331 49032
192738 291116
294440 89731
64354 111211
186850 215394
210996 24524
251522 52212
144697 237904
337771 ...

output:

426087823

result:

ok single line: '426087823'

Test #18:

score: 5
Accepted
time: 180ms
memory: 15780kb

input:

400000 400000 400000
12002 122852
84489 115481
337605 261192
17850 214531
380366 370033
355744 264293
339896 182188
394240 343718
230771 37911
355348 222783
300064 317607
203142 336573
175766 44579
178809 393539
296033 206630
263552 326406
268221 332449
124325 73679
245151 190038
100836 231677
11601...

output:

25685188551537

result:

ok single line: '25685188551537'

Test #19:

score: 5
Accepted
time: 183ms
memory: 15872kb

input:

400000 400000 400000
38512 216254
102995 375030
234652 275189
341740 46030
12926 196045
83576 248413
233698 200361
252150 79364
57497 18701
184873 179086
109433 170404
129689 16805
75098 207421
356368 287450
130329 347721
230046 76193
182296 192607
61846 355538
47292 184761
32782 249642
102766 87348...

output:

7670714553817

result:

ok single line: '7670714553817'

Test #20:

score: 5
Accepted
time: 137ms
memory: 34020kb

input:

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

output:

15569619841999800000

result:

ok single line: '15569619841999800000'

Extra Test:

score: 0
Extra Test Passed