Submission #1225726

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225726		Amaarsaa	Usmjeri (COCI17_usmjeri)	C++20	28 / 140	480 ms	118748 KiB

usmjeri

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const ll N = 5e5 + 2;

ll mod =1e9 + 7;
vector < ll > adj[N];
vector < ll > jda[N];
ll P[20][N], tin[N], tout[N], timer, etseg[N];
ll chiglel[N], depth[N], deesh[N] = {0}, high[N] = {0};

void Go(ll node, ll par, ll de) {
	timer ++;
	depth[node] = de;
	tin[node] = timer;
	P[0][node] = par;
	for ( int i = 1; i <= 17; i ++) P[i][node] = P[i - 1][P[i - 1][node]];
	
	for (ll X : adj[node]) {
		if ( X == par) continue;
		Go(X, node, de + 1);
	}
	tout[node] = timer;
}
ll used[N] = {0}, can = 1;
void DFS(ll node) {
	for ( ll X : adj[node]) {
		if ( used[X] == 0) {
			used[X] = 3 - used[node];
			DFS(node);
			continue;
		}
		if ((used[X] + used[node]) != 3) can = 0;
		
	}
}

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 = 17; i >= 0; i --) {
		if (!is_ancestor(P[i][x], y)) x= P[i][x];
	}
	return P[0][x];
}

ll ataman[N];

ll Get(ll x) {
	if ( x == ataman[x]) return x;
	return ataman[x]= Get(ataman[x]);
}

void Unite(ll x, ll y) {
	x = Get(x);
	y = Get(y);
	if ( x == y) return ;
	if ( x > y) swap(x, y);
	ataman[x] = y;
}
ll Pow(ll x, ll y) {
	if ( y == 0) return 1;
	if ( y == 1) return x % mod;
	ll r = Pow(x, y/2);
	r = r * r% mod;
	if (y % 2 == 1) r = r * x % mod;
	return r;
}
int main() {
	ll n, m, r, x,init_x, init_y, x_iig, 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, 1);
	for (i = 1; i <= n; i ++) high[i] = depth[i],etseg[i] = i,  ataman[i] = i;
	for (i = 1; i <= m; i ++) {
		cin >> x >> y;
		ll lca = LCA(x, y);
		if ( depth[lca] < high[x]) etseg[x] = lca;
		if ( depth[lca] < high[y]) etseg[y] = lca;
		high[x] = min(high[x], depth[lca]);
		high[y] = min(high[y], depth[lca]);
		if ( lca == x || lca == y) continue;
		jda[x].push_back(y);
		jda[y].push_back(x);
	}
	
	ans = 1;
	
	for (i = 1; i <= n; i ++) {
		if ( used[i] == 0) {
			used[i] = 1;
			DFS(i);
		}
	}
	
	if ( can == 0) {
		cout << 0 << endl;
		return 0;
	}
	
	for (i = 1; i <= n; i ++) {
		x =i;
		r = etseg[i];
		while ( Get(i) != Get(r) ) {
			y = P[0][x];
			Unite(x, y);
			x = y;
		}
	}
	map < int, int > mp;
	
	for ( i = 1; i <= n; i ++) {
		mp[Get(i)] ++;
	}
	ans = Pow(2, mp.size() - 1);
	for ( auto R : mp) {
		if ( R.second >= 2) ans = ans * 2 % mod;
	}
	cout << ans << endl;
	
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14