Submission #918457

#	Time	Username	Problem	Language	Result	Execution time	Memory
918457		AlphaMale06	Valley (BOI19_valley)	C++17	100 / 100	294 ms	98492 KiB

valley

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define int long long
 
const int N = 100010;
vector<pair<int, int>> adj[N];
int n, s, q, e;
int h[N], cl[N], tin[N], tout[N];
int dist[N];
vector<pair<pair<int, int>, int>> edges;
int p[17][N];
bool isp[N];
int timer=-1;
int cst[N];
vector<int> sps;
vector<vector<int>> precalc;
 
void dfs(int v, int par){
	if(isp[v])dist[v]=0;
	h[v]=h[par]+1;
	p[0][v]=par;
	for(int i=1; i<=16; i++){
		p[i][v]=p[i-1][p[i-1][v]];
	}
	tin[v]=++timer;
	for(auto to : adj[v]){
		if(to.F!=par){
			dfs(to.F, v);
			dist[v]=min(dist[v], dist[to.F]+to.S);
		}
	}
	tout[v]=timer;
}
 
int anc(int a, int b){
	int ret=a;
	for(int i=0; i<17; i++){
		if(b&(1<<i)){
			ret=p[i][ret];
		}
	}
	return ret;
}
 
 
 
void solve(){
	cin >> n >> s >> q >> e;
	for(int i=0; i< n-1; i++){
		int x, y, z;
		cin >> x >> y >> z;
		edges.pb({{x, y}, z});
		adj[x].pb({y, z});
		adj[y].pb({x, z});
	}
	for(int i=0; i<=n; i++)dist[i]=1e18;
	for(int i=0; i< s; i++){
		int x;
		cin >> x;
		sps.pb(x);
		isp[x]=1;
	}
	dfs(e, 0);
	tin[0]=0; tout[0]=1e9;
	for(auto & p : edges){
		if(h[p.F.F]>h[p.F.S])swap(p.F.F, p.F.S);
		cst[p.F.S]=p.S;
	}
	int sq=300;
	precalc.pb({});
	for(int i=1; i<=n; i++){
		vector<int> prec;
		if(h[i]%sq==0){
			int x=i;
			int mn=dist[x];
			prec.pb(mn);
			int pth=0;
			while(x!=e){
				pth+=cst[x];
				x=p[0][x];
				mn=min(mn, dist[x]+pth);
				prec.pb(mn);
			}
		}
		precalc.pb(prec);
	}
	while(q--){
		int ind, v;
		cin >> ind >> v;
		pair<pair<int, int>, int> edge = edges[ind-1];
		if(h[edge.F.S]>h[v]){
			cout << "escaped\n";
			continue;
		}
		int str=anc(v, h[v]-h[edge.F.S]);
		if(str==edge.F.S){
			if(dist[str]==1e18){
				cout << "oo\n";
				continue;
			}
			int mn=dist[v];
			int pth=0;
			while(mn>0 && v!=str){
				if(precalc[v].size() && h[v]-h[str]>100){
					mn=min(mn, pth+precalc[v][h[v]-h[str]]);
					break;
				}
				pth+=cst[v];
				if(mn<=pth)break;
				v=p[0][v];
				mn=min(mn, pth+dist[v]);	
			}
			cout << mn << '\n';
		}
		else cout << "escaped\n";
	}
}
 
 
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	solve();
}

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