oj.uz

Submission #51561

# Submission time Handle Problem Language Result Execution time Memory
51561 2018-06-18T15:41:52 Z Adhyyan1252 Usmjeri (COCI17_usmjeri) C++11
0 / 140
 1219 ms 103892 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 = 0; i < LOGN; i++){
		if(dep[b] - (1<<i) >= dep[a]){
			b = f[b][i];
		}
	}
	if(a == b) return a;
	for(int i = 0; i < LOGN; 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*2)%1000000007;
		cout<<ans<<endl;
	}else{
		cout<<0<<endl;
	}
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 575 ms 46032 KB Output isn't correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 938 ms 95860 KB Output isn't correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 95860 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 95860 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 95860 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 95860 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

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

Subtask #8
0 / 14.0

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

Subtask #9
0 / 14.0

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

Subtask #10
0 / 14.0

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