oj.uz

Submission #201689

# Submission time Handle Problem Language Result Execution time Memory
201689 2020-02-11T17:32:50 Z Saboon Usmjeri (COCI17_usmjeri) C++14
140 / 140
 522 ms 62716 KB 
#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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 42360 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 341 ms 62716 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 32120 KB Output is correct
2 Correct 25 ms 32120 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 32124 KB Output is correct
2 Correct 23 ms 32120 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 32296 KB Output is correct
2 Correct 25 ms 32248 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 32288 KB Output is correct
2 Correct 25 ms 32376 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 463 ms 45480 KB Output is correct
2 Correct 507 ms 53368 KB Output is correct
3 Correct 253 ms 44536 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 522 ms 48888 KB Output is correct
2 Correct 490 ms 52856 KB Output is correct
3 Correct 322 ms 46056 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 487 ms 45560 KB Output is correct
2 Correct 475 ms 53368 KB Output is correct
3 Correct 344 ms 45816 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 518 ms 49656 KB Output is correct
2 Correct 488 ms 53880 KB Output is correct
3 Correct 175 ms 42872 KB Output is correct