Submission #1241428

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241428		altern23	Usmjeri (COCI17_usmjeri)	C++20	0 / 140	463 ms	327680 KiB

usmjeri

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pii pair<ll, ll>
#define fi first
#define sec second
#define ld long double

const int MAXN = 5e3;
const ll INF = 1e18;
const int MOD = 1e9 + 7;
const ld eps = 1e-6;

ll d[MAXN + 5];

struct DSU{
	ll N;
	vector<ll> par, sz;
	DSU(ll _n){
		N = _n;
		par.resize(N + 5), sz.resize(N + 5);
		for(int i = 1; i <= N; i++) par[i] = i, sz[i] = 1;
	}
	ll find(ll idx){
		return (par[idx] == idx ? idx : par[idx] = find(par[idx]));
	}
	void join(ll a, ll b){
		a = find(a), b = find(b);
		if(a == b) return;
		if(sz[a] < sz[b]) swap(a, b);
		par[b] = a;
		sz[a] += sz[b];
	}
};

vector<pii> adj[MAXN + 5];
pii up[MAXN + 5][MAXN + 5];
ll dist[MAXN + 5];

void init(ll idx, ll par){
	for(auto [i, j] : adj[idx]){
		if(i != par){
			dist[i] = dist[idx] + 1;
			init(i, idx);
		}
	}
}

void dfs(ll idx, ll par, ll head){
	for(auto [i, j] : adj[idx]){
		if(i != par){
			up[i][head] = {idx, j};
			dfs(i, idx, head);
		}
	}
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);		
	int tc = 1;	
	// cin >> tc;
	for(;tc--;){
		ll N, M; cin >> N >> M;
		for(int i = 1; i < N; i++){
			d[i] = -1;
			ll u, v; cin >> u >> v;
			adj[u].push_back({v, i}), adj[v].push_back({u, i});
		}
		DSU dsu(N);
		init(1, -1);
		
		for(int i = 1; i <= N; i++){
			dfs(i, -1, i);
		}
		
		bool ok = 1;
		for(int i = 1; i <= M; i++){
			ll a, b; cin >> a >> b;
			ll tmp = b;
			ll status = -1;
			while(tmp != a){
				if(d[up[tmp][a].sec] != -1){
					if(status != -1 && d[up[tmp][a].sec] != (status ^ (dist[tmp] < dist[up[tmp][a].fi]))){
						ok = 0;
						break;
					}
					status = ((dist[tmp] < dist[up[tmp][a].fi]) != (d[up[tmp][a].sec]));
				}
				tmp = up[tmp][a].fi;
			}
			
			if(status == -1) status = 0;
			tmp = b;
			ll last = -1;
			while(tmp != a){
				d[up[tmp][a].sec] = (status ^ (dist[tmp] < dist[up[tmp][a].fi]));
				if(last == -1) last = up[tmp][a].sec;
				else dsu.join(last, up[tmp][a].sec);
				tmp = up[tmp][a].fi;
			}
		}
		
		if(!ok){
			cout << 0 << "\n";
			continue;
		}
		
		ll ans = 1;
		for(int i = 1; i < N; i++){
			if(dsu.find(i) == i) ans = ans * 2LL % MOD;
		}
		cout << ans << "\n";
	}
}

/*

*/

• Subtask 1: 0 / 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