oj.uz

Submission #38682

# Submission time Handle Problem Language Result Execution time Memory
38682 2018-01-06T03:06:55 Z adamczh1 Usmjeri (COCI17_usmjeri) C++14
126 / 140
 1296 ms 76412 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]){
		pii x=lca_ch(v,u);
		return pii(x.ss,x.ff);
	}
	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 link[MAXN];
set<int> g[MAXN];

void dfs2(int cur,int p=-1){
	for(int v:adj[cur])if(v!=p){
		dfs2(v,cur);
		if(dep[link[cur]]>dep[link[v]]){
			link[cur]=link[v];
		}
	}
	if(dep[link[cur]]<dep[cur]){
		g[cur].insert(p);
		g[p].insert(cur);
	}
}


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

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=1; i<=N; i++){
		link[i]=i;
	}
	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){
				if(dep[link[b]]>dep[c]){
					link[b]=c;
				}
			}
			else{
				if(dep[link[a]]>dep[c]){
					link[a]=c;
				}
			}
		}
		else{
			g[c].insert(d);
			g[d].insert(c);
			if(link[a]==0 || dep[link[a]]>dep[c]){
				link[a]=c;
			}
			if(link[b]==0 || dep[link[b]]>dep[d]){
				link[b]=d;
			}
		}
	}
	dfs2(1);
	ll ans=1;
	for(int i=2; i<=N; i++){
		if(!vis[i]){
			dfs3(i);
			if(hascycle){
				cout<<0<<endl;
				return 0;
			}
			ans=ans*2%MOD;
		}
	}
	cout<<ans<<endl;
	return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 60832 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 76412 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 50200 KB Output is correct
2 Correct 6 ms 50200 KB Output is correct

Subtask #4
0 / 14.0

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

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 50464 KB Output is correct
2 Correct 9 ms 50332 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 50464 KB Output is correct
2 Correct 13 ms 50332 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 819 ms 62672 KB Output is correct
2 Correct 899 ms 67224 KB Output is correct
3 Correct 553 ms 59968 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1296 ms 63204 KB Output is correct
2 Correct 1159 ms 62276 KB Output is correct
3 Correct 773 ms 60628 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1099 ms 62608 KB Output is correct
2 Correct 789 ms 65884 KB Output is correct
3 Correct 633 ms 59844 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 983 ms 63228 KB Output is correct
2 Correct 966 ms 62564 KB Output is correct
3 Correct 689 ms 67624 KB Output is correct