QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#709397#8758. Menji 和 gcdszy10010#WA 2ms9792kbC++231.6kb2024-11-04 14:34:322024-11-04 14:34:33

Judging History

This is the latest submission verdict.

  • [2024-11-04 14:34:33]
  • Judged
  • Verdict: WA
  • Time: 2ms
  • Memory: 9792kb
  • [2024-11-04 14:34:32]
  • Submitted

answer

#include<iostream>
#include<map>
#include<cmath>
#include<string>
#include<vector>
#include<cstring>
#include<algorithm>
#include<unordered_map>

#define pb emplace_back
#define fi first
#define se second
#define int long long
#define all(x) (x).begin(),(x).end()
#define _for(i, a) for(int i = 0; i < (a); ++i) 
#define _rep(i, a, b) for(int i = (a);i <= (b); ++i)
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define u1 (u<<1)
#define u2 (u<<1|1)
//#define endl '\n'
using namespace std;
typedef pair<int,int> PII;

const int INF=0x3f3f3f3f;
const int P=1e9+7;
const int N=2e5+20,M=2*N;
int n;
//res维护以i为根的答案
int res[N],sum[N],sz[N],w[N];
vector<int> v[N];
//bool st[N];
bool cmp(int a,int b)
{
	int ta=res[a]+(sz[a])*sum[b]+res[b];
	int tb=res[b]+(sz[b])*sum[a]+res[a];
//	cout<<a<<" "<<b<<" "<<res[a]<<" "<<res[b]<<" "<<sz[a]<<" "<<sz[b]<<" "<<sum[a]<<" "<<sum[b]<<" "<<ta<<" "<<tb<<endl; 
	return ta>=tb;
}
int dfs(int u){
//	st[u]=true;
//	cout<<" "<<u<<endl;
	sz[u]=1;
	sum[u]=w[u];
	res[u]=w[u];
	for(auto j:v[u])
	{
		dfs(j);
		sz[u]+=sz[j];
		sum[u]+=sum[j];
	}
	if(v[u].size())
	{
		sort(all(v[u]),cmp);
		int nowres=0,nowsz=1;
		for(auto i:v[u])
		{
			nowres+=nowsz*sum[i]+res[i];
	//		cout<<"u="<<u<<endl;
			nowsz+=sz[i];
	//		ans[u].pb(i);
		}
		res[u]+=nowres;
	}
//	cout<<u<<" "<<res[u]<<endl;
	return res[u];
}
void solve(){
	cin>>n;
	_rep(i,1,n) cin>>w[i];
	_rep(i,2,n){
		int fa;
		cin>>fa;
		if(fa>=0&&fa<=n)v[fa].pb(i);
	}
	cout<<dfs(1);
	return;
}
signed main(){
	IOS;
	int T=1;
//	cin>>T;
	_rep(i,1,T){
		solve();
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 2ms
memory: 9792kb

input:

10
1 2
2 4
6 10
11 21
147 154
1470 1540
2890 3028
998244353 1000000007
34827364537 41029384775
147147147147 154154154154

output:

1

result:

wrong answer Answer contains longer sequence [length = 10], but output contains 1 elements