QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#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

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

[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
*/

源文件, 语言: C++20

详细

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: