oj.uz

Submission #644392

# Submission time Handle Problem Language Result Execution time Memory
644392 2022-09-24T14:56:56 Z amoorj Valley (BOI19_valley) C++17
100 / 100
 336 ms 51236 KB 
#pragma GCC optimize ("O3,unroll-loops,Ofast")
//#pragma GCC target ("avx2,bmi,bmi2,popcnt")
#include <bits/stdc++.h>
#define F first
#define pb push_back
#define sz size()
#define S second
using namespace std;
typedef long long int ll;

const int N = 1e5 + 10, LG = 20;
const ll INF = 1e18;
int n,s,q,e,lg2[N],st[N],ft[N],timer = 0;
ll dp[N],h[N],hi[N],val[N],mini[N][LG],up[N][LG];
vector<pair<int,int>> adj[N],edg;
vector<ll> vec;
bool shop[N];

void dfs(int v,int p){
	st[v] = ++timer;
	up[v][0] = p;
	for(int j=1;j<LG;j++)
		up[v][j] = up[up[v][j-1]][j-1];
	if(shop[v])
		dp[v] = 0;
	for(auto x:adj[v]){
		int u = x.F, w = x.S;
		if(u == p)
			continue;
		h[u] = h[v] + w;
		hi[u] = hi[v] + 1;
		dfs(u,v);
		dp[v] = min(dp[v], dp[u] + w);
	}
	ft[v] = ++timer;
}
void dfs2(int v,int p){
	mini[v][0] = min(val[v], val[p]);
	for(int j=1;j<LG;j++)
		mini[v][j] = min(mini[v][j-1], mini[up[v][j-1]][j-1]);
	for(auto x:adj[v]){
		int u = x.F;
		if(u == p)
			continue;
		dfs2(u,v);
	}
}
bool is_anc(int anc,int v){
	return (st[anc] <= st[v] && ft[anc] >= ft[v]);
}
ll minx(int v,int x){
	ll ans = val[v];
	for(int j=LG-1;j>-1;j--){
		if(x >= (1 << j)){
			ans = min(ans, mini[v][j]);
			v = up[v][j];
			x -= (1 << j);
		}
	}
	return ans;
}
inline void init(){
	for(int i=0;i<N;i++){
		dp[i] = INF;
	}
	lg2[1] = 0;
	for(int i=2;i<N;i++)
		lg2[i] = lg2[i/2] + 1;
}
inline void input(){
	cin >> n >> s >> q >> e;
	e--;
	int x,y,w;
	for(int i=0;i<n-1;i++){
		cin >> x >> y >> w;
		x--, y--;
		adj[x].pb({y,w}), adj[y].pb({x,w});
		edg.pb({x,y});
	}
	for(int i=0;i<s;i++){
		cin >> x;
		shop[--x] = 1;
	}
}
inline void solve(){
	int x,y;
	hi[e] = 0, h[e] = 0;
	dfs(e,e);
	for(int i=0;i<n;i++){
		val[i] = dp[i] - h[i];
//		cout << dp[i] << ' ' << h[i] << ' ' << i << endl;
	}
	dfs2(e,e);
/*	for(int i=0;i<n;i++){
		for(int j=0;j<LG;j++){
			if(mini[i][j] > 1e17)
				cout << "INF ";
			else
				cout << mini[i][j] << ' ';
		}
		cout << endl;
	}*/
	while(q--){
		cin >> x >> y; // edge , vertex
		x--, y--;
		int v = edg[x].F, u = edg[x].S;
		if(h[v] < h[u])
			swap(v,u);
		if(!is_anc(v,y)){
			cout << "escaped" << endl;
		}
		else{
			ll ans = minx(y,hi[y]-hi[v]);
//			cout << ans << ' ';
			ans += h[y];
			if(ans > 1e16)
				cout << "oo" << endl;
			else
				cout << ans << endl;
		}
	}
}
int main(){
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
	init();
	int queries = 1;
//	cin >> queries;
	while(queries--){
		input();
		solve();
	}
	return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 4008 KB Output is correct
2 Correct 16 ms 4052 KB Output is correct
3 Correct 16 ms 4052 KB Output is correct
4 Correct 16 ms 4000 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 4008 KB Output is correct
2 Correct 16 ms 4052 KB Output is correct
3 Correct 16 ms 4052 KB Output is correct
4 Correct 16 ms 4000 KB Output is correct
5 Correct 4 ms 4308 KB Output is correct
6 Correct 4 ms 4264 KB Output is correct
7 Correct 5 ms 4308 KB Output is correct
8 Correct 4 ms 4308 KB Output is correct
9 Correct 4 ms 4308 KB Output is correct
10 Correct 4 ms 4332 KB Output is correct
11 Correct 4 ms 4260 KB Output is correct
12 Correct 5 ms 4308 KB Output is correct
13 Correct 5 ms 4260 KB Output is correct
14 Correct 5 ms 4308 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 44860 KB Output is correct
2 Correct 274 ms 44508 KB Output is correct
3 Correct 279 ms 44564 KB Output is correct
4 Correct 312 ms 46612 KB Output is correct
5 Correct 296 ms 46772 KB Output is correct
6 Correct 321 ms 48972 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 4008 KB Output is correct
2 Correct 16 ms 4052 KB Output is correct
3 Correct 16 ms 4052 KB Output is correct
4 Correct 16 ms 4000 KB Output is correct
5 Correct 4 ms 4308 KB Output is correct
6 Correct 4 ms 4264 KB Output is correct
7 Correct 5 ms 4308 KB Output is correct
8 Correct 4 ms 4308 KB Output is correct
9 Correct 4 ms 4308 KB Output is correct
10 Correct 4 ms 4332 KB Output is correct
11 Correct 4 ms 4260 KB Output is correct
12 Correct 5 ms 4308 KB Output is correct
13 Correct 5 ms 4260 KB Output is correct
14 Correct 5 ms 4308 KB Output is correct
15 Correct 267 ms 44860 KB Output is correct
16 Correct 274 ms 44508 KB Output is correct
17 Correct 279 ms 44564 KB Output is correct
18 Correct 312 ms 46612 KB Output is correct
19 Correct 296 ms 46772 KB Output is correct
20 Correct 321 ms 48972 KB Output is correct
21 Correct 283 ms 45836 KB Output is correct
22 Correct 287 ms 45548 KB Output is correct
23 Correct 272 ms 45428 KB Output is correct
24 Correct 293 ms 47936 KB Output is correct
25 Correct 316 ms 51236 KB Output is correct
26 Correct 243 ms 45968 KB Output is correct
27 Correct 262 ms 45616 KB Output is correct
28 Correct 289 ms 45744 KB Output is correct
29 Correct 297 ms 47176 KB Output is correct
30 Correct 336 ms 48996 KB Output is correct
31 Correct 276 ms 45884 KB Output is correct
32 Correct 273 ms 45780 KB Output is correct
33 Correct 270 ms 45648 KB Output is correct
34 Correct 305 ms 47808 KB Output is correct
35 Correct 326 ms 51128 KB Output is correct
36 Correct 288 ms 48476 KB Output is correct