oj.uz

Submission #51564

# Submission time Handle Problem Language Result Execution time Memory
51564 2018-06-18T15:50:25 Z Adhyyan1252 Usmjeri (COCI17_usmjeri) C++11
140 / 140
 1059 ms 107880 KB 
#include<bits/stdc++.h>

using namespace std;
#define NMAX 300005
#define LOGN 19
vector<int> g[NMAX];

int f[NMAX][LOGN];
int dep[NMAX];
void root(int cur, int par = -1, int depth = 0){
	f[cur][0] = par;
	dep[cur] = depth;
	for(auto child: g[cur]){
		if(child == par) continue;
		root(child, cur, depth+1);
	}
}

int n, m;

void init(){
	for(int i = 1; i < LOGN; i++)
		for(int j = 0; j < n; j++)
			if(f[j][i-1] != -1)
				f[j][i] = f[f[j][i-1]][i-1];
			else 
				f[j][i] = -1;
}

int lca(int a, int b){
	if(dep[a] > dep[b]) swap(a, b); // a has lesser depth
	for(int i = LOGN-1; i >= 0; i--){
		if(dep[b] - (1<<i) >= dep[a]){
			b = f[b][i];
		}
	}
	if(a == b) return a;
	for(int i = LOGN-1; i >= 0; i--){
		if(f[a][i] != f[b][i]){
			a = f[a][i];
			b = f[b][i];
		}
	}
	return f[a][0];
}

struct node{
	int a, b, par;
};

node ps[NMAX];

vector<pair<int, bool> > h[NMAX];
int low[NMAX];

int connect(int cur, int par){
	for(auto child: g[cur]){
		if(child == par) continue;
		low[cur] = min(low[cur], connect(child, cur));
	}
	if(cur != 0)
		if(low[cur] < dep[cur] - 1){
			h[cur].push_back({f[cur][0], false});
			h[f[cur][0]].push_back({cur, false});
		}
	return low[cur];
}

bool pos = true;
int col[NMAX];

void check(int cur, int ccol){
	if(col[cur] != -1){
		if(col[cur] != ccol){
			pos = false;
		}
		return;
	}
	col[cur] = ccol;
	for(auto child: h[cur]){
		check(child.first, ccol^child.second);
	}
}

int main(){
	cin>>n>>m;
	for(int i = 0; i < n-1; i++){
		int u, v; cin>>u>>v; u--; v--;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for(int i = 0; i < m; i++){
		cin>>ps[i].a>>ps[i].b; ps[i].a--; ps[i].b--;
	}
	root(0);
	init();
	for(int i = 0; i < n; i++){
		low[i] = 10000000;
		col[i] = -1;
	}
	for(int i = 0; i < m; i++){
		ps[i].par = lca(ps[i].a, ps[i].b);
		if(ps[i].par == ps[i].a || ps[i].par == ps[i].b){	
		}else{
			h[ps[i].a].push_back({ps[i].b, true});
			h[ps[i].b].push_back({ps[i].a, true});
		}
		low[ps[i].a] = min(low[ps[i].a], dep[ps[i].par]);
		low[ps[i].b] = min(low[ps[i].b], dep[ps[i].par]);
		//cout<<"LCA: "<<ps[i].par<<endl;
	}
	connect(0, -1);
//	for(int i = 1; i < n; i++){
//		cout<<i<<" : ";
//		for(auto child: h[i]){
//			cout<<"( "<<child.first<<", "<<child.second<<" ) ";
//		}
//		cout<<endl;
//	}
	int comp = 0;
	for(int i = 1; i < n; i++){
		if(col[i] == -1){
			comp++;
			check(i, 0);
		}
	}	
	if(pos){
		long long ans = 1;
		for(int i = 0; i < comp; i++) ans = (ans*2LL)%1000000007;
		cout<<ans<<endl;
	}else{
		cout<<0<<endl;
	}
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 310 ms 37496 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 672 ms 77732 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 77732 KB Output is correct
2 Correct 17 ms 77732 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 77732 KB Output is correct
2 Correct 19 ms 77732 KB Output is correct

Subtask #5
14.0 / 14.0

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

Subtask #6
14.0 / 14.0

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

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 859 ms 77732 KB Output is correct
2 Correct 963 ms 77732 KB Output is correct
3 Correct 492 ms 77732 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 965 ms 77732 KB Output is correct
2 Correct 884 ms 80676 KB Output is correct
3 Correct 615 ms 80676 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1040 ms 86540 KB Output is correct
2 Correct 1010 ms 90376 KB Output is correct
3 Correct 665 ms 90376 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1059 ms 99716 KB Output is correct
2 Correct 914 ms 107880 KB Output is correct
3 Correct 543 ms 107880 KB Output is correct