Submission #707891

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
707891	2023-03-10T11:18:42 Z	vjudge1	Multidrink (POI13_mul)	C++17	29 / 100	173 ms	43336 KB

#include<bits/stdc++.h>
#define N 5000005
using namespace std;
int read(){
	int w=0,h=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')h=-h;ch=getchar();}
	while(ch>='0'&&ch<='9'){w=w*10+ch-'0';ch=getchar();}
	return w*h;
}
struct Edge{int next,to;}edge[N<<1];
int n,from[N];
bool dp[N][3],f[N][2],on[N];
// 0: u->u
// 1: u->son son->u
// 2: son->son
int head[N],num;
vector<int>vec,ans;
void add(int u,int v){edge[++num]=(Edge){head[u],v};head[u]=num;}
bool FindChain(int u,int fa){
	if(u==n)return true;
	for(int i=head[u],v;i;i=edge[i].next)
		if((v=edge[i].to)!=fa&&!on[v])
			if(FindChain(v,u))
				return vec.emplace_back(v),from[v]=u,true;
	return false;
}
void dfs(int u,int fa){
	dp[u][0]=(edge[head[u]].next==0);
	dp[u][1]=dp[u][2]=dp[u][0]^1;
	for(int i=head[u],v,ct=0,cnt=0;i;i=edge[i].next)
		if((v=edge[i].to)!=fa&&!on[v]){
			dfs(v,u);
			dp[u][1]&=(dp[v][0]||(dp[v][1]&&ct++==0));
			dp[u][2]&=(dp[v][0]||(dp[v][1]&&cnt++<=1));
		}
}
void sfd(int u,int fa,int t){
	if(t==0)return void(ans.emplace_back(u));
	if(t==1){
		ans.emplace_back(u);
		for(int i=head[u],v;i;i=edge[i].next)
			if((v=edge[i].to)!=fa&&!on[v]&&dp[v][0]==0)sfd(v,u,2);
		for(int i=head[u],v;i;i=edge[i].next)
			if((v=edge[i].to)!=fa&&!on[v]&&dp[v][0])sfd(v,u,0);
	}
	if(t==2){
		for(int i=head[u],v;i;i=edge[i].next)
			if((v=edge[i].to)!=fa&&!on[v]&&dp[v][0])sfd(v,u,0);
		for(int i=head[u],v;i;i=edge[i].next)
			if((v=edge[i].to)!=fa&&!on[v]&&dp[v][0]==0)sfd(v,u,1);
		ans.emplace_back(u);
	}
	if(t==3){
		int cnt=0;
		for(int i=head[u],v;i;i=edge[i].next)
			cnt+=((v=edge[i].to)!=fa&&!on[v]&&dp[v][0]==0);
		if(cnt<2)return sfd(u,fa,1);
		for(int i=head[u],v,ct=0;i;i=edge[i].next)
			if((v=edge[i].to)!=fa&&!on[v]&&dp[v][0]==0){
				if(ct==0)ct++,sfd(v,u,1),ans.emplace_back(u);
				else sfd(v,u,2);
			}
		for(int i=head[u],v;i;i=edge[i].next)
			if((v=edge[i].to)!=fa&&!on[v]&&dp[v][0])sfd(v,u,0);
	}
}
void Construct(int u,int t){
	if(u==1)return void(sfd(u,0,t));
	if(t==0)Construct(from[u],f[from[u]][0]?0:1),sfd(u,0,dp[u][0]?0:2);
	else Construct(from[u],f[from[u]][0]?0:1),sfd(u,0,dp[u][1]?1:3);
}
signed main(){
	n=read();
	for(int i=2,u,v;i<=n;i++)u=read(),v=read(),add(u,v),add(v,u);
	FindChain(1,0);
	vec.emplace_back(1);
	reverse(vec.begin(),vec.end());
	assert(*vec.begin()==1);assert(vec.back()==n);
	for(auto u:vec)on[u]=true;
	for(auto u:vec)dfs(u,0);
	f[1][0]=dp[1][0];f[1][1]=dp[1][1];
	for(int i=1,len=vec.size();i<len;i++){
		int u=vec[i],v=vec[i-1];
		f[u][0]=(f[v][0]&&(dp[u][0]||dp[u][1]))||(f[v][1]&&dp[u][0]);
		f[u][1]=(f[v][0]&&(dp[u][1]||dp[u][2]))||(f[v][1]&&dp[u][1]);
	}
	if(f[n][0]==0)return puts("BRAK"),0;
	Construct(n,0);
	for(auto u:ans)printf("%d\n",u);
	return 0;
}

Subtask #1
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	1 ms	308 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	308 KB	Output is correct

Subtask #2
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	1 ms	308 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct

Subtask #3
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct

Subtask #4
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	308 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct

Subtask #5
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	316 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct

Subtask #6
4.0 / 4.0

#	Verdict	Memory	Grader output
1	Correct	340 KB	Output is correct
2	Correct	340 KB	Output is correct
3	Correct	340 KB	Output is correct
4	Correct	340 KB	Output is correct
5	Correct	340 KB	Output is correct
6	Correct	340 KB	Output is correct

Subtask #7
0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	316 KB	Expected integer, but "BRAK" found
2	Halted	0 ms	0 KB	-

Subtask #8
0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	340 KB	Expected integer, but "BRAK" found
2	Halted	0 ms	0 KB	-

Subtask #9
0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	340 KB	Expected integer, but "BRAK" found
2	Halted	0 ms	0 KB	-

Subtask #10
0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	340 KB	Expected integer, but "BRAK" found
2	Halted	0 ms	0 KB	-

Subtask #11
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	340 KB	Expected integer, but "BRAK" found
2	Halted	0 ms	0 KB	-

Subtask #12
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	340 KB	Expected integer, but "BRAK" found
2	Halted	0 ms	0 KB	-

Subtask #13
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	312 KB	Expected integer, but "BRAK" found
2	Halted	0 ms	0 KB	-

Subtask #14
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	596 KB	Expected integer, but "BRAK" found
2	Halted	0 ms	0 KB	-

Subtask #15
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	448 KB	Output is correct
2	Incorrect	1 ms	340 KB	Expected integer, but "BRAK" found
3	Halted	0 ms	0 KB	-

Subtask #16
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	13 ms	6104 KB	Expected integer, but "BRAK" found
2	Halted	0 ms	0 KB	-

Subtask #17
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	11 ms	6100 KB	Expected integer, but "BRAK" found
2	Halted	0 ms	0 KB	-

Subtask #18
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	3904 KB	Output is correct
2	Incorrect	0 ms	340 KB	Expected integer, but "BRAK" found
3	Halted	0 ms	0 KB	-

Subtask #19
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	87 ms	21480 KB	Expected integer, but "BRAK" found
2	Halted	0 ms	0 KB	-

Subtask #20
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	90 ms	21536 KB	Expected integer, but "BRAK" found
2	Halted	0 ms	0 KB	-

Subtask #21
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	114 ms	26652 KB	Expected integer, but "BRAK" found
2	Halted	0 ms	0 KB	-

Subtask #22
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	173 ms	43288 KB	Output is correct
2	Correct	131 ms	43336 KB	Output is correct

Submission #707891

Compilation message