Submission #610592

#	Time	Username	Problem	Language	Result	Execution time	Memory
610592		l_reho	Valley (BOI19_valley)	C++14	100 / 100	782 ms	78908 KiB

valley

#include<bits/stdc++.h>
using namespace std;
 
#define ll long long
 
int N, S, Q, E;
vector<vector<pair<int, ll>>> graph;
vector<int> shops;
vector<pair<int, int>> edges;
vector<int> tin;
vector<int> tout;
map<int, bool> isShop;
vector<ll> dist;
vector<ll> dp;
vector<vector<pair<int, ll>>> up;
 
 
int timer = 0;
int l = 0;

void dfs(int curr, int p){
	
	tin[curr] = timer++;
	
	vector<pair<int, ll>> adj = graph[curr];
	
	for(pair<int, ll> a : adj){
		if(a.first == p) continue;
		
		dfs(a.first, curr);
	}
	
	tout[curr]=timer++;
	
}
 
bool inst(int a, int b){
	return tin[a] <= tin[b] && tout[a] >= tout[b];	
}
 
int cnt = 0;

// dist[E][R] + min(dist[E][V] - dist[E][W]*2)

// per ogni W posso precalcolare

void bfs(int root){
	
	queue<int> q;
	
	q.push(root);
	
	dist[root] = 0;
	
	while(!q.empty()){
		int node = q.front();
		
		q.pop();
		
		vector<pair<int, ll>> adj = graph[node];
		
		for(pair<int, ll> a : adj){
			if(dist[a.first] != LLONG_MAX) continue;
			
			dist[a.first] = dist[node] + a.second;
			q.push(a.first);
		}
	}
	
}

ll precompute(int curr, int parent){
	
	
	vector<pair<int, ll>> adj = graph[curr];

	
	if(isShop[curr])
		dp[curr] = dist[curr];
	
	for(pair<int, ll> p : adj){
		if(p.first == parent) continue;
		
		ll ret = precompute(p.first, curr);
		dp[curr] = min(dp[curr], ret);
		
	}
	
	return dp[curr];
}

void binaryLifting(int curr, int p){
	
	
	vector<pair<int, ll>> adj = graph[curr];
	
	up[curr][0] = {p, min(dp[curr], dp[p])};
	
	for(int i = 1; i <= l; i++){
		pair<int, ll> upper = up[up[curr][i-1].first][i-1];
		up[curr][i] = {upper.first, min(upper.second, up[curr][i-1].second)};
	}
	
	for(pair<int, ll> a : adj){
		if(a.first == p) continue;
		
		binaryLifting(a.first, curr);
	}
	
}

void solve(){
	cin>>N>>S>>Q>>E;
	
	graph.assign(N+1, vector<pair<int, ll>>());
	shops.assign(S, 0);
	tin.assign(N+1, 0);
	tout.assign(N+1, 0);
	edges.assign(N-1, pair<int, int>());
	
	dist.assign(N+1, LLONG_MAX);
	dp.assign(N+1, LLONG_MAX);
	up.assign(N+1, vector<pair<int, ll>>(31, {0, LLONG_MAX}));
	
	l = ceil(log2(N+1));
	
	for(int i = 0; i < N-1; i++){
		int a, b, c;
		cin>>a>>b>>c;
		
		edges[i] = {a, b};
		
		graph[a].push_back({b, c});
		graph[b].push_back({a, c});
		
	}
	
	for(int i = 0; i < S; i++){
		cin>>shops[i];
		isShop[shops[i]] = true;
	}
		
	dfs(E, -1);
	bfs(E);
	precompute(E, -1);
	
	for(int i = 1; i <= N; i++){
		if(dp[i] != LLONG_MAX)
			dp[i] = dp[i] - 2*dist[i];
	}
	
	binaryLifting(E, E);
	
	for(int q = 0; q < Q; q++){
		int a, b;
		cin>>a>>b;
		a--;
		// eliminiamo l'edge ad indice a
		pair<int, int> e = edges[a];
		
		// mi serve l'estremo più distante da E
		int e1 = e.first;
		int e2 = e.second;
		
		bool test1 = inst(e1, e2);
		
		int d = test1 ? e2 : e1;
		if(!inst(d, b)){
			cout<<"escaped"<<endl;
			continue;
		}
		
		// devo sfruttare il precalcolo
		if(N == S){
			cout<<0<<endl;
			continue;
		}
		
		// adesso si dovrebbe fare il binary lifting per individuare il miglior
		// w tale per cui dist[E][V] - dist[E][W]*2 è minima
		
		// come posso fare binary lifting 
		
		int u = b;
		ll ans = LLONG_MAX;
		for(int i = l; i >= 0; i--){
			if(inst(d, up[u][i].first)){
				ans = min(ans, up[u][i].second);
				u = up[u][i].first;
			}
		}
		
		
		ans = min(ans, dp[d]);
		if(ans == LLONG_MAX) cout<<"oo"<<endl;
		else cout<<ans+dist[b]<<endl;
	}
	
}
 
int main(){
	solve();
	return 0;
}

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