Submission #201689

#	Time	Username	Problem	Language	Result	Execution time	Memory
201689		Saboon	Usmjeri (COCI17_usmjeri)	C++14	140 / 140	522 ms	62716 KiB

usmjeri

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 300000 + 10;
const int mod = 1e9 + 7;

vector<int> t[maxn];
int par[maxn][20], h[maxn], p[maxn];

struct DSU{
	int cmp;
	int par[maxn];
	int w[maxn];
	DSU(){
		memset(par, -1, sizeof par);
	}
	pair<int,bool> get_par(int v){
		if (par[v] < 0)
			return make_pair(v, 0);
		auto it = get_par(par[v]);
		par[v] = it.first, w[v] = it.second ^ w[v];
		return make_pair(par[v], w[v]);
	}
	void merge(int v, int u, bool w){
		auto pv = get_par(v), pu = get_par(u);
		if (pv.first == pu.first){
			if (w ^ pv.second ^ pu.second){
				cout << 0 << endl;
				exit(0);
			}
			return;
		}
		cmp --;
		par[pv.first] = pu.first;
		this->w[pv.first] = pv.second ^ w ^ pu.second;
	}
} dsu;

void dfs2(int v, int parent = -1){
	for (auto u : t[v]){
		if (u == parent)
			continue;
		dfs2(u, v);
		p[v] += p[u];
	}
	if (p[v])
		dsu.merge(v, parent, 0);
}

int getpar(int v, int x){
	for (int i = 0; i < 20; i++)
		if (x & (1 << i))
			v = par[v][i];
	return v;
}

int lca(int v, int u){
	if (h[v] < h[u])
		swap(v, u);
	for (int i = 19; i >= 0; i--)
		if (h[v] - (1 << i) >= h[u])
			v = par[v][i];
	if (v == u)
		return v;
	for (int i = 19; i >= 0; i--)
		if (par[v][i] != par[u][i])
			v = par[v][i], u = par[u][i];
	return par[v][0];
}

void dfs(int v, int parent = -1){
	par[v][0] = parent;
	for (int i = 1; i < 20 and par[v][i - 1] != -1; i++)
		par[v][i] = par[par[v][i - 1]][i - 1];
	for (auto u : t[v]){
		if (u == parent)
			continue;
		h[u] = h[v] + 1;
		dfs(u, v);
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n - 1; i++){
		int v, u;
		cin >> v >> u;
		t[v].push_back(u);
		t[u].push_back(v);
	}
	memset(par, -1, sizeof par);
	dfs(1);
	dsu.cmp = n - 1;
	for (int i = 0; i < m; i++){
		int v, u;
		cin >> v >> u;
		int w = lca(v, u);
		if (v != w and u != w){
			int vp = getpar(v, h[v] - h[w] - 1);
			int up = getpar(u, h[u] - h[w] - 1);
			dsu.merge(vp, up, 1);
		}
		if (h[v] - h[w] >= 2){
			int diff = h[v] - h[w];
			p[v] ++;
			p[getpar(v, diff - 1)] --;
		}
		if (h[u] - h[w] >= 2){
			int diff = h[u] - h[w];
			p[u] ++;
			p[getpar(u, diff - 1)] --;
		}
	}
	dfs2(1);
	int ans = 1;
	while (dsu.cmp --){
		ans = ans * 2 % mod;
	}
	cout << ans << '\n';
}

• 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