oj.uz

Submission #707900

# Submission time Handle Problem Language Result Execution time Memory
707900 2023-03-10T11:37:09 Z vjudge1 Multidrink (POI13_mul) C++17
29 / 100
 204 ms 36632 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);
			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;
}

Compilation message

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.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 340 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 0 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 #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 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct

Subtask #4
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 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 0 ms 340 KB Output is correct

Subtask #5
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 1 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 #6
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 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 0 ms 340 KB Output is correct

Subtask #7
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 #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 0 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 1 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 0 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 340 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 468 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 408 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 4992 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 12 ms 5032 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 2644 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 95 ms 14768 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 91 ms 14832 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 126 ms 19992 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 204 ms 36632 KB Output is correct
2 Correct 118 ms 36556 KB Output is correct