oj.uz

Submission #497062

# Submission time Handle Problem Language Result Execution time Memory
497062 2021-12-22T09:20:04 Z deinfreund Valley (BOI19_valley) C++17
100 / 100
 419 ms 81208 KB 
#include <bits/stdc++.h>
#define int int64_t
using namespace std;
 
vector<vector<pair<int, int>>>graph;
vector<vector<int>>up, val;
vector<int>tin, tout, dist, lvl, shh, shop;
 
int timer = 0;
int l = 32;
 
int min(int a, int b){
	if(a < b) return a;
	return b;
}
 
void dfs(int v, int p){
	tin[v] = timer++;
	up[v][0] = p;
 
	if(shop[v]) shh[v] = 0;
	
	for(int i = 1; i<=l; ++i){
		up[v][i] = up[up[v][i-1]][i-1];
	}
	
	for(auto [u, w]: graph[v]){
		if(u != p){
			lvl[u] = lvl[v] + 1;
			dist[u] = dist[v] + w;
			dfs(u, v);
			shh[v] = min(shh[u] + dist[u]-dist[v], shh[v]);
			assert(dist[u] - dist[v] >= 0);
		} 			
	}
	
	tout[v] = timer++;
}
 
void table(int v, int p){
	val[v][0] = dist[v] - dist[p] + shh[p];
	
	for(int i = 1; i<=l; ++i){
		val[v][i] = min(val[v][i-1], val[up[v][i-1]][i-1] + dist[v] - dist[up[v][i-1]]);
		assert(dist[v] - dist[up[v][i-1]] >= 0);
	}
	
	for(auto [u, w]: graph[v]) if(u != p) table(u, v);
	
}
 
int check(int u, int v){
	if(tin[u] <= tin[v] && tout[u] >= tout[v]) return 1;
	return 0;
}
 
int lca(int u, int v){
	if(check(u, v)) return u;
	if(check(v, u)) return v;
	
	for(int i = l; i>=0; --i){
		if(!check(up[u][i], v)) u = up[u][i];
	}
	
	return up[u][0];
}
 
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n, s, q, e; cin>>n>>s>>q>>e;
	--e;
	
	vector<pair<int, int>>edges;
	
	graph.assign(n, vector<pair<int, int>>());
	up.assign(n, vector<int>(33));
	val.assign(n, vector<int>(33));
	tin.assign(n, 0);
	tout.assign(n, 0);
	dist.assign(n, 0);
	lvl.assign(n, 0);
	shh.assign(n, 1e18);
	shop.assign(n, 0);
	
	for(int i = 0; i<n-1; ++i){
		int a, b, c; cin>>a>>b>>c;
		--a; --b;
		graph[a].push_back({b, c});
		graph[b].push_back({a, c});
		edges.push_back({a, b});
	}
	
	for(int i = 0; i<s; ++i){
		int c; cin>>c;
		--c;
		shop[c] = 1;
	}
	
	dfs(e, e);
	
	//for(auto u: shh) cout<<u<<" ";
	//cout<<endl;
	
	
	table(e, e);
	/*
	for(int i = 0; i<n; ++i){
		for(int j = 0; j<3; ++j) cout<<val[i][j]<<" ";
		cout<<endl;
	}
	cout<<endl;
	*/
	/*
	for(auto [x, y]: edges) cout<<x<<" "<<y<<endl;
	cout<<endl;
	*/
	
	for(int i = 0; i<q; ++i){
		int j, r; cin>>j>>r;
		--j; --r;
		int a = edges[j].first;
		int b = edges[j].second;
		int cur;
		
		if(lvl[a] > lvl[b]) cur = a;
		else cur = b;
		
		//cout<<cur<<" "<<r<<" "<<j<<endl;
		
		if(lca(cur, r) != cur) cout<<"escaped"<<'\n';
		else{
			
			int one = shh[r];
			int range = lvl[r] - lvl[cur];
			int jump = r;
			int two = 1e18;
			
			for(int i = l; i>=0; --i){
				if(range >= 1ll<<i){
					range -= 1ll<<i;
					two = min(two, val[jump][i] + dist[r] - dist[jump]);
					assert(dist[r] >= dist[jump]); 
					jump = up[jump][i];
					
					//cout<<jump<<" "<<two<<endl;
 
				}
			}
			
			if(min(one, two) < 1e18) cout<<min(one, two)<<'\n';
			else cout<<"oo"<<'\n';			
		}
	}
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 460 KB Output is correct
2 Correct 3 ms 452 KB Output is correct
3 Correct 4 ms 472 KB Output is correct
4 Correct 3 ms 452 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 460 KB Output is correct
2 Correct 3 ms 452 KB Output is correct
3 Correct 4 ms 472 KB Output is correct
4 Correct 3 ms 452 KB Output is correct
5 Correct 2 ms 972 KB Output is correct
6 Correct 2 ms 972 KB Output is correct
7 Correct 2 ms 972 KB Output is correct
8 Correct 2 ms 972 KB Output is correct
9 Correct 3 ms 972 KB Output is correct
10 Correct 2 ms 972 KB Output is correct
11 Correct 2 ms 972 KB Output is correct
12 Correct 2 ms 972 KB Output is correct
13 Correct 2 ms 1092 KB Output is correct
14 Correct 2 ms 972 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 73424 KB Output is correct
2 Correct 267 ms 72832 KB Output is correct
3 Correct 288 ms 73100 KB Output is correct
4 Correct 349 ms 74996 KB Output is correct
5 Correct 341 ms 75208 KB Output is correct
6 Correct 419 ms 77364 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 460 KB Output is correct
2 Correct 3 ms 452 KB Output is correct
3 Correct 4 ms 472 KB Output is correct
4 Correct 3 ms 452 KB Output is correct
5 Correct 2 ms 972 KB Output is correct
6 Correct 2 ms 972 KB Output is correct
7 Correct 2 ms 972 KB Output is correct
8 Correct 2 ms 972 KB Output is correct
9 Correct 3 ms 972 KB Output is correct
10 Correct 2 ms 972 KB Output is correct
11 Correct 2 ms 972 KB Output is correct
12 Correct 2 ms 972 KB Output is correct
13 Correct 2 ms 1092 KB Output is correct
14 Correct 2 ms 972 KB Output is correct
15 Correct 227 ms 73424 KB Output is correct
16 Correct 267 ms 72832 KB Output is correct
17 Correct 288 ms 73100 KB Output is correct
18 Correct 349 ms 74996 KB Output is correct
19 Correct 341 ms 75208 KB Output is correct
20 Correct 419 ms 77364 KB Output is correct
21 Correct 227 ms 75872 KB Output is correct
22 Correct 254 ms 75704 KB Output is correct
23 Correct 284 ms 76000 KB Output is correct
24 Correct 351 ms 78132 KB Output is correct
25 Correct 394 ms 81208 KB Output is correct
26 Correct 226 ms 75924 KB Output is correct
27 Correct 252 ms 75704 KB Output is correct
28 Correct 272 ms 76036 KB Output is correct
29 Correct 349 ms 77492 KB Output is correct
30 Correct 404 ms 79080 KB Output is correct
31 Correct 224 ms 75956 KB Output is correct
32 Correct 253 ms 75812 KB Output is correct
33 Correct 282 ms 76152 KB Output is correct
34 Correct 357 ms 77976 KB Output is correct
35 Correct 399 ms 80908 KB Output is correct
36 Correct 330 ms 78008 KB Output is correct