QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#633074 | #9349. Exchanging Gifts | wlkmok369 | WA | 102ms | 38856kb | C++23 | 2.0kb | 2024-10-12 14:29:32 | 2024-10-12 14:29:33 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define INF 0x3f
const ll mod = 1e9 + 7;
const ll MAXN = 1e6 + 100;
ll _ = 1, n, m, x, ans = 0; // a[MAXN], f[MAXN];
ll op[MAXN];
struct node
{
ll n;
vector<ll> a;
} a[MAXN];
struct node2
{
ll x, y;
} add[MAXN];
vector<ll> dp(n + 100, 0);
inline ll read()
{
ll x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
void solve()
{
n = read();
for (int i = 1; i <= n; i++)
{
dp[i] = 0;
a[i].a.clear();
op[i] = read();
if (op[i] == 1)
{
a[i].n = read();
for (int j = 1; j <= a[i].n; j++)
{
x = read();
a[i].a.push_back(x);
}
}
else
{
add[i].x = read();
add[i].y = read();
}
}
ll len = 0;
map<ll, ll> ma;
dp[n] = 1;
for (int i = n; i >= 1; i--)
{
if (op[i] == 2)
{
dp[add[i].x] += dp[i];
dp[add[i].y] += dp[i];
}
else
{
for (int j = 0; j < a[i].a.size(); j++)
{
ma[a[i].a[j]] += dp[i];
}
len += a[i].a.size() * dp[i];
}
}
ll maxn = 0;
for (auto it : ma)
{
maxn = max(maxn, it.second);
}
if (maxn > len - maxn)
{
cout << 2 * (len - maxn) << '\n';
}
else
{
cout << len << '\n';
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
_ = read();
while (_--)
{
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 38448kb
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: 102ms
memory: 36468kb
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: -100
Wrong Answer
time: 93ms
memory: 38856kb
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:
result:
wrong answer 1st lines differ - expected: '7496', found: ''