QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#578771 | #9349. Exchanging Gifts | Yukari# | TL | 0ms | 3704kb | C++20 | 1.3kb | 2024-09-20 21:12:58 | 2024-09-20 21:12:59 |
Judging History
answer
#pragma GCC optimize(3)
#include <cstdio>
#include <map>
#include <vector>
using namespace std;
typedef long long ll;
int read() {
int x = 0;
char c = getchar();
for (; c < '0' || c > '9'; c = getchar());
for (; c >= '0' && c <= '9'; c = getchar())
x = (x << 1) + (x << 3) + (c ^ 48);
return x;
}
int main() {
int t = read();
while (t--) {
int n = read();
vector<map<int, ll>> vec(n);
for (int i = 0; i < n; i++) {
int op = read();
if (op == 1) {
int k = read();
for (int j = 1, x; j <= k; j++) vec[i][read()]++;
} else {
int x = read(), y = read();
for (auto& [k, v] : vec[x - 1]) vec[i][k] += v;
for (auto& [k, v] : vec[y - 1]) vec[i][k] += v;
}
}
auto& g = vec[n - 1];
ll last = 0, ans = 0;
for (auto it = g.rbegin(); it != g.rend(); it++) {
auto& [k, v] = *it;
if (v >= last) {
ans += last * 2;
last = v - last;
} else {
ans += v * 2;
last -= v;
}
}
printf("%lld\n", ans);
}
return 0;
}
/*
2
1
1 5 3 3 2 1 3
3
1 3 3 3 2
1 4 2 2 3 3
2 1 2
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3704kb
input:
2 1 1 5 3 3 2 1 3 3 1 3 3 3 2 1 4 2 2 3 3 2 1 2
output:
4 6
result:
ok 2 lines
Test #2:
score: -100
Time Limit Exceeded
input:
10000 100 1 30 371028678 371028678 371028678 716418076 398221499 591504380 398221499 398221499 591504380 777141390 398221499 591504380 591504380 777141390 287847807 716418076 777141390 716418076 777141390 287847807 287847807 287847807 371028678 371028678 398221499 777141390 371028678 6827702 6827702...
output:
652 68 298 284 114 1024 174 604 704 0 484 244 28 266 1184 236 998 310 326 524 3040 328 1044 178 344 188 0 62 566 354 228 782 134 1402 86 2696 2260 1190 428 360 334 302 350 2848 0 480 1156 44 0 394 590 376 40 16 84 498 728 478 204 654 820 1706 164 166 650 1442 416 282 202 236 666 0 568 1564 692 92 0 ...