oj.uz

Submission #610587

# Submission time Handle Problem Language Result Execution time Memory
610587 2022-07-28T11:02:20 Z l_reho Valley (BOI19_valley) C++14
100 / 100
 639 ms 82000 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<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, dp[curr]};
	
	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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 340 KB Output is correct
2 Correct 23 ms 488 KB Output is correct
3 Correct 16 ms 492 KB Output is correct
4 Correct 22 ms 496 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 340 KB Output is correct
2 Correct 23 ms 488 KB Output is correct
3 Correct 16 ms 492 KB Output is correct
4 Correct 22 ms 496 KB Output is correct
5 Correct 4 ms 916 KB Output is correct
6 Correct 4 ms 1024 KB Output is correct
7 Correct 4 ms 980 KB Output is correct
8 Correct 4 ms 952 KB Output is correct
9 Correct 4 ms 936 KB Output is correct
10 Correct 5 ms 1040 KB Output is correct
11 Correct 4 ms 980 KB Output is correct
12 Correct 5 ms 980 KB Output is correct
13 Correct 7 ms 944 KB Output is correct
14 Correct 5 ms 980 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 549 ms 69292 KB Output is correct
2 Correct 492 ms 68904 KB Output is correct
3 Correct 535 ms 69192 KB Output is correct
4 Correct 519 ms 73092 KB Output is correct
5 Correct 524 ms 73036 KB Output is correct
6 Correct 639 ms 77456 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 340 KB Output is correct
2 Correct 23 ms 488 KB Output is correct
3 Correct 16 ms 492 KB Output is correct
4 Correct 22 ms 496 KB Output is correct
5 Correct 4 ms 916 KB Output is correct
6 Correct 4 ms 1024 KB Output is correct
7 Correct 4 ms 980 KB Output is correct
8 Correct 4 ms 952 KB Output is correct
9 Correct 4 ms 936 KB Output is correct
10 Correct 5 ms 1040 KB Output is correct
11 Correct 4 ms 980 KB Output is correct
12 Correct 5 ms 980 KB Output is correct
13 Correct 7 ms 944 KB Output is correct
14 Correct 5 ms 980 KB Output is correct
15 Correct 549 ms 69292 KB Output is correct
16 Correct 492 ms 68904 KB Output is correct
17 Correct 535 ms 69192 KB Output is correct
18 Correct 519 ms 73092 KB Output is correct
19 Correct 524 ms 73036 KB Output is correct
20 Correct 639 ms 77456 KB Output is correct
21 Correct 561 ms 72012 KB Output is correct
22 Correct 451 ms 71852 KB Output is correct
23 Correct 476 ms 72148 KB Output is correct
24 Correct 568 ms 76736 KB Output is correct
25 Correct 553 ms 82000 KB Output is correct
26 Correct 442 ms 72048 KB Output is correct
27 Correct 482 ms 71896 KB Output is correct
28 Correct 528 ms 72100 KB Output is correct
29 Correct 507 ms 75044 KB Output is correct
30 Correct 604 ms 78100 KB Output is correct
31 Correct 463 ms 72212 KB Output is correct
32 Correct 495 ms 71944 KB Output is correct
33 Correct 500 ms 72264 KB Output is correct
34 Correct 603 ms 76436 KB Output is correct
35 Correct 599 ms 81992 KB Output is correct
36 Correct 523 ms 76384 KB Output is correct