oj.uz

Submission #608761

# Submission time Handle Problem Language Result Execution time Memory
608761 2022-07-27T09:55:53 Z l_reho Valley (BOI19_valley) C++14
36 / 100
 96 ms 262144 KB 
#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];	
}


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()){
		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>());
	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);
	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
		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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 468 KB Output is correct
2 Correct 16 ms 488 KB Output is correct
3 Correct 16 ms 492 KB Output is correct
4 Correct 18 ms 468 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 468 KB Output is correct
2 Correct 16 ms 488 KB Output is correct
3 Correct 16 ms 492 KB Output is correct
4 Correct 18 ms 468 KB Output is correct
5 Correct 7 ms 8276 KB Output is correct
6 Correct 7 ms 8360 KB Output is correct
7 Correct 7 ms 8276 KB Output is correct
8 Correct 10 ms 8404 KB Output is correct
9 Correct 16 ms 8396 KB Output is correct
10 Correct 11 ms 8248 KB Output is correct
11 Correct 12 ms 8376 KB Output is correct
12 Correct 8 ms 8276 KB Output is correct
13 Correct 8 ms 8388 KB Output is correct
14 Correct 39 ms 8372 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 96 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 468 KB Output is correct
2 Correct 16 ms 488 KB Output is correct
3 Correct 16 ms 492 KB Output is correct
4 Correct 18 ms 468 KB Output is correct
5 Correct 7 ms 8276 KB Output is correct
6 Correct 7 ms 8360 KB Output is correct
7 Correct 7 ms 8276 KB Output is correct
8 Correct 10 ms 8404 KB Output is correct
9 Correct 16 ms 8396 KB Output is correct
10 Correct 11 ms 8248 KB Output is correct
11 Correct 12 ms 8376 KB Output is correct
12 Correct 8 ms 8276 KB Output is correct
13 Correct 8 ms 8388 KB Output is correct
14 Correct 39 ms 8372 KB Output is correct
15 Runtime error 96 ms 262144 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -