oj.uz

Submission #110073

# Submission time Handle Problem Language Result Execution time Memory
110073 2019-05-09T08:53:12 Z maruii Usmjeri (COCI17_usmjeri) C++14
140 / 140
 791 ms 66040 KB 
#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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 32824 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 64836 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 15872 KB Output is correct
2 Correct 18 ms 16000 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 15872 KB Output is correct
2 Correct 19 ms 16000 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 16384 KB Output is correct
2 Correct 21 ms 16384 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 16384 KB Output is correct
2 Correct 22 ms 16356 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 672 ms 52980 KB Output is correct
2 Correct 791 ms 62892 KB Output is correct
3 Correct 281 ms 46136 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 640 ms 57308 KB Output is correct
2 Correct 705 ms 64888 KB Output is correct
3 Correct 485 ms 49656 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 479 ms 57464 KB Output is correct
2 Correct 750 ms 61688 KB Output is correct
3 Correct 391 ms 49844 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 619 ms 57856 KB Output is correct
2 Correct 550 ms 66040 KB Output is correct
3 Correct 488 ms 46648 KB Output is correct