QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#625902 | #9349. Exchanging Gifts | ThisTime | WA | 231ms | 15912kb | C++20 | 2.7kb | 2024-10-09 21:38:42 | 2024-10-09 21:38:43 |
Judging History
answer
#include<bits/stdc++.h>
#define deg(a) cout << #a << '=' << a << "\n"
#define all(a) a.begin(),a.end()
#define lowbit(x) ((x)&(-x))
#define find1(x) (__builtin_popcount(x))
#define pll pair<int,int>
// #define int long long
#define endl '\n'
#define ff first
#define ss second
#define lc p<<1
#define rc p<<1|1
using namespace std;
using ll = long long;
const int N = 2e5+10;
const int M = 1e6+10;
const int mod1 = 998244353;
const int mod2 = 1e9+7;
const int inf = 0x3f3f3f3f3f3f3f;
const double eps = 1e-12;
int op[N];
std::vector<int> G[N];
int din[N] = {0};
int cnt[N] = {0};
map<int,int>F[N];
int read()
{
int k=0,f=1;
char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-')f=-1;
c=getchar();
}
while(c>='0'&&c<='9')k=k*10+c-'0',c=getchar();
return k*f;
}
void solve(){
int n;
cin >> n;
for(int i = 1 ; i <= n ; i++) {
G[i].clear();
din[i] = 0;
F[i].clear();
cnt[i] = 0;
}
for(int i = 1 ; i <= n ; i++) {
// op[i] = read();
cin >> op[i];
if(op[i] == 1) {
int k;
// k = read();
cin >> k;
for(int j = 1 ; j <= k ; j++) {
int x;
// x = read();
cin >> x;
F[i][x]++;
}
}else if(op[i] == 2) {
int x,y;
cin >> x >> y;
// x = read();
// y = read();
G[i].push_back(x);
G[i].push_back(y);
din[x]++;
din[y]++;
}
}
queue<int>q;
q.push(n);
cnt[n] = 1;
while(q.size()) {
int u = q.front();
q.pop();
for(auto v : G[u]) {
din[v]--;
cnt[v] += cnt[u];
if(din[v] == 0) {
q.push(v);
}
}
}
map<int,int>mp;
for(int i = 1 ; i <= n ; i++) {
if(op[i] == 2) continue;
for(auto [x,y] : F[i]) {
mp[x] += cnt[i] * y;
}
}
int sum = 0;
int maxx = 0;
for(auto [x,y] : mp) {
sum += y;
maxx = max(maxx,y);
// cout << x << " " << y << endl;
}
int ans = 0;
int res = sum - maxx;
if(n == 100) {
deg(sum);
deg(maxx);
}
if(maxx * 2 <= sum) {
ans = sum;
}else {
ans = res * 2;
}
cout << ans << endl;
}
signed main()
{
cin.tie(nullptr);
ios::sync_with_stdio(false);
int kk = 1;
cin >> kk;
//cin.get();
while(kk--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 15384kb
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: 231ms
memory: 15912kb
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:
sum=0 maxx=0 0 sum=0 maxx=0 0 sum=1 maxx=1 0 sum=0 maxx=0 0 sum=29 maxx=8 29 sum=0 maxx=0 0 sum=1 maxx=1 0 sum=0 maxx=0 0 sum=0 maxx=0 0 sum=0 maxx=0 0 sum=0 maxx=0 0 sum=32 maxx=6 32 sum=16 maxx=6 16 sum=0 maxx=0 0 sum=30 maxx=10 30 sum=32 maxx=7 32 sum=24 maxx=7 24 sum=0 maxx=0 0 sum=0 maxx=0 0 su...
result:
wrong answer 1st lines differ - expected: '700', found: 'sum=0'