Submission #945146

#	Time	Username	Problem	Language	Result	Execution time	Memory
945146		NintsiChkhaidze	Valley (BOI19_valley)	C++17	100 / 100	245 ms	56268 KiB

valley

#include <bits/stdc++.h>
#define ll long long
#define s second
#define f first
#define pb push_back
#define pii pair <int,int>
#define left (h<<1),l,(l + r)/2
#define right ((h<<1)|1),(l + r)/2 + 1,r
#define int ll
using namespace std;

const int N = 1e5 + 3;

pair <pii,int> edge[N];
vector <pii> v[N];
int d[25][N],dep[N],dp[N],dist[N];
int mn[25][N];
int timer,tin[N],tout[N];

void dfs(int x,int par){
	dep[x] = dep[par] + 1;
	d[0][x] = par;
	tin[x] = ++timer;

	for (auto [to,w]: v[x]){
		if (to==par) continue;
		dp[to] = dp[x] + w;
		dfs(to,x);
		dist[x] = min(dist[x],dist[to] + w);
	}

	tout[x] = timer;
}

signed main(){
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);

	int n,s,q,root;
	cin>>n>>s>>q>>root;

	for (int i = 1; i < n; i++){
		int a,b,c;
		cin>>a>>b>>c;
		v[a].pb({b,c});
		v[b].pb({a,c});
		edge[i] = {{a,b},c};
	}

	for (int i = 1; i <= n; i++){
		dist[i] = 1e18;
	}
	for (int i = 1; i <= s; i++){
		int x;
		cin>>x;
		dist[x]=0;
	}

	dfs(root,root);
	for (int i = 1; i < n; i++){
		if (dep[edge[i].f.f] > dep[edge[i].f.s])
			swap(edge[i].f.f,edge[i].f.s);
	}

	for (int i =0;i <= 18; i++)
		for (int j = 0; j <= n; j++)
			mn[i][j] = 1e18;
	
	for (int j = 1; j <= n; j++)
		mn[0][j] = dist[j];

	for (int i = 1; i <= 18; i++){
		for (int j = 1; j <= n; j++){
			d[i][j] = d[i - 1][d[i - 1][j]];
			mn[i][j] = min(mn[i - 1][j],dp[j] - dp[d[i - 1][j]] + mn[i - 1][d[i - 1][j]]);
		}
	}

	while (q--){
		int x,y;
		cin>>x>>y;

		x = edge[x].f.s;
		if (!(tin[x] <= tin[y] && tout[y] <= tout[x])){
			cout<<"escaped"<<endl;
			continue;
		}

		int ans = 1e18,len = dep[y] - dep[x] + 1,D = 0;
		for (int i = 18; i >= 0; i--){
			if ((len & (1LL<<i)) > 0) {
				ans = min(ans,mn[i][y] + D);
				D += dp[y] - dp[d[i][y]];
				y = d[i][y];
			}
		}

		if (ans == 1e18) cout<<"oo"<<endl;
		else cout<<ans<<endl;
	}
}	

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