QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#115696#6629. Travelling TraderyoungsystemCompile Error//C++206.0kb2023-06-26 16:17:102023-06-26 16:17:12

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-26 16:17:12]
  • 评测
  • [2023-06-26 16:17:10]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
	int n=0,f=1,ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		n=n*10+ch-'0';
		ch=getchar();
	}
	return n*f;
}
vector<int>v[200005];
int qz[200005];
int het[200005]; 
int fa[200005];
int sc[200005],cnt;
void dfs(int x,int f)
{
	fa[x]=f;
	het[x]=qz[x]+het[f];
	for(int i=0;i<v[x].size();i++)
	{
		if(v[x][i]==f)continue;
		dfs(v[x][i],x);
	}
}
int k;
int dep[200005];
void dfsdp(int x,int f,int zf)
{
	if(zf==1)
	{
		sc[++cnt]=x;
		for(int i=0;i<v[x].size();i++)
		{
			if(v[x][i]==f)continue;
			dfsdp(v[x][i],x,-1);	
		}
	}
	else
	{
		for(int i=0;i<v[x].size();i++)
		{
			if(v[x][i]==f)continue;
			dfsdp(v[x][i],x,1);
		}
		sc[++cnt]=x;
	}
}
int dp[200005][3];
int pos[200005][6];
int ez[200005];
//0:hui 1:bu hui
void dfs2(int x,int f)
{
	fa[x]=f;
	int het=qz[x];
	for(int i=0;i<v[x].size();i++)
	{
		if(v[x][i]==f)continue; 
		het+=qz[v[x][i]];
	}
	dp[x][0]=het;
	int max1=0,pos1=0,max2=0,pos2=0;
	int max3=0,pos3=0;
	for(int i=0;i<v[x].size();i++)
	{
		if(v[x][i]==f)continue;
		dfs2(v[x][i],x);
		if(dp[v[x][i]][0]+het-qz[v[x][i]]>dp[x][0])
		{
			dp[x][0]=dp[v[x][i]][0]+het-qz[v[x][i]];
			pos[x][0]=v[x][i];
		}
		if(dp[v[x][i]][0]-qz[v[x][i]]>max1)
		{
			max3=max2;
			pos3=pos2;
			max2=max1;
			pos2=pos1;
			max1=dp[v[x][i]][0]-qz[v[x][i]];
			pos1=v[x][i];
		}
		else if(dp[v[x][i]][0]-qz[v[x][i]]>max2)
		{
			max3=max2;
			pos3=pos2;
			max2=dp[v[x][i]][0]-qz[v[x][i]];
			pos2=v[x][i];
		}
		else if(dp[v[x][i]][0]-qz[v[x][i]]>max3)
		{
			max3=dp[v[x][i]][0]-qz[v[x][i]];
			pos3=v[x][i];
		}
	}
	dp[x][1]=het;
	pos[x][1]=pos[x][2]=0;
	for(int i=0;i<v[x].size();i++)
	{
		if(v[x][i]==f)continue;
		if(v[x][i]==pos1)
		{
			int now=dp[v[x][i]][1]-qz[v[x][i]]+max2+het;
			if(now>dp[x][1])
			{
				dp[x][1]=now;
				pos[x][1]=v[x][i];
				pos[x][2]=pos2;
			}
		}
		else if(v[x][i]==pos2)
		{
			int now=dp[v[x][i]][1]-qz[v[x][i]]+max1+het;
			if(now>dp[x][1])
			{
				dp[x][1]=now;
				pos[x][1]=v[x][i];
				pos[x][2]=pos1;
			}
		} 
	}
	for(int i=0;i<v[x].size();i++)
	{
		if(v[x][i]==f)continue;
		if(dp[v[x][i]][2]+qz[x]>dp[x][1])
		{
			dp[x][1]=dp[v[x][i]][2]+qz[x];
			pos[x][1]=v[x][i];
			pos[x][2]=-1;
		}
	}
	dp[x][2]=het;
	for(int i=0;i<v[x].size();i++)
	{
		if(v[x][i]==f)continue;
		if(v[x][i]==pos1)
		{
			int now=dp[v[x][i]][2]-qz[v[x][i]]+max2+het;
			if(now>dp[x][2])
			{
				dp[x][2]=now;
				pos[x][3]=v[x][i];
				pos[x][4]=pos2;
				pos[x][5]=-1;
			}
		}
		else
		{
			int now=dp[v[x][i]][2]-qz[v[x][i]]+max1+het;
			if(now>dp[x][2])
			{
				dp[x][2]=now;
				pos[x][3]=v[x][i];
				pos[x][4]=pos1;
				pos[x][5]=-1;
			}
		}
	}
	for(int i=0;i<v[x].size();i++)
	{
		if(v[x][i]==f)continue;
		if(v[x][i]==pos1)
		{
			int now=dp[v[x][i]][1]-qz[v[x][i]]+max2+max3+het;
			if(now>dp[x][2])
			{
				dp[x][2]=now;
				pos[x][3]=v[x][i];
				pos[x][4]=pos2;
				pos[x][5]=pos3;
			}
		}
		else if(v[x][i]==pos2)
		{
			int now=dp[v[x][i]][1]-qz[v[x][i]]+max1+max3+het;
			if(now>dp[x][2])
			{
				dp[x][2]=now;
				pos[x][3]=v[x][i];
				pos[x][4]=pos1;
				pos[x][5]=pos3;
			}
		} 
		else
		{
			int now=dp[v[x][i]][1]-qz[v[x][i]]+max1+max2+het;
			if(now>dp[x][2])
			{
				dp[x][2]=now;
				pos[x][3]=v[x][i];
				pos[x][4]=pos1;
				pos[x][5]=pos2;
			}
		}
	}
	//printf("%lld %lld %lld %lld %lld\n",x,dp[x][1],pos[x][1],pos[x][2],pos[x][3]);
}
void findgz(int x,int zt,int zf)
{
	//printf("vis:%d %d %d\n",x,zt,zf);
	if(x==0)return;
	if(zt==0)
	{
		if(zf==1)
		{
			sc[++cnt]=x;
			if(pos[x][0]!=0)findgz(pos[x][0],0,-1);
			for(int i=0;i<v[x].size();i++)
			{
				if(v[x][i]==fa[x])continue;
				if(v[x][i]!=pos[x][0])sc[++cnt]=v[x][i];
			}
		}
		else
		{
			for(int i=0;i<v[x].size();i++)
			{
				if(v[x][i]==fa[x])continue;
				if(v[x][i]!=pos[x][0])sc[++cnt]=v[x][i];
			}
			if(pos[x][0]!=0)findgz(pos[x][0],0,1);
			sc[++cnt]=x;
		}
		return;
	}
	if(zt==1)
	{
		assert(zf==1);
		if(pos[x][2]==-1)
		{
			sc[++cnt]=x;
			findgz(pos[x][1],2,1);
			return; 
		}
		sc[++cnt]=x;
		if(pos[x][2]!=0)
		{
			findgz(pos[x][2],0,-1);
		}
		for(int i=0;i<v[x].size();i++)
		{
			if(v[x][i]==fa[x])continue;
			if(v[x][i]!=pos[x][1]&&v[x][i]!=pos[x][2])sc[++cnt]=v[x][i];
		}
		if(pos[x][1]!=0)
		{
			findgz(pos[x][1],1,1);
		}
		return;
	}
	if(zt==2)
	{
		assert(zf==1);
		if(pos[x][5]==-1)
		{
			for(int i=0;i<v[x].size();i++)
			{
				if(v[x][i]==f)continue;
				if(v[x][i]!=pos[x][4]&&v[x][i]!=pos[x][3])sc[++cnt]=v[x][i];
			}
			if(pos[x][4]!=0)findgz(pos[x][4],0,1);
			sc[++cnt]=x;
			if(pos[x][3]!=0)findgz(pos[x][3],2,1);
			return;
		}
		if(pos[x][4]!=0)findgz(pos[x][4],0,1);
		sc[++cnt]=x;
		if(pos[x][5]!=0)findgz(pos[x][5],0,-1);
		for(int i=0;i<v[x].size();i++)
		{
			if(v[x][i]==fa[x])continue;
			if(v[x][i]!=pos[x][3]&&v[x][i]!=pos[x][4]&&v[x][i]!=pos[x][5])sc[++cnt]=v[x][i];
		}
		if(pos[x][3]!=0)findgz(pos[x][3],1,1);
	}
}
signed main()
{
	int n,x,y;
	n=read();
	k=read();
	for(int i=1;i<=n-1;i++)
	{
		x=read();
		y=read();
		v[x].push_back(y);
		v[y].push_back(x);
	}
	for(int i=1;i<=n;i++)qz[i]=read();
	if(k==1)
	{
		dfs(1,0);
		int maxn=0,mpos=0;
		for(int i=1;i<=n;i++)
		{
			if(het[i]>maxn)
			{
				maxn=het[i];
				mpos=i;
			}
		}
		printf("%lld\n",maxn);
		while(mpos!=0)
		{
			sc[++cnt]=mpos;
			mpos=fa[mpos];
		}
		reverse(sc+1,sc+cnt+1);
		printf("%lld\n",cnt);
		for(int i=1;i<=cnt;i++)printf("%lld ",sc[i]);
		printf("\n");
		return 0;
	}
	if(k==3)
	{
		int ans=0;
		for(int i=1;i<=n;i++)ans+=qz[i];
		printf("%lld %lld\n",ans,n);
		dfsdp(1,0,1);
		for(int i=1;i<=n;i++)printf("%lld ",sc[i]);
		return 0;
	}
	dfs2(1,0);
	findgz(1,1,1);
	printf("%lld %lld\n",dp[1][1],cnt);
	for(int i=1;i<=cnt;i++)printf("%lld ",sc[i]);
	printf("\n");
	return 0;
}

詳細信息

answer.code: In function ‘void findgz(long long int, long long int, long long int)’:
answer.code:266:45: error: ‘f’ was not declared in this scope
  266 |                                 if(v[x][i]==f)continue;
      |                                             ^