Submission #498535

#	Time	Username	Problem	Language	Result	Execution time	Memory
498535		s_samchenko	Valley (BOI19_valley)	C++17	59 / 100	310 ms	64448 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 ll inf = 1e15;
const ll 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 sol12(){
	while (q--){
		int ir, v, x, y;
		cin >> ir >> v;
		x = edges[ir].ff.ff, y = edges[ir].ff.ss;
		
		vector <int> u(n+10); u[v] = 1;
		queue <int> q; q.push(v);
		for (int i = 1; i <= n; ++i) d[i] = inf;
		d[v] = 0;
		while (!q.empty()){
			v = q.front(); q.pop();
			for (auto [to, len] : g[v]){
				if (v == x && to == y || v == y && to == x) continue;
				if (u[to]) continue;
				u[to] = 1;
				d[to] = d[v] + len;
				q.push(to);
			}
		}
		
		if (d[r] != inf){
			cout << "escaped\n";
			continue;
		}
		int best = inf;
		for (int i = 1; i <= n; ++i)
			if (c[i]) best = min(best, d[i]);
		if (best == inf) cout << "oo\n";
		else cout << best << '\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;
	}
	
	if (n*q <= 1e6){
		sol12();
		return;
	}
}

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

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

Compilation message (stderr)

valley.cpp: In function 'void sol12()':
valley.cpp:86:16: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   86 |     if (v == x && to == y || v == y && to == x) continue;
      |         ~~~~~~~^~~~~~~~~~

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