Submission #38682

#	Time	Username	Problem	Language	Result	Execution time	Memory
38682		adamczh1	Usmjeri (COCI17_usmjeri)	C++14	126 / 140	1296 ms	76412 KiB

usmjeri

/*
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 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 0 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14