QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#645823#9349. Exchanging GiftshhhhyfTL 0ms7704kbC++201.9kb2024-10-16 19:58:262024-10-16 19:58:27

Judging History

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

  • [2024-10-16 19:58:27]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:7704kb
  • [2024-10-16 19:58:26]
  • 提交

answer

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

#define all(a) a.begin(), a.end()

using ll = long long;

const int N = 1e6 + 5;

ll cnt[N], dp[N];
bool vis[N];
vector<int> nums;

void solve () {
    int n;
    cin >> n;
    
    vector<vector<int>> s(n), e(n);
    for (int i = 0; i < n; i ++) {
        int op;
        cin >> op;
        
        if (op == 1) {
            int k;
            cin >> k;
            
            s[i].resize(k);
            for (int& x: s[i]) {
                cin >> x;
                nums.push_back(x);
            }
        } else {
            int x, y;
            cin >> x >> y;
            x --;
            y --;
            e[x].push_back(i);
            e[y].push_back(i);
        }
    }
    
    sort(all(nums));
    nums.erase(unique(all(nums)), nums.end());
    
    auto get = [&](int x) {
        return lower_bound(all(nums), x) - nums.begin();
    };
    
    dp[n - 1] = 1;
    
    auto dfs = [&](auto&& self, int u) -> ll {
        if (vis[u]) {
            return dp[u];
        }
        vis[u] = 1;
        for (int v: e[u]) {
            dp[u] += self(self, v);
        }
        return dp[u];
    };
    
    int m = nums.size();
    for (int i = 0; i < n; i ++) {
        dfs(dfs, i);
        if (dp[i]) {
            for (int x: s[i]) {
                x = get(x);
                cnt[x] += dp[i];
            }
        }
    }
    
    ll sum = 0;
    ll mx = 0;
    for (auto x: cnt) {
        sum += x;
        mx = max(mx, x);
    }
    cout << sum - max<ll>(0, mx * 2 - sum) << '\n';
    
    fill(cnt, cnt + m, 0);
    fill(dp, dp + n, 0);
    fill(vis, vis + n, 0);
    nums.clear();
}

int main () {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int t = 1;
    cin >> t;
    while (t --) {
        solve();
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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:


result: