Submission #699838

#	Time	Username	Problem	Language	Result	Execution time	Memory
699838		Iliya_	Valley (BOI19_valley)	C++14	100 / 100	267 ms	55756 KiB

valley

// IN THE NAME OF GOD
#include<bits/stdc++.h>
//#pragma GCC optimize ("O2,unroll-loops,O3,Ofast,no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#define endl '\n'
#define file_reading freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
using namespace std;
typedef long long ll;
typedef long double dll;
typedef unsigned long long ull;

const ll B = 1e5+7, logg = 23, inf = 1e18; 
ll dist[B],sub[B],par[logg][B],sp[logg][B],h[B],mark[B],e[B][2]; 
vector<pair<int,int>> g[B]; 

void dfs(int v, int father){
	mark[v] = 1; 
	par[0][v] = father; 
	for(int i=1; i<logg; i++){par[i][v] = par[i-1][par[i-1][v]];}
	for(pair<int,int> cur : g[v]){
		int u = cur.first, w = cur.second; 
		if (mark[u]){continue;}
		dist[u] = dist[v] + w; 
		h[u] = h[v] + 1;
		dfs(u,v); 
		sub[v] = min(sub[v],sub[u]+w); 
	}
	sp[0][v] = sub[v]-dist[v];
}

pair<ll,ll> k_par(int v, ll k){
	if (k < 0){return{inf,inf};}
	ll ans = inf; 
	for(int i=logg-1; i>=0; i--){
		if ((k>>i)&1){
			ans = min(ans,sp[i][v]);
			v = par[i][v];
		}
	}
	if (sp[0][v] < ans){ans = sp[0][v];}
	return {v,ans};

}

void solve(){ 
	int n,s,q,st; cin >> n >> s >> q >> st; 
	sub[1] = inf; 
	for(int i=1; i<n; i++){
		int v,u,w; cin >> v >> u >> w; 
		g[v].push_back({u,w});
		g[u].push_back({v,w}); 
		e[i][0] = v; e[i][1] = u; 
		sub[i+1] = inf; 
	}
	for(int i=1; i<=s; i++){
		int get; cin  >> get; 
		sub[get] = 0;
	}
	dfs(st,0); 
	for(int k = 1; k < logg; k++){
		for (int i = 1; i<=n; i++){
			sp[k][i] = min(sp[k-1][i],sp[k-1][par[k-1][i]]);
		}
	}
	while(q--){
		int v,rem; cin >> rem >> v;
		if (h[e[rem][0]] < h[e[rem][1]]){swap(e[rem][0],e[rem][1]);}
		pair<ll,ll> giv = k_par(v,h[v]-h[e[rem][0]]); 
		if (giv.first != e[rem][0]){
			cout << "escaped" << endl;
			continue;
		}
		ll tmp = giv.second + dist[v]; 
		if (tmp >= inf){cout << "oo" << endl;}
		else{cout << tmp << endl;}
	}
}
 
int32_t main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int t; t=1;
	while(t--){solve();}
	return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 27 / 27
• Subtask 3: 23 / 23
• Subtask 4: 41 / 41