Submission #498533

#	Time	Username	Problem	Language	Result	Execution time	Memory
498533		s_samchenko	Valley (BOI19_valley)	C++17	23 / 100	285 ms	68064 KiB

valley

#include <bits/stdc++.h>
#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
//#pragma GCC optimize("Ofast")
//#pragma GCC target ("avx2")
#define ll long long
#define ff first
#define ss second
#define int ll
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define pb push_back
#define pii pair <int, int>
#define pdd pair <double, double>
#define vi vector <int>
using namespace std;
using namespace __gnu_pbds;
template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
const int inf = 1e15;
const int mod = 1e9+7;
const int N = 2e5+100;

vector <int> p(N), d(N), ds(N);
vector < vector <pii> > g(N);
vector < vector <int> > up(N, vector <int> (20));
vector <pair <pii, int> > edges(N);
vector <int> c(N);
int n, s, q, r;

void dfs(int v, int pr, int l = 0, int h = 1){
	d[v] = h;
	ds[v] = l;
	up[v][0] = pr;
	for (int j = 1; j < 20; ++j) up[v][j] = up[up[v][j-1]][j-1];
	
	for (auto i : g[v]){
		int to = i.ff, len = i.ss;
		if (to == pr) continue;
		dfs(to, v, l + len, h+1);
	}
}

int lca(int u, int v){
	if (d[u] > d[v]) swap(u, v);
	for (int j = 19, H = d[v] - d[u]; H && j >= 0; --j){
		if (H < (1 << j)) continue;
		H -= (1 << j);
		v = up[v][j];
	}
	if (u == v) return u;
	for (int j = 19; j >= 0; --j){
		int u1 = up[u][j], v1 = up[v][j];
		if (u1 != v1){
			u = u1; v = v1;
		}
	}
	return up[u][0];
}

void sol3(){
	while (q--){
		int ir, v, x, y;
		cin >> ir >> v;
		x = edges[ir].ff.ff, y = edges[ir].ff.ss;
		
		int w1 = lca(v, x), w2 = lca(v, y);
		if (w1 == x && w2 == y) cout << "0\n";
		else cout << "escaped\n";
	}
}

void solve(){
	cin >> n >> s >> q >> r;
	for (int i = 1; i < n; ++i){
		int a, b, w; cin >> a >> b >> w;
		g[a].pb({b, w});
		g[b].pb({a, w});
		edges[i] = {{a, b}, w};
	}
	for (int i = 0; i < s; ++i){
		int a; cin >> a; c[a] = 1;
	}
	
	dfs(r, r);
	
	if (s == n){
		sol3(); return;
	}
}

signed main(){
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int tt = 1;

	while (tt--){
		solve();
		cout << '\n';
	}
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 27
• Subtask 3: 23 / 23
• Subtask 4: 0 / 41