제출 #707900

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
707900		vjudge1	새로운 문제 (POI13_mul)	C++17	29 / 100	204 ms	36632 KiB

mul

#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);
			if(!dp[v][0])if(!dp[v][1])dp[u][1]=0;else if(++ct>1)dp[u][1]=0;
			if(!dp[v][0])if(!dp[v][1])dp[u][2]=0;else if(++cnt>2)dp[u][2]=0;
			/*
			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;
}

컴파일 시 표준 에러 (stderr) 메시지

mul.cpp: In function 'void dfs(int, int)':
mul.cpp:33:6: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   33 |    if(!dp[v][0])if(!dp[v][1])dp[u][1]=0;else if(++ct>1)dp[u][1]=0;
      |      ^
mul.cpp:34:6: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   34 |    if(!dp[v][0])if(!dp[v][1])dp[u][2]=0;else if(++cnt>2)dp[u][2]=0;
      |      ^

• Subtask 1: 4 / 4
• Subtask 2: 4 / 4
• Subtask 3: 4 / 4
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 4 / 4
• Subtask 7: 0 / 4
• Subtask 8: 0 / 4
• Subtask 9: 0 / 4
• Subtask 10: 0 / 4
• Subtask 11: 0 / 5
• Subtask 12: 0 / 5
• Subtask 13: 0 / 5
• Subtask 14: 0 / 5
• Subtask 15: 0 / 5
• Subtask 16: 0 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5
• Subtask 20: 0 / 5
• Subtask 21: 0 / 5
• Subtask 22: 5 / 5