oj.uz

Submission #110071

# Submission time Handle Problem Language Result Execution time Memory
110071 2019-05-09T08:42:02 Z maruii Usmjeri (COCI17_usmjeri) C++14
28 / 140
 663 ms 71932 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(x!=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, 1)) 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 200 ms 36504 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 347 ms 71932 KB Output is correct

Subtask #3
0 / 14.0

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

Subtask #4
0 / 14.0

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

Subtask #5
0 / 14.0

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

Subtask #6
0 / 14.0

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

Subtask #7
0 / 14.0

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

Subtask #8
0 / 14.0

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

Subtask #9
0 / 14.0

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

Subtask #10
0 / 14.0

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