QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#629630 | #9349. Exchanging Gifts | yumingsk | WA | 188ms | 54924kb | C++14 | 2.4kb | 2024-10-11 13:57:23 | 2024-10-11 13:57:23 |
Judging History
answer
#pragma GCC optimize(3, "Ofast", "inline")
#include <iostream>
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define INF 0x3f3f3f3f
#define L_INF 0x7f3f3f3f3f3f3f3f
#define db cout << "debug\n";
using namespace std;
const int Mod = 998244353;
using ll = long long;
vector<int> e[1000005];
vector<int> sq[1000000 + 1];
int deg[1000005];
map<int, int> ma;
vector<int> tp(1000005);
void bfs(int u)
{
queue<int> q;
q.push(u);
tp[u] = 1;
while (!q.empty())
{
int t = q.front();
q.pop();
// cout << t << '\n';
for (auto v : e[t])
{
// cout << v << '\n';
tp[v] += tp[t];
deg[v]--;
if (deg[v] == 0)
{
q.push(v);
}
}
}
return;
}
void solve()
{
int n;
cin >> n;
for (int i = 1; i <= n + 1; i++)
e[i].clear(), sq[i].clear(), tp[i] = 0, deg[i] = 0;
ma.clear();
for (int i = 1; i <= n; i++)
{
int op;
cin >> op;
if (op == 1)
{
int len;
cin >> len;
sq[i].resize(len);
for (int j = 1; j <= len; j++)
{
int x;
cin >> x;
sq[i][j - 1] = x;
}
}
else
{
int x, y;
cin >> x >> y;
e[i].push_back(x);
e[i].push_back(y);
deg[x]++;
deg[y]++;
}
}
// cout << "SS\n";
ll sum = 0;
ll mx = 0;
bfs(n);
for (int i = 1; i <= n; i++)
{
if (!sq[i].empty())
{
for (auto v : sq[i])
ma[v] += tp[i];
}
}
for (auto v : ma)
{
sum += v.second;
mx = max(mx, v.second * 1LL);
}
// cout << sum << " " << mx << '\n';
if (mx > sum - mx)
{
cout << 2LL * (sum - mx) << '\n';
}
else
{
cout << sum << '\n';
}
}
int main()
{
IOS;
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#ifndef ONLINE_JUDGE
clock_t start_time = clock();
#endif
int t = 1;
cin >> t;
while (t--)
{
solve();
}
#ifndef ONLINE_JUDGE
cout << "Used " << (double)(clock() - start_time) << " ms" << endl;
#endif
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 54924kb
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
Wrong Answer
time: 188ms
memory: 54024kb
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:
0 0 0 0 29 0 0 0 0 0 0 32 16 0 30 32 24 0 0 0 28 0 0 0 0 5 0 0 0 0 10 0 0 0 9 0 0 0 0 8 0 25 0 0 0 0 18 0 0 0 0 0 4 18 0 19 0 0 0 0 0 0 0 0 37 0 0 18 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 2 23 0 0 0 20 0 0 23 0 12 0 0 0 0 0 0 0 10 0 0 0 0 0 35 0 0 25 0 0 0 0 22 0 0 0 0 0 0 12 0 0 0 0 94 0 23 0 0 0 0...
result:
wrong answer 1st lines differ - expected: '700', found: '0'