QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#114021#6629. Travelling Trader1kri0 2ms9880kbC++146.6kb2023-06-20 15:32:252023-06-20 15:32:29

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

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]==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++)
				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: 0
Wrong Answer
time: 2ms
memory: 9880kb

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

Server Time: 2024-12-07 09:54:48 | OpenSource Project