oj.uz

Submission #610592

# Submission time Handle Problem Language Result Execution time Memory
610592 2022-07-28T11:04:57 Z l_reho Valley (BOI19_valley) C++14
100 / 100
 782 ms 78908 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, 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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 340 KB Output is correct
2 Correct 17 ms 452 KB Output is correct
3 Correct 20 ms 380 KB Output is correct
4 Correct 17 ms 440 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 17 ms 452 KB Output is correct
3 Correct 20 ms 380 KB Output is correct
4 Correct 17 ms 440 KB Output is correct
5 Correct 4 ms 980 KB Output is correct
6 Correct 4 ms 980 KB Output is correct
7 Correct 4 ms 980 KB Output is correct
8 Correct 4 ms 980 KB Output is correct
9 Correct 6 ms 980 KB Output is correct
10 Correct 4 ms 928 KB Output is correct
11 Correct 4 ms 980 KB Output is correct
12 Correct 4 ms 980 KB Output is correct
13 Correct 4 ms 980 KB Output is correct
14 Correct 4 ms 980 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 522 ms 69336 KB Output is correct
2 Correct 475 ms 69016 KB Output is correct
3 Correct 515 ms 69360 KB Output is correct
4 Correct 533 ms 73052 KB Output is correct
5 Correct 620 ms 72988 KB Output is correct
6 Correct 772 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 17 ms 452 KB Output is correct
3 Correct 20 ms 380 KB Output is correct
4 Correct 17 ms 440 KB Output is correct
5 Correct 4 ms 980 KB Output is correct
6 Correct 4 ms 980 KB Output is correct
7 Correct 4 ms 980 KB Output is correct
8 Correct 4 ms 980 KB Output is correct
9 Correct 6 ms 980 KB Output is correct
10 Correct 4 ms 928 KB Output is correct
11 Correct 4 ms 980 KB Output is correct
12 Correct 4 ms 980 KB Output is correct
13 Correct 4 ms 980 KB Output is correct
14 Correct 4 ms 980 KB Output is correct
15 Correct 522 ms 69336 KB Output is correct
16 Correct 475 ms 69016 KB Output is correct
17 Correct 515 ms 69360 KB Output is correct
18 Correct 533 ms 73052 KB Output is correct
19 Correct 620 ms 72988 KB Output is correct
20 Correct 772 ms 77456 KB Output is correct
21 Correct 603 ms 68764 KB Output is correct
22 Correct 530 ms 68760 KB Output is correct
23 Correct 643 ms 68908 KB Output is correct
24 Correct 782 ms 73544 KB Output is correct
25 Correct 743 ms 78908 KB Output is correct
26 Correct 509 ms 68936 KB Output is correct
27 Correct 540 ms 68888 KB Output is correct
28 Correct 531 ms 68988 KB Output is correct
29 Correct 606 ms 71892 KB Output is correct
30 Correct 642 ms 74956 KB Output is correct
31 Correct 510 ms 68940 KB Output is correct
32 Correct 547 ms 68760 KB Output is correct
33 Correct 480 ms 69164 KB Output is correct
34 Correct 533 ms 73200 KB Output is correct
35 Correct 572 ms 78712 KB Output is correct
36 Correct 565 ms 73636 KB Output is correct