QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #115696 | #6629. Travelling Trader | youngsystem | Compile Error | / | / | C++20 | 6.0kb | 2023-06-26 16:17:10 | 2023-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]
- 评测
- 测评结果：Compile Error
- 用时：0ms
- 内存：0kb
- [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;
}
Details
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;
| ^