Submission #38681

#	Time	Username	Problem	Language	Result	Execution time	Memory
38681		adamczh1	Usmjeri (COCI17_usmjeri)	C++14	28 / 140	1133 ms	82276 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]) 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 hascycle;
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=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);
			}
		}
	}
	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;
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14