Submission #1229875

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229875		Amaarsaa	Usmjeri (COCI17_usmjeri)	C++20	140 / 140	564 ms	118704 KiB

usmjeri

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const ll N = 3e5 + 2;
const ll LOG = 18;
const ll mod = 1000000007;

ll P[LOG][N], high[N];
ll tin[N], tout[N], timer = 0, depth[N];
vector < ll > adj[N];
vector < ll > opo[N];
vector < ll > sam[N];

void Go(ll node, ll par) {
	P[0][node] = par;
	for (int i = 1; i < LOG; i ++) P[i][node] = P[i- 1][P[i - 1][node]];
	
	timer ++;
	tin[node] = timer; 
	for ( ll nxt : adj[node]) {
		if ( nxt == par) continue;
		depth[nxt] = depth[node] + 1;
		Go(nxt, node);
	}
	
	timer ++;
	tout[node] = timer;
}

bool is_ancestor(ll x, ll y) {
	if ( tin[x] <= tin[y] && tout[y] <= tout[x]) return true;
	return false;
}

ll LCA(ll x, ll y) {
	if ( is_ancestor(x, y)) return x;
	if ( is_ancestor(y, x)) return y;
	
	for ( int i = LOG - 1; i >= 0; i --) if (!is_ancestor(P[i][x], y)) x = P[i][x];
	
	return P[0][x];
}
ll color[N] = {0};
ll can = 1;
ll gunii(ll node,ll par) {
	for ( ll nxt : adj[node]) {
		if ( nxt ==par) continue;
		high[node] =min(high[node], gunii(nxt, node));
		if( depth[node] > high[nxt]) {
			sam[node].push_back(nxt);
			sam[nxt].push_back(node);
		}
	}
	return high[node];
}
void dfs(ll node) {
	for ( ll nxt : opo[node]) {
		if (color[nxt] == 0) {
			color[nxt] = 3 - color[node];
			dfs(nxt);
			continue;
		}
		if ( color[nxt] + color[node] != 3) can = 0;
	}
	for ( ll nxt : sam[node]) {
		if (color[nxt] == 0) {
			color[nxt] = color[node];
			dfs(nxt);
			continue;
		}
		if ( color[nxt] != color[node] ) can = 0;
	}
}
int main() {
	ll n, m, r, lca, x, y, i, j, ans, t;

	cin >> n >> m;
	

	for (i = 1; i < n; i ++) {
		cin >> x >> y;
		adj[x].push_back(y);
		adj[y].push_back(x);
	}
	
	Go(1, 1);
	for (i = 1; i <= n; i ++) high[i] =depth[i];
	
	for (i = 1; i <= m; i ++) {
		cin >> x >> y;
		lca = LCA(x, y);
		high[x] = min(high[x], depth[lca]);
		high[y] = min(high[y], depth[lca]);	
		if ( lca == x || lca == y) continue;
		opo[x].push_back(y);
		opo[y].push_back(x);
	
	}
	gunii(1, 1);
	ans = 1;
	for (i = 2; i <= n; i++) {
		if ( color[i] == 0) {
			color[i] = 1;
			dfs(i);
			ans *= 2;
			ans %= mod;
		}
	}
	
	if ( can == 0) {
		cout << 0 << endl;
		return 0;
	}

	
	
	cout << ans << 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