oj.uz

Submission #608771

# Submission time Handle Problem Language Result Execution time Memory
608771 2022-07-27T09:59:51 Z l_reho Valley (BOI19_valley) C++14
59 / 100
 462 ms 262148 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];	
}

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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 468 KB Output is correct
2 Correct 16 ms 468 KB Output is correct
3 Correct 17 ms 468 KB Output is correct
4 Correct 19 ms 340 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 468 KB Output is correct
2 Correct 16 ms 468 KB Output is correct
3 Correct 17 ms 468 KB Output is correct
4 Correct 19 ms 340 KB Output is correct
5 Correct 10 ms 8276 KB Output is correct
6 Correct 10 ms 8276 KB Output is correct
7 Correct 8 ms 8276 KB Output is correct
8 Correct 14 ms 8380 KB Output is correct
9 Correct 16 ms 8276 KB Output is correct
10 Correct 8 ms 8328 KB Output is correct
11 Correct 4 ms 340 KB Output is correct
12 Correct 3 ms 340 KB Output is correct
13 Correct 3 ms 468 KB Output is correct
14 Correct 41 ms 8276 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 414 ms 18960 KB Output is correct
2 Correct 408 ms 18876 KB Output is correct
3 Correct 400 ms 18944 KB Output is correct
4 Correct 443 ms 22472 KB Output is correct
5 Correct 462 ms 22492 KB Output is correct
6 Correct 372 ms 26336 KB Output is correct

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 468 KB Output is correct
2 Correct 16 ms 468 KB Output is correct
3 Correct 17 ms 468 KB Output is correct
4 Correct 19 ms 340 KB Output is correct
5 Correct 10 ms 8276 KB Output is correct
6 Correct 10 ms 8276 KB Output is correct
7 Correct 8 ms 8276 KB Output is correct
8 Correct 14 ms 8380 KB Output is correct
9 Correct 16 ms 8276 KB Output is correct
10 Correct 8 ms 8328 KB Output is correct
11 Correct 4 ms 340 KB Output is correct
12 Correct 3 ms 340 KB Output is correct
13 Correct 3 ms 468 KB Output is correct
14 Correct 41 ms 8276 KB Output is correct
15 Correct 414 ms 18960 KB Output is correct
16 Correct 408 ms 18876 KB Output is correct
17 Correct 400 ms 18944 KB Output is correct
18 Correct 443 ms 22472 KB Output is correct
19 Correct 462 ms 22492 KB Output is correct
20 Correct 372 ms 26336 KB Output is correct
21 Runtime error 102 ms 262148 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -