oj.uz

Submission #498567

# Submission time Handle Problem Language Result Execution time Memory
498567 2021-12-25T14:03:14 Z s_samchenko Valley (BOI19_valley) C++17
100 / 100
 420 ms 110964 KB 
#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), sz(N, inf);
vector < vector <pii> > g(N);
vector < vector <int> > up(N, vector <int> (20)), jmp = up;
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){
	p[v] = pr;
	d[v] = h;
	ds[v] = l;
	up[v][0] = pr;
	if (c[v]) sz[v] = 0;
	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);
		sz[v] = min(sz[v], sz[to] + len);
	}
}

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 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);
	for (int i = 1; i <= n; ++i) jmp[i][0] = sz[i] - ds[i];
	for (int j = 1; j < 20; ++j)
		for (int i = 1; i <= n; ++i) jmp[i][j] = min(jmp[i][j-1], jmp[up[i][j-1]][j-1]);
	
	while (q--){
		int ir, v; cin >> ir >> v;
		int x = edges[ir].ff.ff, y = edges[ir].ff.ss;
		if (!(lca(v, x) == x && lca(v, y) == y)){
			cout << "escaped\n";
			continue;
		}
		if (d[x] > d[y]) swap(x, y);
		if (sz[y] == inf){
			cout << "oo\n";
			continue;
		}
		
		int ans = inf, dd = ds[v];
		for (int j = 19, H = d[v] - d[x]; j >= 0; --j){
			if ((1 << j) > H) continue;
			H -= (1 << j);
			ans = min(ans, jmp[v][j]);
			v = up[v][j];
		}
		ans = min(ans, jmp[y][0]);
		cout << ans + dd << '\n';
	}
}

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

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

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 95936 KB Output is correct
2 Correct 64 ms 95908 KB Output is correct
3 Correct 66 ms 95936 KB Output is correct
4 Correct 62 ms 95976 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 95936 KB Output is correct
2 Correct 64 ms 95908 KB Output is correct
3 Correct 66 ms 95936 KB Output is correct
4 Correct 62 ms 95976 KB Output is correct
5 Correct 69 ms 95872 KB Output is correct
6 Correct 59 ms 95932 KB Output is correct
7 Correct 59 ms 95964 KB Output is correct
8 Correct 57 ms 95936 KB Output is correct
9 Correct 59 ms 95940 KB Output is correct
10 Correct 61 ms 95952 KB Output is correct
11 Correct 63 ms 95916 KB Output is correct
12 Correct 61 ms 95876 KB Output is correct
13 Correct 59 ms 95948 KB Output is correct
14 Correct 60 ms 95924 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 101784 KB Output is correct
2 Correct 281 ms 101700 KB Output is correct
3 Correct 312 ms 101956 KB Output is correct
4 Correct 391 ms 104176 KB Output is correct
5 Correct 381 ms 104304 KB Output is correct
6 Correct 408 ms 106852 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 95936 KB Output is correct
2 Correct 64 ms 95908 KB Output is correct
3 Correct 66 ms 95936 KB Output is correct
4 Correct 62 ms 95976 KB Output is correct
5 Correct 69 ms 95872 KB Output is correct
6 Correct 59 ms 95932 KB Output is correct
7 Correct 59 ms 95964 KB Output is correct
8 Correct 57 ms 95936 KB Output is correct
9 Correct 59 ms 95940 KB Output is correct
10 Correct 61 ms 95952 KB Output is correct
11 Correct 63 ms 95916 KB Output is correct
12 Correct 61 ms 95876 KB Output is correct
13 Correct 59 ms 95948 KB Output is correct
14 Correct 60 ms 95924 KB Output is correct
15 Correct 273 ms 101784 KB Output is correct
16 Correct 281 ms 101700 KB Output is correct
17 Correct 312 ms 101956 KB Output is correct
18 Correct 391 ms 104176 KB Output is correct
19 Correct 381 ms 104304 KB Output is correct
20 Correct 408 ms 106852 KB Output is correct
21 Correct 249 ms 102940 KB Output is correct
22 Correct 252 ms 104740 KB Output is correct
23 Correct 283 ms 104964 KB Output is correct
24 Correct 337 ms 107560 KB Output is correct
25 Correct 398 ms 110964 KB Output is correct
26 Correct 245 ms 104952 KB Output is correct
27 Correct 274 ms 104772 KB Output is correct
28 Correct 284 ms 104948 KB Output is correct
29 Correct 377 ms 106808 KB Output is correct
30 Correct 396 ms 108724 KB Output is correct
31 Correct 247 ms 104940 KB Output is correct
32 Correct 268 ms 104824 KB Output is correct
33 Correct 279 ms 105156 KB Output is correct
34 Correct 359 ms 107372 KB Output is correct
35 Correct 420 ms 110808 KB Output is correct
36 Correct 347 ms 107400 KB Output is correct