Submission #1104951

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104951		Acanikolic	Valley (BOI19_valley)	C++14	100 / 100	143 ms	45136 KiB

valley

#include <bits/stdc++.h>  

#define int long long 

#define pb push_back
 
#define F first
 
#define S second
 
using namespace std;
 
const int N = 1e5 + 10;
 
const int mod = 1e9 + 7;
 
const long long inf = 1e18;

const int LOG = 17;

vector<pair<int,int>>g[N];
int dist[N],dp[N],up[N][LOG],mn[N][LOG],in[N],out[N],timer = 0;
bool shop[N],have[N];
pair<int,int>edges[N];

void dfs(int x,int par) {
	in[x] = ++timer;
	have[x] = shop[x];
	for(auto X : g[x]) {
		if(X.F == par) continue;
		dist[X.F] = dist[x] + X.S;
		dfs(X.F,x);
		have[x] |= have[X.F];
	}
	out[x] = timer;
}

void Dfs(int x,int par) {
	if(shop[x]) dp[x] = dist[x];
	else dp[x] = inf;
	for(auto X : g[x]) {
		if(X.F == par) continue;
		Dfs(X.F,x);
		dp[x] = min(dp[x],dp[X.F]);
	}
}

bool In(int u,int v) {
	return in[u] <= in[v] && out[u] >= out[v];
} 

int lift(int x,int v) {
	int res = inf;
	for(int j = LOG - 1; j >= 0; j--) {
		if(In(v,up[x][j])) {
			res = min(res,mn[x][j]);
			x = up[x][j];
		}
	}
	//cout << "dbg " << dp[x] << endl;
	res = min(res,dp[x]);
	return res;
}

void setup(int x,int par) {
	up[x][0] = par;
	mn[x][0] = dp[x];
	for(int j = 1; j < LOG; j++) {
		up[x][j] = up[up[x][j - 1]][j - 1];
		mn[x][j] = min(mn[x][j - 1],mn[up[x][j - 1]][j - 1]);
	}
	for(auto X : g[x]) {
		if(X.F == par) continue;
		setup(X.F,x);
	}
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 	
 	int n,s,q,e;
 	cin >> n >> s >> q >> e;
	for(int i = 1; i <= n - 1; i++) {
		int u,v,w;
		cin >> u >> v >> w;
		edges[i] = {u,v};
		g[u].pb({v,w});
		g[v].pb({u,w});
	}
	for(int i = 1; i <= s; i++) {
		int x;
		cin >> x;
		shop[x] = true;
	}
	dfs(e,0);
	Dfs(e,0);
	for(int i = 1; i <= n; i++) dp[i] -= 2 * dist[i];
	setup(e,0);
	/*cout << dp[3] << endl;
	cout << lift(5,3) + dist[5] << endl;*/
	while(q--) {
		int i,r;
		cin >> i >> r;
		int node = edges[i].F;
		if(in[edges[i].F] < in[edges[i].S]) node = edges[i].S;
		if(!In(node,r)) {
			cout << "escaped\n";
			continue;
		}else if(!have[node]) {
			cout << "oo\n";
			continue;
		}
		cout << lift(r,node) + dist[r] << "\n";
	}
    return 0;
}

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