QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#114020#6629. Travelling Trader1kri0 3ms13896kbC++146.6kb2023-06-20 15:30:572023-06-20 15:31:00

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:31:00]
  • 评测
  • 测评结果：0
  • 用时：3ms
  • 内存：13896kb
查看
  • [2023-06-20 15:30:57]
  • 提交

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++)
			for (int j=0;j<len;j++){
				for (int k=0;k<len;k++){
					if (i!=j&&i!=k&&j!=k)
						f0[now]=max(f0[now],g1[c[i]]-a[c[i]]+g0[c[j]]-a[c[j]]+f1[c[k]]-a[c[k]]);
				}
			}
		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]==g1[_x]-a[_x]+f0[_y]-a[_y])x=_x,y=_y;
				_x=c[t],_y=id0[1][t-1];
				if (f0[now]==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++)
				for (int j=0;j<len;j++){
					for (int k=0;k<len;k++){
						if (i!=j&&i!=k&&j!=k)
							if (f0[now]==a[now]+sum+g1[c[i]]-a[c[i]]+g0[c[j]]-a[c[j]]+f1[c[k]]-a[c[k]]){
								for (int l=0;l<len;l++)
									if (c[l]!=c[i]&&c[l]!=c[j]&&c[l]!=c[k]&&c[l]!=0)id[++tot]=c[l];
								if (c[i]!=0)dfs2(c[i],now,3);
								id[++tot]=now;
								if (c[j]!=0)dfs2(c[j],now,2);
								if (c[k]!=0)dfs2(c[k],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: 13888kb

input:

2 2
2 1
243296356 635616793

output:

878913149
2
1 2

result:

ok correct!

Test #13:

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

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: 0ms
memory: 13896kb

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
9
1 135 89 194 179 151 39 83 27

result:

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

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-09 04:24:45 | OpenSource Project