QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#608173#9349. Exchanging GiftscatwineTL 631ms4156kbC++141.3kb2024-10-03 19:20:462024-10-03 19:20:47

Judging History

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

  • [2024-10-03 19:20:47]
  • 评测
  • 测评结果:TL
  • 用时:631ms
  • 内存:4156kb
  • [2024-10-03 19:20:46]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define endl '\n'

int n, op, m, x, y, mx, res, total, tmp, t;

void solve() {
  cin >> n;
  vector<unordered_map<int, int>> a(n + 1);
  vector<unordered_map<int, int>> b(n + 1);
  for (int i = 1; i <= n; ++i) {
    cin >> op;
    if (op == 1) {
      cin >> m;
      while (m--) {
        cin >> tmp;
        ++a[i][tmp];
      }
    } else {
      cin >> x >> y;
      if (b[x].size())
        for (auto [num, cnt] : b[x])
          b[i][num] += cnt;
      else
        b[i][x]++;

      if (b[y].size())
        for (auto [num, cnt] : b[y])
          b[i][num] += cnt;
      else
        b[i][y]++;
    }
  }

  unordered_map<int, int> mp;
  if (a[n].size())
    for (auto [k, v] : a[n])
      mp[k] += v;
  else
    for (auto [num, cnt] : b[n]) {
      for (auto [k, v] : a[num]) {
        mp[k] += cnt * v;
      }
    }

  mx = 0, total = 0, res = 0;
  for (const auto &[k, v] : mp) {
    mx = max(v, mx);
    total += v;
  }
  if (mx <= total - mx) {
    res = total;
  } else {
    res = 2 * (total - mx);
  }

  cout << res << endl;
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0), cout.tie(0), cerr.tie(0);
  cin >> t;
  while (t--)
    solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3788kb

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: 0
Accepted
time: 498ms
memory: 3672kb

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:

700
68
332
284
131
1048
194
667
704
0
484
252
35
351
1228
238
1025
354
383
571
4272
340
1044
199
448
190
0
69
841
546
247
883
138
1633
91
3308
2556
1280
488
618
407
381
383
2865
0
496
1202
53
0
415
662
380
41
18
91
505
818
603
241
764
1227
1802
176
187
817
1489
460
296
238
236
1028
0
606
1696
746
10...

result:

ok 10000 lines

Test #3:

score: 0
Accepted
time: 631ms
memory: 4156kb

input:

1000
1000
1 95 626416845 75969860 75969860 75969860 75969860 75969860 626416845 75969860 626416845 626416845 626416845 626416845 75969860 75969860 75969860 626416845 75969860 626416845 626416845 75969860 626416845 75969860 75969860 626416845 75969860 626416845 626416845 75969860 75969860 75969860 62...

output:

7496
113951
17628
151136
92998
49984
39422
57746
0
28271
27458
0
127054
13854
68249
32166
280419
70120
0
0
47941
71104
93032
21042
30012
0
0
14482
20938
66600
94605
129973
145603
16366
43924
0
9923
18731
0
249292
8847
30154
288759
0
86256
30372
156418
247862
91672
38330
89806
27911
137951
166924
189...

result:

ok 1000 lines

Test #4:

score: -100
Time Limit Exceeded

input:

100
10000
1 1354 265069553 265069553 729542591 729542591 729542591 729542591 729542591 729542591 729542591 265069553 265069553 265069553 729542591 729542591 265069553 729542591 265069553 729542591 265069553 729542591 265069553 265069553 265069553 265069553 265069553 265069553 729542591 265069553 265...

output:


result: