QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#578771#9349. Exchanging GiftsYukari#TL 0ms3704kbC++201.3kb2024-09-20 21:12:582024-09-20 21:12:59

Judging History

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

  • [2024-09-20 21:12:59]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3704kb
  • [2024-09-20 21:12:58]
  • 提交

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
...

result: