QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#578602 | #9349. Exchanging Gifts | Yukari# | TL | 0ms | 3744kb | C++20 | 1.4kb | 2024-09-20 20:19:20 | 2024-09-20 20:19:26 |
Judging History
answer
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
int t;
scanf("%d", &t);
while (t--) {
int n;
scanf("%d", &n);
vector<map<int, ll>> vec;
for (int i = 0; i < n; i++) {
int op;
scanf("%d", &op);
if (op == 1) {
int k;
scanf("%d", &k);
map<int, ll> mp;
for (int j = 1, x; j <= k; j++) {
scanf("%d", &x);
mp[x] += 1;
}
vec.emplace_back(mp);
} else {
int x, y;
scanf("%d%d", &x, &y);
map<int, ll> mp;
for (auto& [k, v] : vec[x - 1]) mp[k] += v;
for (auto& [k, v] : vec[y - 1]) mp[k] += v;
vec.emplace_back(mp);
}
}
auto& g = vec[n - 1];
ll last = 0;
ll 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: 3744kb
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 ...