Submission #51564

#	Time	Username	Problem	Language	Result	Execution time	Memory
51564		Adhyyan1252	Usmjeri (COCI17_usmjeri)	C++11	140 / 140	1059 ms	107880 KiB

usmjeri

#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 / 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