oj.uz

Submission #38680

# Submission time Handle Problem Language Result Execution time Memory
38680 2018-01-06T02:17:12 Z adamczh1 Usmjeri (COCI17_usmjeri) C++14
28 / 140
 1296 ms 82564 KB 
/*
consider dual graph (where edges are vertices)
draw corresponding paths in dual graph
if there is cycle answer = 0
else answer is 2^number of components
*/
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

#define SIZE(x) (int)(x).size()
#define ff first
#define ss second

inline ll readi(){
	ll x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

const int MAXN=3e5+5;
const int MOD=1e9+7;

int N, M;
vector<int> adj[MAXN];
int par[20][MAXN];
int dep[MAXN];

void dfs(int cur,int p=1){
	if(cur!=1)dep[cur]=dep[p]+1;
	par[0][cur]=p;
	for(int i=1;i<20;i++){
		par[i][cur]=par[i-1][par[i-1][cur]];
	}
	for(int v:adj[cur]) if(v!=p){
		dfs(v,cur);
	}
}

pii lca_ch(int u,int v){ // children of lca
	if(dep[u]<dep[v]) swap(u,v);
	for(int i=19;i>=0;i--){
		if(dep[par[i][u]]>dep[v]){
			u=par[i][u];
		}
	}
	if(par[0][u]==v) return pii(u,u);
	if(dep[u]!=dep[v])u=par[0][u];
	for(int i=19;i>=0;i--){
		if(par[i][u]!=par[i][v]){
			u=par[i][u],v=par[i][v];
		}
	}
	return pii(u,v);
}

int delta[MAXN];
int val[MAXN];
void dfs2(int cur,int p=-1){
	val[cur]=delta[cur];
	for(int v:adj[cur])if(v!=p){
		dfs2(v,cur);
		val[cur]+=val[v];
	}
}

set<int> g[MAXN];
int vis[MAXN];
bool onstack[MAXN];
bool hascycle;
void dfs3(int cur,int p=-1){
	vis[cur]=1;
	onstack[cur]=1;
	for(int v:g[cur])if(v!=p){
		if(!vis[v])dfs3(v,cur);
		else if(onstack[v]){
			hascycle=1;
		}
	}
	onstack[cur]=0;
}

int main(){
	N=readi(), M=readi();
	for(int i=1; i<N; i++){
		int u=readi(), v=readi();
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	dfs(1);
	for(int i=0; i<M; i++){
		int a=readi(),b=readi();
		pii p=lca_ch(a,b);
		int c=p.ff;
		int d=p.ss;
		if(c==d){
			if(par[0][c]==a){
				delta[b]++;
				delta[a]--;
			}
			else{
				delta[a]++;
				delta[b]--;
			}
		}
		else{
			g[c].insert(d);
			g[d].insert(c);
			delta[a]++;
			delta[b]++;
			delta[par[0][c]]-=2;
		}
	}
	dfs2(1);
	for(int i=1; i<=N; i++){
		if(val[i]){
			for(int v:adj[i]){
				if(val[v]) g[i].insert(v);
			}
		}
	}
	int leftover=N-1;
	ll ans=1;
	for(int i=2; i<=N; i++){
		if(!vis[i]){
			hascycle=0;
			dfs3(i);
			if(hascycle){
				cout<<0<<endl;
				return 0;
			}
			ans=ans*2%MOD;
		}
	}
	cout<<ans<<endl;
	return 0;
}

Compilation message

usmjeri.cpp: In function 'int main()':
usmjeri.cpp:125:6: warning: unused variable 'leftover' [-Wunused-variable]
  int leftover=N-1;
      ^

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 63860 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 306 ms 82564 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 51664 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 51664 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 52060 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 52060 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 729 ms 64240 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1296 ms 64904 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1006 ms 64376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1029 ms 64900 KB Output isn't correct
2 Halted 0 ms 0 KB -