oj.uz

Submission #496646

# Submission time Handle Problem Language Result Execution time Memory
496646 2021-12-21T18:11:35 Z _Avocado_ Valley (BOI19_valley) C++14
23 / 100
 445 ms 76664 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 = 30;

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]);
		} 			
	}
	
	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]]);
	}
	
	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>(31));
	val.assign(n, vector<int>(31));
	tin.assign(n, 0);
	tout.assign(n, 0);
	dist.assign(n, 0);
	lvl.assign(n, 0);
	shh.assign(n, 1e10);
	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 = 1e10;
			int tt = 0;
			
			for(int i = 30; i>=0; --i){
				if(range >= 1ll<<i){
					range -= 1ll<<i;
					if(val[jump][i] != 1e10){
						tt += val[jump][i]; 
						two = tt;
					}
					jump = up[jump][i];
					
					//cout<<jump<<" "<<two<<endl;

				}
			}
			
			if(min(one, two) < 1e10) cout<<min(one, two)<<'\n';
			else cout<<"oo"<<'\n';
			
			
		}
	}
	

	
	
	
	cout<<'\n';
}

Compilation message

valley.cpp: In function 'void dfs(int64_t, int64_t)':
valley.cpp:27:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   27 |  for(auto [u, w]: graph[v]){
      |           ^
valley.cpp: In function 'void table(int64_t, int64_t)':
valley.cpp:46:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   46 |  for(auto [u, w]: graph[v]) if(u != p) table(u, v);
      |           ^

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 452 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 452 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 73312 KB Output is correct
2 Correct 275 ms 73208 KB Output is correct
3 Correct 280 ms 73396 KB Output is correct
4 Correct 356 ms 74920 KB Output is correct
5 Correct 338 ms 75040 KB Output is correct
6 Correct 445 ms 76664 KB Output is correct

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 452 KB Output isn't correct
2 Halted 0 ms 0 KB -