Submission #1086672

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086672		ZeroCool	Valley (BOI19_valley)	C++14	100 / 100	142 ms	56148 KiB

valley

#include <bits/stdc++.h>

using namespace std;

#define ar array
#define int long long
#define ld long double
#define crash assert(69 == 420)

const int MOD = 1e9 + 7;
const int INF = 1e17;
const int N = 2e5  + 20;
const int LOG = 20;

int n, k, q, r;

vector<ar<int, 2>> g[N];
int in[N], out[N], T = -1;
int dep[N],dst[N], dp[N];
int up[N][LOG], mn[N][LOG];

void dfs(int x,int p){
	in[x] = ++T;
	for(auto [u, w]: g[x]){
		if(u == p)continue;
		dep[u] = dep[x] + 1;
		dst[u] = dst[x] + w;
		dfs(u, x);
		dp[x] = min(dp[x], dp[u] + w);
	}
	out[x] = T;
	up[x][0] = p;
	if(dp[x] < INF)mn[x][0] = min(mn[x][0], dp[x] - dst[x]);
}

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

int qry(int u,int k){
	int ans = INF;
	for(int i = 0;i < LOG;i++){
		if((1 << i) & k){
			ans = min(ans, mn[u][i]);
			u = up[u][i];
		}
	}
	return ans;
}

signed main(){ios_base::sync_with_stdio(false);cin.tie(0);
	cin>>n>>k>>q>>r;
	--r;
	ar<int, 2> e[n];
	for(int i = 1;i < n;i++){
		int u, v, w;
		cin>>u>>v>>w;
		--u, --v;
		e[i] = {u, v};
		g[u].push_back({v, w});
		g[v].push_back({u, w});
	}
	for(int i = 0;i < n;i++)dp[i] = mn[i][0] = INF;
	while(k--){
		int x;
		cin>>x;
		--x;
		dp[x] = 0;
	}
	dfs(r, r);
	for(int j = 1;j < LOG;j++){
		for(int i = 0;i < n;i++){
			up[i][j] = up[up[i][j - 1]][j - 1];
			mn[i][j] = min(mn[i][j - 1], mn[up[i][j - 1]][j - 1]);
		}
	}
	while(q--){
		int i, p;
		cin>>i>>p;
		--p;
		if(dep[e[i][0]] < dep[e[i][1]])swap(e[i][0], e[i][1]);
		if(!anc(e[i][0], p)){
			cout<<"escaped\n";
			continue;
		}
		int ans = dst[p] + qry(p, dep[p] - dep[e[i][0]] + 1);
		if(ans >= INF)cout<<"oo\n";
		else cout<<ans<<'\n';
	}
}

Compilation message (stderr)

valley.cpp: In function 'void dfs(long long int, long long int)':
valley.cpp:24:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   24 |  for(auto [u, w]: g[x]){
      |           ^

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