QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#571840#9349. Exchanging GiftshuaxiamengjinWA 0ms32308kbC++14726b2024-09-18 09:21:162024-09-18 09:21:17

Judging History

你现在查看的是最新测评结果

  • [2024-09-18 09:21:17]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:32308kb
  • [2024-09-18 09:21:16]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int q;
int l[1001001],r[1001001];
vector<int>g[1001001];
int f[1001001],sz[1001001];
map<int,int>ct;
void solve(){
	cin>>q;
	ct.clear();
	int mx,op,n;
	for (int i=1;i<=q;i++){
		g[i].clear();l[i]=r[i]=f[i]=sz[i]=0;
		cin>>op;
		if(op==1){
			cin>>n;
			for (int j=1,x;j<=n;j++)
			cin>>x,g[i].push_back(x);
			sz[i]=n;
		}else{
			cin>>l[i]>>r[i];
			sz[i]=sz[l[i]]+sz[r[i]];
		}
	}
	f[q]=1;
	for (int i=q;i;i--){
		if(l[i]!=0){
			f[l[i]]+=f[i],f[r[i]]+=f[i];
		}else{
			for (auto j:g[i])
			ct[j]+=f[i],mx=max(mx,ct[j]);
		}
	}
//	cout<<mx<<"****\n";
	cout<<min((sz[q]-mx)*2,sz[q])<<"\n";
}
int main(){
	int T;cin>>T;
	while(T--)solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 32308kb

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:

-10
6

result:

wrong answer 1st lines differ - expected: '4', found: '-10'