Submission #1225708

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225708		Amaarsaa	Usmjeri (COCI17_usmjeri)	C++20	14 / 140	115 ms	31400 KiB

usmjeri

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const ll N = 1e5 + 2;

ll mod =1e9 + 7;
vector < ll > adj[N];
ll P[20][N], tin[N], tout[N], timer;
ll chiglel[N], depth[N], deesh[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;
}

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);
	}
	
	
	for (i = 1; i <= n; i++) ataman[i] = i;
	
	Go(1, 1, 1);
	for (i = 1; i <= m; i ++) {
		cin >> x >> y;
		ll lca = LCA(x, y);
		init_x = x;
		init_y = y;
		x_iig = -1;
		while ( depth[x] > depth[lca]) {
			if ( chiglel[x] == 1){
				if ( x_iig == -1) x_iig = 1;
				else {
					if ( x_iig != 1) {
						cout << 0 << endl;
						return 0;
					}
				}
			}
			if ( chiglel[x] == 2){
				if ( x_iig == -1) x_iig = 0;
				else {
					if ( x_iig != 0) {
						cout << 0 << endl;
						return 0;
					}
				}
			}
			x = P[0][x];
		}
		
		while ( depth[y] > depth[lca]) {
			if ( chiglel[y] == 1){
				if ( x_iig == -1) x_iig = 0;
				else {
					if ( x_iig != 0) {
						cout << 0 << endl;
						return 0;
					}
				}
				y = deesh[y];
				continue;
			}
			if ( chiglel[y] == 2){
				if ( x_iig == -1) x_iig = 1;
				else {
					if ( x_iig != 1) {
						cout << 0 << endl;
						return 0;
					}
				}
				y = deesh[y];
				continue;
			}
			y = P[0][y];
		}
		if ( x_iig == -1) x_iig = 1;
		ll deeshee;
		if ( depth[x] >= depth[lca] && depth[x] >= depth[y]) deeshee = x;
		if ( depth[y] >= depth[lca] && depth[y] >= depth[x]) deeshee= y;
		if ( depth[lca] >= depth[x] && depth[lca] >= depth[y]) deeshee = lca;
		x = init_x;
		y = init_y;
		if ( x_iig == 1) {
			while ( depth[x] >  depth[lca]) {
				chiglel[x] = 1;
				Unite(x, P[0][x]);
				if ( deesh[x] == 0) {
					deesh[x] = deeshee;
					x = P[0][x];
				}
				else x = deesh[x];
			}
			while ( depth[y] > depth[lca]) {
				chiglel[y] = 2;
				Unite(y, P[0][y]);
				if ( deesh[y] == 0) {
					deesh[y] = deeshee;
					y = P[0][y];
				}
				else y = deesh[y];
			}
		}
		else {
			while ( depth[x] >  depth[lca]) {
				chiglel[x] = 2;
				Unite(x, P[0][x]);
				if ( deesh[x] == 0) {
					deesh[x] = deeshee;
					x = P[0][x];
				}
				else x = deesh[x];
			}
			while ( depth[y] > depth[lca]) {
				chiglel[y] = 1;
				Unite(y, P[0][y]);
				if ( deesh[y] == 0) {
					deesh[y] = deeshee;
					y = P[0][y];
				}
				else y = deesh[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: 0 / 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