请求加强数据!
  • 板块题目总版
  • 楼主LeoWayyyyyyy
  • 当前回复4
  • 已保存回复4
  • 发布时间2021/10/21 22:05
  • 上次更新2023/11/4 02:59:02
查看原帖
请求加强数据!
180155
LeoWayyyyyyy楼主2021/10/21 22:05

这题我连第三个样例点都过不了,却能AC?

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int SIZE=1e4;

int n,s;
int fa[SIZE],a[SIZE],b[SIZE],c[SIZE],v[SIZE];
vector<int> ver[SIZE];

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

inline void read()
{
	for(register int i=1;i<=n;i++) fa[i]=i;
	
	cin>>n>>s;
	for(register int i=1;i<n;i++)
	{
		int x;
		cin>>x;
		ver[x].push_back(i+1);
		fa[i+1]=x;
		//ver[i+1].push_back(x);
	}
	for(register int i=1;i<=n;i++)
	{
		cin>>a[i];
		b[i]=a[i];
	}
	
	for(register int i=1;i<=n;i++)
	{
		if(i!=1) b[fa[i]]+=a[i];
	}
	
	for(register int i=1;i<=n;i++)
	{
		if(ver[i].size()) sort(ver[i].begin(),ver[i].end(),cmp);
	}
}

inline int bfs()
{
	queue<int> q;
	q.push(1);
	v[1]=1;
	if(s+a[1]<0)
	{
		cout<<s;
		puts("");
		return 0;
	} 
	while(q.size())
	{
		int x=q.front();q.pop();
		s+=a[x];
		for(register int y=0;y<ver[x].size();y++)
		{
			int t=ver[x][y];
			if(a[t]+s>=0&&b[t]>0&&!v[t])
			{
				q.push(t);
				v[t]=1;
			}
		}
	}
	return s;
}
signed main()
{
	read();
	cout<<bfs()<<endl;
	return 0;
}

只过了两个样例,本来想交一下看看能有多少分,没想到直接AC了? @昒昕

2021/10/21 22:05
加载中...