Submission #110073

#	Time	Username	Problem	Language	Result	Execution time	Memory
110073		maruii	Usmjeri (COCI17_usmjeri)	C++14	140 / 140	791 ms	66040 KiB

usmjeri

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define ff first
#define ss second

vector<int> edge0[300002];
vector<pii> edge[300002];
int prt[19][300002], dth[300002], par[300002];
int fnd(int x){return x==par[x]?x:par[x]=fnd(par[x]);}
void uni(int x, int y){
	x = fnd(x), y = fnd(y);
	if(x==y) return;
	if(dth[x]<dth[y]) swap(x, y);
	par[x] = y;
}
void dfs0(int x, int p){
	prt[0][x] = p;
	dth[x] = dth[p] + 1;
	for(auto i: edge0[x]){
		if(i==p) continue;
		dfs0(i, x);
	}
}

int lca(int x, int y){
	if(dth[x]<dth[y]) swap(x, y);
	for(int i=18; i>=0; --i) if(dth[prt[i][x]]>=dth[y]) x = prt[i][x];
	if(x==y) return x;
	for(int i=18; i>=0; --i) if(prt[i][x]!=prt[i][y]) x = prt[i][x], y = prt[i][y];
	return prt[0][x];
}

const int mod = 1e9+7;
bool used[300001];
int dir[300001];
bool dfs(int x, int p, int c){
	if(dir[x] != -1) return dir[x] == c;
	dir[x] = c;
	for(auto i: edge[x]){
		if(p==i.ss) continue;
		if(!dfs(i.ss, x, c ^ i.ff)) return 0;
	}
	return 1;
}
int main(){
	ios_base::sync_with_stdio(0), cin.tie(0);
	int N, M; cin>>N>>M;
	for(int i=1; i<N; ++i){
		int x,y; cin>>x>>y;
		edge0[x].push_back(y), edge0[y].push_back(x);
	}
	iota(par, par+N+1, 0);
	dfs0(1, 0);
	for(int i=1; i<19; ++i) for(int j=1; j<=N; ++j) prt[i][j] = prt[i-1][prt[i-1][j]]; 

	for(int i=0; i<M; ++i){
		int x,y,l; cin>>x>>y;
		l = lca(x, y);
		if(l!=x && l!=y) edge[x].emplace_back(1, y), edge[y].emplace_back(1, x);
		for(int v=fnd(x); dth[prt[0][v]]>dth[l]; v=fnd(prt[0][v])){
			edge[v].emplace_back(0, prt[0][v]), edge[prt[0][v]].emplace_back(0, v);
			uni(v, prt[0][v]);
		}
		for(int v=fnd(y); dth[prt[0][v]]>dth[l]; v=fnd(prt[0][v])){
			edge[v].emplace_back(0, prt[0][v]), edge[prt[0][v]].emplace_back(0, v);
			uni(v, prt[0][v]);
		}
	}
	memset(dir, -1, sizeof(dir));
	int ans = 1;
	for(int i=2; i<=N; ++i) if(dir[i]==-1){
		if(dfs(i, 0, 0)) ans = (ans<<1)%mod;
		else return !printf("0");
	}
	cout<<ans;
	return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 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