Submission #34852

#	Time	Username	Problem	Language	Result	Execution time	Memory
34852		szawinis	Usmjeri (COCI17_usmjeri)	C++14	140 / 140	946 ms	128740 KiB

usmjeri

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5+1;
const long long MOD = 1e9+7;

int n, m, d[N], mp[N], dsu[2*N];
vector<pair<int,int> > g[N], rem[N];
vector<int> par[N];
priority_queue<int, vector<int>, greater<int> > df[N];

int root(int v) { return (dsu[v] < 0 ? v : dsu[v] = root(dsu[v])); }
void merge(int u, int tpu, int v, int tpv) {
	u += n*tpu; v += n*tpv;
	if((u = root(u)) == (v = root(v))) return;
	if(dsu[u] > dsu[v]) swap(u, v);
	dsu[u] += dsu[v];
	dsu[v] = u;
}

void init_lca(int u, int p) {
	for(auto v: g[u]) if(v.first != p) {
		d[v.first] = d[u] + 1;
		par[v.first].push_back(u);
		for(int j = 0; 1 << j+1 <= d[v.first]; j++)
			par[v.first].push_back(par[par[v.first][j]][j]);
		init_lca(v.first, u);
	}
}

int get_lca(int u, int v) {
	if(d[v] > d[u]) swap(u, v);
	if(d[u] > d[v]) for(int j = 0; 1 << j <= d[u] - d[v]; j++)
		if(d[u] - d[v] >> j & 1) u = par[u][j];
	if(u == v) return u;
	for(int j = 31 - __builtin_clz(d[u]); j >= 0; j--) if(j < par[u].size() && par[u][j] != par[v][j]) {
		u = par[u][j];
		v = par[v][j];
	}
	return par[u][0];
}

int find_child(int u, int v) {
	assert(d[v] > d[u]);
	for(int j = 31 - __builtin_clz(d[v] - d[u] - 1); j >= 0; j--)
		if(d[v] - d[u] - 1 >> j & 1) v = par[v][j];
	return v;
}

void dfs(int u, int par, int pedge_id) {
	for(auto v: g[u]) if(v.first != par){
		dfs(v.first, u, v.second);
		mp[v.first] = v.second;
		if(!df[v.first].empty() && df[v.first].top() < d[u]) {
			merge(pedge_id, 0, v.second, 0);
			merge(pedge_id, 1, v.second, 1);
		}
		if(df[v.first].size() > df[u].size()) swap(df[u], df[v.first]);
		while(!df[v.first].empty()) df[u].push(df[v.first].top()), df[v.first].pop();
	}
	for(auto p: rem[u]) if(p.first != u && p.second != u) {
		int x = find_child(u, p.first), y = find_child(u, p.second);
		merge(mp[x], 0, mp[y], 1);
		merge(mp[x], 1, mp[y], 0);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	for(int i = 1, u, v; i < n; i++) {
		cin >> u >> v;
		g[u].emplace_back(v, i);
		g[v].emplace_back(u, i);
	}
	init_lca(1, -1);
	for(int i = 0, u, v; i < m; i++) {
		cin >> u >> v;
		int lca = get_lca(u, v);
		rem[lca].emplace_back(u, v);
		df[u].push(d[lca]);
		df[v].push(d[lca]);
	}
	fill(dsu+1, dsu+2*n, -1);
	dfs(1, -1, -1);
	for(int i = 1; i < n; i++) if(root(i) == root(n+i)) {
		cout << 0;
		return 0;
	}
	for(int i = 1; i < n; i++) merge(i, 0, i, 1);
	vector<int> ccs;
	for(int i = 1; i < n; i++) ccs.push_back(root(i));
	sort(ccs.begin(), ccs.end());
	ccs.resize(distance(ccs.begin(), unique(ccs.begin(), ccs.end())));
	long long ans = 1, b = 2, e = ccs.size();
	while(e) {
		if(e & 1) ans = (ans * b) % MOD;
		b = (b*b) % MOD;
		e >>= 1;
	}
	cout << ans;
}
// check if there exists some in subtree v such that depth of lca < depth of u -> 0 0 1 1
// for all pairs which are lca at u, v do 0 1 1 0

Compilation message (stderr)

usmjeri.cpp: In function 'void init_lca(int, int)':
usmjeri.cpp:24:24: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   for(int j = 0; 1 << j+1 <= d[v.first]; j++)
                        ^
usmjeri.cpp: In function 'int get_lca(int, int)':
usmjeri.cpp:33:11: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   if(d[u] - d[v] >> j & 1) u = par[u][j];
           ^
usmjeri.cpp:35:58: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j = 31 - __builtin_clz(d[u]); j >= 0; j--) if(j < par[u].size() && par[u][j] != par[v][j]) {
                                                          ^
usmjeri.cpp: In function 'int find_child(int, int)':
usmjeri.cpp:45:18: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   if(d[v] - d[u] - 1 >> j & 1) v = par[v][j];
                  ^

• 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