QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#625867 | #9349. Exchanging Gifts | ThisTime | WA | 106ms | 7864kb | C++23 | 2.6kb | 2024-10-09 21:30:40 | 2024-10-09 21:30:41 |
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};
std::vector<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();
if(op[i] == 1) {
int k;
k = read();
for(int j = 1 ; j <= k ; j++) {
int x;
x = read();
F[i].push_back(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);
}
}
}
// deg(cnt[1]);
// deg(cnt[2]);
map<int,int>mp;
for(int i = 1 ; i <= n ; i++) {
if(op[i] == 2) continue;
for(auto x : F[i]) {
mp[x] += cnt[i];
}
}
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(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: 0ms
memory: 7864kb
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: 106ms
memory: 7708kb
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'