QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#645823 | #9349. Exchanging Gifts | hhhhyf | TL | 0ms | 7704kb | C++20 | 1.9kb | 2024-10-16 19:58:26 | 2024-10-16 19:58:27 |
Judging History
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...