Submission #1186295

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186295		kl0989e	Valley (BOI19_valley)	C++20	100 / 100	234 ms	45888 KiB

valley

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define vl vector<ll>
#define pi pair<int, int>
#define pl pair<ll,ll>
#define all(x) (x).begin(),(x).end()

const int maxn=1e5+10;
const int logg=ceil(log2(maxn));

vector<vector<pl>> graph(maxn);
vector<pi> edges(maxn);
vi tin(maxn),tout(maxn);
int timer=0;
vl dst(maxn,1e18);
vl depth(maxn,0);
vector<vi> up(maxn,vi(logg+1));
vector<vl> vals(maxn,vl(logg+1));

void dfs(int cur, int prev, ll len) {
	tin[cur]=timer++;
	depth[cur]=depth[prev]+len;
	up[cur][0]=prev;
	for (int i=1; i<=logg; i++) {
		up[cur][i]=up[up[cur][i-1]][i-1];
	}
	for (auto [to,w]:graph[cur]) {
		if (prev==to) {
			continue;
		}
		dfs(to,cur,w);
		dst[cur]=min(dst[cur],dst[to]+w);
	}
	vals[cur][0]=dst[cur];
	tout[cur]=timer;
}

void dfs2(int cur, int prev) {
	for (int i=1; i<=logg; i++) {
		vals[cur][i]=min(vals[cur][i-1],vals[up[cur][i-1]][i-1]+depth[cur]-depth[up[cur][i-1]]);
	}
	for (auto [to,w]:graph[cur]) {
		if (prev==to) {
			continue;
		}
		dfs2(to,cur);
	}
}

bool is_root(int a, int b) {
	return (tin[a]<=tin[b] && tout[b]<=tout[a]);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
	int n,s,q,e;
	cin >> n >> s >> q >> e;
	e--;
	int a,b;
	ll c;
	for (int i=0; i<n-1; i++) {
		cin >> a >> b >> c;
		edges[i]={--a,--b};
		graph[a].pb({b,c});
		graph[b].pb({a,c});
	}
	for (int i=0; i<s; i++) {
		cin >> a;
		dst[--a]=0;
	}
	dfs(e,e,0);
	dfs2(e,e);
	for (int i=0; i<q; i++) {
		cin >> a >> b;
		a--;
		b--;
		int l=edges[a].fi;
		int r=edges[a].se;
		if (depth[l]<depth[r]) {
			swap(l,r);
		}
		if (!is_root(l,b)) {
			cout << "escaped\n";
			continue;
		}
		l=b;
		ll ans=1e18;
		for (int j=logg; j>=0; j--) {
			if (!is_root(up[l][j],r)) {
				ans=min(ans,vals[l][j]+depth[b]-depth[l]);
				l=up[l][j];
			}
		}
		ans=min(ans,vals[l][0]+depth[b]-depth[l]);
		if (ans==1e18) {
			cout << "oo\n";
		}
		else {
			cout << ans << '\n';
		}
	}
    return 0;
}

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