QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#114024#6629. Travelling Trader1kri0 3ms16008kbC++149.0kb2023-06-20 15:43:282023-06-20 15:43:32

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-20 15:43:32]
  • 评测
  • 测评结果：0
  • 用时：3ms
  • 内存：16008kb
查看
  • [2023-06-20 15:43:28]
  • 提交

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(x,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]);
		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;
}
Source code, Language: C++14

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: 7
Accepted
time: 3ms
memory: 15992kb

input:

2 2
2 1
243296356 635616793

output:

878913149
2
1 2

result:

ok correct!

Test #13:

score: 0
Accepted
time: 2ms
memory: 11936kb

input:

10 2
6 4
3 7
5 10
6 10
8 2
3 9
3 5
4 2
1 4
2 4 2 5 5 4 2 3 4 2

output:

33
10
1 4 10 3 9 7 5 6 2 8

result:

ok correct!

Test #14:

score: -7
Wrong Answer
time: 1ms
memory: 16008kb

input:

200 2
150 170
21 33
96 152
143 26
136 70
92 159
34 164
163 182
74 115
93 61
151 83
81 119
10 146
114 170
39 83
139 4
173 41
193 96
87 57
14 164
107 51
45 15
157 17
43 183
96 30
11 137
55 18
138 81
87 12
112 122
159 82
195 185
75 71
16 191
33 88
70 195
149 114
106 160
96 118
92 44
9 141
107 143
151 2...

output:

57921623677
112
1 135 89 194 179 151 179 194 89 27 40 112 125 180 120 117 122 72 99 33 131 105 96 114 171 28 110 149 59 170 193 138 94 162 88 21 45 138 94 162 88 21 193 59 170 149 110 28 171 114 131 105 96 33 12 76 70 53 159 17 178 24 44 41 67 173 116 42 186 92 32 5 101 197 82 121 198 29 87 64 93 19...

result:

wrong answer your claimed profit is 57921623677 but the profit of your plan is 65759356357

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%
English 繁體中文 简体中文

Server Time: 2024-12-11 01:00:44 | OpenSource Project