Submission #608771

#	Time	Username	Problem	Language	Result	Execution time	Memory
608771		l_reho	Valley (BOI19_valley)	C++14	59 / 100	462 ms	262148 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<vector<ll>> dist;



int timer = 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;
void bfs(vector<int> starts){
	
	
	queue<pair<int, int>> q;
	
	for(int s : starts){
		q.push({s, s});		
		dist[s][s] = 0;
	}
	
	
	while(!q.empty()){
		cnt++;
		pair<int, int> curr = q.front();
		q.pop();
		int s = curr.first;
		int node = curr.second;
		
		vector<pair<int, ll>> adj = graph[node];
		
		for(pair<int, ll> a : adj){
			if(isShop[a.first]) continue;
			if(dist[s][a.first] != LLONG_MAX) continue;
			
			dist[s][a.first] = dist[s][node]+a.second;
			
			q.push({s, a.first});
		}
		
	}
	
	
	
}

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>());
	
	if(S != N)
		dist.assign(N+1, vector<ll>(N+1, LLONG_MAX));
	
	
	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);
	if(S != N)
		bfs(shops);
	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;
		}
		
		ll mn = LLONG_MAX;
		// devo sfruttare il precalcolo
		if(N == S){
			cout<<0<<endl;
			continue;
		}
		for(int s : shops){
			if(inst(d, s)) mn = min(mn, dist[s][b]);
		}
		
		if(mn == LLONG_MAX) cout<<"oo"<<endl;
		else cout<<mn<<endl;
	}
	
}
 
int main(){
	solve();
	return 0;
}

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