QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#33521 | #4061. 垃圾回收 | Backlight | 100 ✓ | 183ms | 34020kb | C++17 | 2.1kb | 2022-06-03 00:07:03 | 2022-06-03 00:07:03 |
Judging History
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";
}
詳細信息
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