Submission #1229850

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229850		Amaarsaa	Usmjeri (COCI17_usmjeri)	C++20	28 / 140	485 ms	111528 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 = 1e9 + 7;

ll P[LOG][N], high[N], high_par[N];
ll tin[N], tout[N], timer = 0, depth[N];
vector < ll > adj[N];
vector < ll > ver[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;

void dfs(ll node) {
	for ( ll nxt : ver[node]) {
		if (color[nxt] == 0) {
			color[nxt] = 3 - color[node];
			dfs(nxt);
			continue;
		}
		if ( color[nxt] + color[node] != 3) 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], high_par[i] = i;
	
	for (i = 1; i <= m; i ++) {
		cin >> x >> y;
		lca = LCA(x, y);
		if ( depth[lca] < high[x]) high_par[x]= lca;
		if ( depth[lca] < high[y]) high_par[y]= lca;
		high[x] = min(high[x], depth[lca]);
		high[y] = min(high[y], depth[lca]);	
		if ( lca == x || lca == y) continue;
		ver[x].push_back(y);
		ver[y].push_back(x);
	
	}
	
	for (i = 1; i <= n; i++) {
		if ( color[i] == 0) {
			color[i] = 1;
			dfs(i);
		}
	}
	
	if ( can == 0) {
		cout << 0 << endl;
		return 0;
	}
	vector < pair < ll, ll > > v;
	for (i = 1; i <= n; i++) {
		v.push_back(make_pair(depth[i], i));
//		cout << high[i] << " ";
	}
//	cout <<endl;
	sort(v.rbegin(), v.rend());
	ans = 1;
	set < ll > S;
	for (i = 0; i < v.size(); i++) {
		x = v[i].second;
		if ( high[P[0][x]] > high[x]) {
			high_par[P[0][x]] = high_par[x];
		}
		high[P[0][x]] = min(high[P[0][x]], high[x]);
	}
	for (i = 2; i <= n; i++) {
		r = i;
		while ( r != high_par[r]) {
			r = high_par[r];
		}
		
		S.insert(r);
	}
	for (i = 1; i <= S.size(); i++) 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