QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#114025 | #6629. Travelling Trader | 1kri | 0 | 2ms | 11956kb | C++14 | 9.0kb | 2023-06-20 15:45:45 | 2023-06-20 15:45:46 |
Judging History
answer
#include <iostream>
#include <cstdio>
#include <cassert>
#include <cstring>
#include <vector>
#define ll long long
using namespace std;
int n,k,u[400005],v[400005],first[200005],nxt[400005];
int a[200005];
namespace QwQ1{
ll f[200005];
int tot,id[200005];
void dfs1(int now,int fa){
for (int i=first[now];i;i=nxt[i])
if (v[i]!=fa){
dfs1(v[i],now);
f[now]=max(f[now],f[v[i]]);
}
f[now]+=a[now];
return;
}
void dfs2(int now,int fa){
id[++tot]=now;
for (int i=first[now];i;i=nxt[i])
if (v[i]!=fa&&f[now]==a[now]+f[v[i]]){
dfs2(v[i],now);
break;
}
return;
}
void work(){
dfs1(1,0);
dfs2(1,0);
printf("%lld\n",f[1]);
printf("%d\n",tot);
for (int i=1;i<=tot;i++)printf("%d ",id[i]);
printf("\n");
return;
}
}
namespace QwQ2{
ll f0[200005],f1[200005],g0[200005],g1[200005];
int id0[3][200005],id1[3][200005];
void dfs1(int now,int fa){
for (int i=first[now];i;i=nxt[i])
if (v[i]!=fa)dfs1(v[i],now);
vector<int> c;
for (int i=first[now];i;i=nxt[i])
if (v[i]!=fa)c.push_back(v[i]);
c.push_back(0),c.push_back(0);
int len=c.size();
ll sum=0;
for (int i=0;i<len;i++)sum+=a[c[i]];
for (int i=0;i<len;i++){
id0[0][i]=id0[1][i]=0;
if (i>0)id0[0][i]=id0[0][i-1],id0[1][i]=id0[1][i-1];
if (id0[0][i]==-1||g1[c[i]]-a[c[i]]>g1[id0[0][i]]-a[id0[0][i]])id0[0][i]=c[i];
if (id0[1][i]==-1||f0[c[i]]-a[c[i]]>f0[id0[1][i]]-a[id0[1][i]])id0[1][i]=c[i];
}
for (int t=1;t<len;t++){
int x,y;
x=id0[0][t-1],y=c[t];
f0[now]=max(f0[now],g1[x]-a[x]+f0[y]-a[y]);
x=c[t],y=id0[1][t-1];
f0[now]=max(f0[now],g1[x]-a[x]+f0[y]-a[y]);
}
for (int i=0;i<len;i++){
id0[0][i]=id0[1][i]=id0[2][i]=0;
if (i>0)id0[0][i]=id0[0][i-1],id0[1][i]=id0[1][i-1],id0[2][i]=id0[2][i-1];
if (id0[0][i]==-1||g1[c[i]]-a[c[i]]>g1[id0[0][i]]-a[id0[0][i]])id0[0][i]=c[i];
if (id0[1][i]==-1||g0[c[i]]-a[c[i]]>g0[id0[1][i]]-a[id0[1][i]])id0[1][i]=c[i];
if (id0[2][i]==-1||f1[c[i]]-a[c[i]]>f1[id0[2][i]]-a[id0[2][i]])id0[2][i]=c[i];
}
for (int i=len-1;i>=0;i--){
id1[0][i]=id1[1][i]=id1[2][i]=0;
if (i<len-1)id1[0][i]=id1[0][i+1],id1[1][i]=id1[1][i+1],id1[2][i]=id1[2][i+1];
if (id1[0][i]==-1||g1[c[i]]-a[c[i]]>g1[id1[0][i]]-a[id1[0][i]])id1[0][i]=c[i];
if (id1[1][i]==-1||g0[c[i]]-a[c[i]]>g0[id1[1][i]]-a[id1[1][i]])id1[1][i]=c[i];
if (id1[2][i]==-1||f1[c[i]]-a[c[i]]>f1[id1[2][i]]-a[id1[2][i]])id1[2][i]=c[i];
}
for (int i=1;i<len-1;i++){
int x=c[i],y=id0[1][i-1],z=id1[2][i+1];
f0[now]=max(f0[now],g1[x]-a[x]+g0[y]-a[y]+f1[z]-a[z]);
x=c[i],y=id1[1][i+1],z=id0[2][i-1];
f0[now]=max(f0[now],g1[x]-a[x]+g0[y]-a[y]+f1[z]-a[z]);
x=id0[0][i-1],y=c[i],z=id1[2][i+1];
f0[now]=max(f0[now],g1[x]-a[x]+g0[y]-a[y]+f1[z]-a[z]);
x=id0[0][i-1],y=id1[1][i+1],z=c[i];
f0[now]=max(f0[now],g1[x]-a[x]+g0[y]-a[y]+f1[z]-a[z]);
x=id1[0][i+1],y=c[i],z=id0[2][i-1];
f0[now]=max(f0[now],g1[x]-a[x]+g0[y]-a[y]+f1[z]-a[z]);
x=id1[0][i+1],y=id0[1][i-1],z=c[i];
}
f0[now]+=a[now]+sum;
for (int i=0;i<len;i++){
id0[0][i]=id0[1][i]=0;
if (i>0)id0[0][i]=id0[0][i-1],id0[1][i]=id0[1][i-1];
if (id0[0][i]==-1||g0[c[i]]-a[c[i]]>g0[id0[0][i]]-a[id0[0][i]])id0[0][i]=c[i];
if (id0[1][i]==-1||f1[c[i]]-a[c[i]]>f1[id0[1][i]]-a[id0[1][i]])id0[1][i]=c[i];
}
for (int t=1;t<len;t++){
int x,y;
x=id0[0][t-1],y=c[t];
f1[now]=max(f1[now],g0[x]-a[x]+f1[y]-a[y]);
x=c[t],y=id0[1][t-1];
f1[now]=max(f1[now],g0[x]-a[x]+f1[y]-a[y]);
}
f1[now]+=a[now]+sum;
for (int i=0;i<len;i++)
f1[now]=max(f1[now],a[now]+f0[c[i]]);
for (int i=0;i<len;i++)g0[now]=max(g0[now],g1[c[i]]-a[c[i]]);
g0[now]+=a[now]+sum;
for (int i=0;i<len;i++)g1[now]=max(g1[now],g0[c[i]]-a[c[i]]);
g1[now]+=a[now]+sum;
return;
}
int tot,id[200005];
void dfs2(int now,int fa,int o){
vector<int> c;
for (int i=first[now];i;i=nxt[i])
if (v[i]!=fa)c.push_back(v[i]);
c.push_back(0),c.push_back(0);
int len=c.size();
ll sum=0;
for (int i=0;i<len;i++)sum+=a[c[i]];
if (o==0){
for (int i=0;i<len;i++){
id0[0][i]=id0[1][i]=0;
if (i>0)id0[0][i]=id0[0][i-1],id0[1][i]=id0[1][i-1];
if (id0[0][i]==-1||g1[c[i]]-a[c[i]]>g1[id0[0][i]]-a[id0[0][i]])id0[0][i]=c[i];
if (id0[1][i]==-1||f0[c[i]]-a[c[i]]>f0[id0[1][i]]-a[id0[1][i]])id0[1][i]=c[i];
}
int x=-1,y=-1,z=-1;
for (int t=1;t<len;t++){
int _x,_y;
_x=id0[0][t-1],_y=c[t];
if (f0[now]==a[now]+sum+g1[_x]-a[_x]+f0[_y]-a[_y])x=_x,y=_y;
_x=c[t],_y=id0[1][t-1];
if (f0[now]==a[now]+sum+g1[_x]-a[_x]+f0[_y]-a[_y])x=_x,y=_y;
}
if (x!=-1&&y!=-1){
for (int i=0;i<len;i++)
if (c[i]!=x&&c[i]!=y&&c[i]!=0)id[++tot]=c[i];
if (x!=0)dfs2(x,now,3);
id[++tot]=now;
if (y!=0)dfs2(y,now,0);
return;
}
for (int i=0;i<len;i++){
id0[0][i]=id0[1][i]=id0[2][i]=0;
if (i>0)id0[0][i]=id0[0][i-1],id0[1][i]=id0[1][i-1],id0[2][i]=id0[2][i-1];
if (id0[0][i]==-1||g1[c[i]]-a[c[i]]>g1[id0[0][i]]-a[id0[0][i]])id0[0][i]=c[i];
if (id0[1][i]==-1||g0[c[i]]-a[c[i]]>g0[id0[1][i]]-a[id0[1][i]])id0[1][i]=c[i];
if (id0[2][i]==-1||f1[c[i]]-a[c[i]]>f1[id0[2][i]]-a[id0[2][i]])id0[2][i]=c[i];
}
for (int i=len-1;i>=0;i--){
id1[0][i]=id1[1][i]=id1[2][i]=0;
if (i<len-1)id1[0][i]=id1[0][i+1],id1[1][i]=id1[1][i+1],id1[2][i]=id1[2][i+1];
if (id1[0][i]==-1||g1[c[i]]-a[c[i]]>g1[id1[0][i]]-a[id1[0][i]])id1[0][i]=c[i];
if (id1[1][i]==-1||g0[c[i]]-a[c[i]]>g0[id1[1][i]]-a[id1[1][i]])id1[1][i]=c[i];
if (id1[2][i]==-1||f1[c[i]]-a[c[i]]>f1[id1[2][i]]-a[id1[2][i]])id1[2][i]=c[i];
}
for (int i=1;i<len-1;i++){
int _x=c[i],_y=id0[1][i-1],_z=id1[2][i+1];
if (f0[now]==a[now]+sum+g1[_x]-a[_x]+g0[_y]-a[_y]+f1[_z]-a[_z])x=_x,y=_y,z=_z;
_x=c[i],_y=id1[1][i+1],_z=id0[2][i-1];
if (f0[now]==a[now]+sum+g1[_x]-a[_x]+g0[_y]-a[_y]+f1[_z]-a[_z])x=_x,y=_y,z=_z;
_x=id0[0][i-1],_y=c[i],_z=id1[2][i+1];
if (f0[now]==a[now]+sum+g1[_x]-a[_x]+g0[_y]-a[_y]+f1[_z]-a[_z])x=_x,y=_y,z=_z;
_x=id0[0][i-1],_y=id1[1][i+1],_z=c[i];
if (f0[now]==a[now]+sum+g1[_x]-a[_x]+g0[_y]-a[_y]+f1[_z]-a[_z])x=_x,y=_y,z=_z;
_x=id1[0][i+1],_y=c[i],_z=id0[2][i-1];
if (f0[now]==a[now]+sum+g1[_x]-a[_x]+g0[_y]-a[_y]+f1[_z]-a[_z])x=_x,y=_y,z=_z;
_x=id1[0][i+1],_y=id0[1][i-1],_z=c[i];
}
if (x!=-1&&y!=-1&&z!=-1){
for (int i=0;i<len;i++)
if (c[i]!=x&&c[i]!=y&&c[i]!=z&&c[i]!=0)id[++tot]=c[i];
if (x!=0)dfs2(x,now,3);
id[++tot]=now;
if (y!=0)dfs2(y,now,2);
if (z!=0)dfs2(z,now,1);
return;
}
return;
}
if (o==1){
id[++tot]=now;
for (int i=0;i<len;i++){
id0[0][i]=id0[1][i]=0;
if (i>0)id0[0][i]=id0[0][i-1],id0[1][i]=id0[1][i-1];
if (id0[0][i]==-1||g0[c[i]]-a[c[i]]>g0[id0[0][i]]-a[id0[0][i]])id0[0][i]=c[i];
if (id0[1][i]==-1||f1[c[i]]-a[c[i]]>f1[id0[1][i]]-a[id0[1][i]])id0[1][i]=c[i];
}
int x=-1,y=-1;
for (int t=1;t<len;t++){
int _x,_y;
_x=id0[0][t-1],_y=c[t];
if (f1[now]==a[now]+sum+g0[_x]-a[_x]+f1[_y]-a[_y])x=_x,y=_y;
_x=c[t],_y=id0[1][t-1];
if (f1[now]==a[now]+sum+g0[_x]-a[_x]+f1[_y]-a[_y])x=_x,y=_y;
}
if (x!=-1&&y!=-1){
if (x!=0)dfs2(x,now,2);
for (int i=0;i<len;i++)
if (c[i]!=x&&c[i]!=y&&c[i]!=0)id[++tot]=c[i];
if (y!=0)dfs2(y,now,1);
return;
}
for (int i=0;i<len;i++)
if (f1[now]==a[now]+f0[c[i]]){
dfs2(c[i],now,0);
return;
}
return;
}
if (o==2){
int qwq=0;
for (int i=0;i<len;i++)
if (g0[now]==a[now]+g1[c[i]]+sum-a[c[i]])qwq=c[i];
for (int i=0;i<len;i++)
if (c[i]!=qwq&&c[i]!=0)id[++tot]=c[i];
if (qwq!=0)dfs2(qwq,now,3);
id[++tot]=now;
return;
}
if (o==3){
id[++tot]=now;
int qwq=0;
for (int i=0;i<len;i++)
if (g1[now]==a[now]+g0[c[i]]+sum-a[c[i]])qwq=c[i];
if (qwq!=0)dfs2(qwq,now,2);
for (int i=0;i<len;i++)
if (c[i]!=qwq&&c[i]!=0)id[++tot]=c[i];
return;
}
return;
}
void work(){
dfs1(1,0);
dfs2(1,0,1);
printf("%lld\n",f1[1]);
return;
printf("%d\n",tot);
for (int i=1;i<=tot;i++)printf("%d ",id[i]);
printf("\n");
return;
}
}
namespace QwQ3{
void dfs1(int,int);
void dfs2(int,int);
int tot,id[200005];
void dfs2(int now,int fa){
for (int i=first[now];i;i=nxt[i])
if (v[i]!=fa)dfs1(v[i],now);
id[++tot]=now;
return;
}
void dfs1(int now,int fa){
id[++tot]=now;
for (int i=first[now];i;i=nxt[i])
if (v[i]!=fa)dfs2(v[i],now);
return;
}
void work(){
dfs1(1,0);
ll sum=0;
for (int i=1;i<=n;i++)sum+=a[i];
printf("%lld\n",sum);
printf("%d\n",tot);
for (int i=1;i<=tot;i++)printf("%d ",id[i]);
printf("\n");
return;
}
}
int main(){
scanf("%d%d",&n,&k);
assert(k==2);
for (int i=1;i<n;i++){
scanf("%d%d",&u[i],&v[i]);
nxt[i]=first[u[i]],first[u[i]]=i;
u[i+n]=v[i],v[i+n]=u[i];
nxt[i+n]=first[u[i+n]],first[u[i+n]]=i+n;
}
for (int i=1;i<=n;i++)scanf("%d",&a[i]);
if (k==1){
QwQ1::work();
return 0;
}
if (k==2){
QwQ2::work();
return 0;
}
if (k==3){
QwQ3::work();
return 0;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Dangerous Syscalls
Test #1:
score: 0
Dangerous Syscalls
input:
2 1 1 2 255959470 961356354
output:
result:
Subtask #2:
score: 0
Wrong Answer
Test #12:
score: 0
Wrong Answer
time: 2ms
memory: 11956kb
input:
2 2 2 1 243296356 635616793
output:
878913149
result:
wrong output format Unexpected end of file - int32 expected
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #3:
0%
Subtask #5:
score: 0
Dangerous Syscalls
Test #83:
score: 0
Dangerous Syscalls
input:
2000 3 1359 90 1703 163 158 188 360 1501 195 664 1414 215 1546 1756 536 1096 1726 1223 1150 104 1757 703 1982 282 1023 998 1180 419 576 1759 1496 1993 44 670 1703 952 855 849 1998 1399 1280 980 1533 1090 1270 678 1680 387 469 1734 1799 263 473 588 303 226 5 295 1489 1471 1094 1667 1912 210 1368 1360...
output:
result:
Subtask #6:
score: 0
Skipped
Dependency #5:
0%