oj.uz

Submission #880838

# Submission time Handle Problem Language Result Execution time Memory
880838 2023-11-30T06:46:48 Z serifefedartar Usmjeri (COCI17_usmjeri) C++17
140 / 140
 360 ms 80980 KB 
#include <bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll LOGN = 21;
const ll MAXN = 3e5 + 10000;

vector<vector<int>> graph;
vector<vector<pair<int,int>>> G;
int up[LOGN][MAXN], par[MAXN], sz[MAXN], depth[MAXN], p[MAXN];
int find(int node) {
	if (node == par[node])
		return node;
	return par[node] = find(par[node]);
}

void unite(int a, int b) {
	a = find(a);
	b = find(b);
	if (sz[b] > sz[a]) 
		swap(a, b);
	sz[a] += sz[b];
	par[b] = a;
	int pa = p[a];
	int pb = p[b];
	if (depth[pa] > depth[pb])
		p[a] = pb;
	else
		p[a] = pa;
}

void dfs(int node, int parent) {
	for (auto u : graph[node]) {
		if (u == parent)
			continue;
		depth[u] = depth[node] + 1;
		up[0][u] = node;
		for (int i = 1; i < LOGN; i++)
			up[i][u] = up[i-1][up[i-1][u]];
		dfs(u, node);
	}
}

int lift(int node, int k) {
	for (int i = 0; i < LOGN; i++) {
		if ((1<<i) & k)
			node = up[i][node];
	}
	return node;
}

int lca(int a, int b) {
	if (depth[b] > depth[a])
		swap(a, b);
	a = lift(a, depth[a] - depth[b]);
	if (a == b)
		return a;

	for (int i = LOGN - 1; i >= 0; i--) {
		if (up[i][a] != up[i][b]) {
			a = up[i][a];
			b = up[i][b];
		}
	}
	return up[0][a];
}

void merge(int a, int b) {
	a = find(a);
	int lst = up[0][p[a]];
	while (depth[lst] > depth[b]) {
		a = find(a); 
		G[p[a]].push_back({lst, 0});
		G[lst].push_back({p[a], 0});
		unite(lst, a);
		lst = up[0][p[find(lst)]];
	}
}

int c[MAXN], vis[MAXN];
bool q; 
void check(int node, int parent, int color) {
	if (vis[node])
		return ;
	vis[node] = true; 

	c[node] = color;
	for (auto u : G[node]) {
		if (u.f == parent)
			continue;
		int need = c[node] ^ u.s;
		if (c[u.f] != -1 && c[u.f] != need)
			q = false;
		else
			check(u.f, node, need);
	}
}

int main() {
	fast
	memset(c, -1, sizeof(c));
	int N, M, a, b;
	cin >> N >> M;

	graph = vector<vector<int>>(N+1, vector<int>());
	G = vector<vector<pair<int,int>>>(N+1, vector<pair<int,int>>());
	for (int i = 1; i < N; i++) {
		cin >> a >> b;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}
	for (int i = 0; i < LOGN; i++)
		up[i][1] = 1;
	dfs(1, 1);
	depth[0] = 1e8;

	for (int i = 1; i <= N; i++)
		sz[i] = 1, par[i] = p[i] = i;
	for (int i = 0; i < M; i++) {
		cin >> a >> b;
		int LCA = lca(a, b);
		merge(a, LCA);
		merge(b, LCA);

		if (a != LCA && b != LCA) {
			G[a].push_back({b, 1});
			G[b].push_back({a, 1});
		}
	}

	ll ans = 1;
	for (int i = 2; i <= N; i++) {
		if (!vis[i]) {
			q = true;
			check(i, i, 0);
			if (q)
				ans = (ans * 2) % MOD;
			else
				ans = 0;
		}
	}
	cout << ans << "\n";
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 48468 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 80980 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 31324 KB Output is correct
2 Correct 4 ms 31480 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 31324 KB Output is correct
2 Correct 4 ms 31456 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 31580 KB Output is correct
2 Correct 6 ms 31580 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 31580 KB Output is correct
2 Correct 6 ms 31580 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 60256 KB Output is correct
2 Correct 269 ms 69716 KB Output is correct
3 Correct 140 ms 55332 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 64116 KB Output is correct
2 Correct 360 ms 71508 KB Output is correct
3 Correct 184 ms 59448 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 64528 KB Output is correct
2 Correct 253 ms 68556 KB Output is correct
3 Correct 186 ms 59216 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 64832 KB Output is correct
2 Correct 245 ms 73168 KB Output is correct
3 Correct 168 ms 55892 KB Output is correct