QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#607677#9349. Exchanging Giftscatwine#TL 0ms3668kbC++141.5kb2024-10-03 15:46:552024-10-03 15:46:57

Judging History

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

  • [2024-10-03 15:46:57]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3668kb
  • [2024-10-03 15:46:55]
  • 提交

answer

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

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

#ifdef DEBUG
#define debug(x) cerr << #x << ": " << x << endl;
#else
#define debug(x)
#endif

int n, m, t;

void solve() {
  cin >> n;
  vector<unordered_map<int, int>> mp(n);
  int op, k, num, mp1, mp2;
  for (int i = 0; i < n; ++i) {
    cin >> op;
    if (op == 1) {
      cin >> k;
      while (k--) {
        cin >> num;
        ++mp[i][num];
      }
    } else if (op == 2) {
      cin >> mp1 >> mp2;
      --mp1, --mp2;
      for (const auto &[k, v] : mp[mp1]) {
        mp[i][k] += v;
        // cerr << i << ' ' << k << ' ' << v << endl;
      }
      for (const auto &[k, v] : mp[mp2]) {
        mp[i][k] += v;
        // cerr << i << ' ' << k << ' ' << v << endl;
      }
    }
    // for (const auto &[k, v]: mp[i]) {
    //   cerr << k << ": " << v << endl;
    // }
    // cerr << endl;
  }

  vector<int> tmp;
  int sm = 0;
  for (const auto &[k, v] : mp[n - 1]) {
    // cerr << k << ": " << v << endl;
    tmp.push_back(v);
    sm += v;
  }
  sort(tmp.begin(), tmp.end(), greater<int>());
  int res = tmp.front(), sz = tmp.size();
  for (int i = 1; i < sz; ++i) {
    res = res - tmp[i];
    if (res < 0) res *= -1;
    // cerr << res << endl;
  }
  // for (int &it : tmp) {
  //   cerr << it << ' ';
  // }
  // cerr << endl;
  cout << sm - 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: 3668kb

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:

640
68
328
284
128
892
186
664
704
0
484
248
34
266
1184
234
930
310
372
566
3756
330
986
196
444
188
0
64
624
390
232
874
134
1560
90
3306
2408
1278
428
604
384
302
380
2834
0
496
1188
50
0
414
654
378
40
18
90
504
816
590
204
756
974
1778
164
166
650
1432
440
292
222
236
732
0
576
1684
702
96
0
15...

result: