QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#717875#9580. 插排串联NULL_SFRE 1ms5756kbC++231.1kb2024-11-06 19:09:472024-11-06 19:09:47

Judging History

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

  • [2024-11-06 19:09:47]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:5756kb
  • [2024-11-06 19:09:47]
  • 提交

answer

#include <iostream>
#include <vector>
#include <algorithm>

#define int long long

using namespace std;

vector<int> son[100001];
int w[100001],depth[100001],sum[100001],curr=0;
vector<int> save;

void dfs(int u)
{
	int maxi=0;
	
	for(auto v:son[u])
	{
		dfs(v);
		
		maxi=max(maxi,depth[v]);
	}
	
	depth[u]=maxi+1;
	
	return;
}

void dfs2(int u)
{
	if((int)son[u].size()==0)
	{
		sum[u]=w[++curr];
		
		return;
	}
	
	for(auto v:son[u]){
		dfs2(v);
		
		sum[u]+=sum[v];
	}
	
	save.push_back(sum[u]);
	
	return;
}

bool cmp(int x,int y)
{
	return depth[x]>depth[y];
}

signed main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	
	int n;
	
	cin>>n;
	for(int i=1;i<=n;i++){
		int fa;
		cin>>fa>>w[i];
		
		son[fa].push_back(i);
	}
	
	sort(w+1,w+n+1);
	
	dfs(1);
	
	for(int i=1;i<=n;i++){
		sort(son[i].begin(),son[i].end(),cmp);
	}
	
	dfs2(1);
	
	sort(save.begin(),save.end());
	for(int i=curr+1,j=0;i<=n;i++,j++)
	{
		if(save[j]>w[i])
		{
			cout<<"NO\n";
			return 0;
		}
	}
	
	if(sum[1]<=2200) cout<<"YES\n";
	else cout<<"NO\n";
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5668kb

input:

5
0 500
1 700
1 400
2 100
2 200

output:

YES

result:

ok single line: 'YES'

Test #2:

score: 0
Accepted
time: 1ms
memory: 5756kb

input:

5
0 500
1 700
1 400
2 100
2 300

output:

NO

result:

ok single line: 'NO'

Test #3:

score: 0
Accepted
time: 0ms
memory: 5600kb

input:

4
0 1000
1 800
1 500
2 300

output:

YES

result:

ok single line: 'YES'

Test #4:

score: -100
Runtime Error

input:

3
0 1000000000
0 1000000000
0 147483647

output:


result: