oj.uz

답안 #707903

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
707903 2023-03-10T11:38:42 Z vjudge1 Multidrink (POI13_mul) C++17
100 / 100
 206 ms 40504 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]=dp[u][1]=dp[u][2]=1;
	/*
	dp[u][0]=(edge[head[u]].next==0);
	dp[u][1]=dp[u][2]=dp[u][0]^1;
	*/
	int son=0;
	for(int i=head[u],v,ct=0,cnt=0;i;i=edge[i].next)
		if((v=edge[i].to)!=fa&&!on[v]){
			son++;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));
		}
	if(son)dp[u][0]=0;else dp[u][1]=dp[u][2]=0;
}
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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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

Subtask #2
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 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 1 ms 340 KB Output is correct

Subtask #3
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 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 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #4
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 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 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct

Subtask #5
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 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 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct

Subtask #6
4.0 / 4.0

# 결과 실행 시간 메모리 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 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct

Subtask #7
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct

Subtask #8
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct

Subtask #9
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct

Subtask #10
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct

Subtask #11
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct

Subtask #12
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct

Subtask #13
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct

Subtask #14
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 596 KB Output is correct

Subtask #15
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 0 ms 340 KB Output is correct

Subtask #16
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 6028 KB Output is correct

Subtask #17
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 5956 KB Output is correct

Subtask #18
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 2644 KB Output is correct
2 Correct 0 ms 340 KB Output is correct

Subtask #19
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 145 ms 20324 KB Output is correct

Subtask #20
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 159 ms 20280 KB Output is correct

Subtask #21
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 206 ms 25412 KB Output is correct
2 Correct 155 ms 32028 KB Output is correct

Subtask #22
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 173 ms 40504 KB Output is correct
2 Correct 115 ms 40496 KB Output is correct