Submission #405510

#	Time	Username	Problem	Language	Result	Execution time	Memory
405510		knightron0	Valley (BOI19_valley)	C++14	100 / 100	363 ms	178228 KiB

valley

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

#define pb push_back
#define fr first
#define sc second
#define clr(a, x) memset(a, x, sizeof(a))
#define dbg(x) cout<<"("<<#x<<"): "<<x<<endl;
#define printvector(arr) for (auto it = arr.begin(); it != arr.end(); ++it) cout<<*it<<" "; cout<<endl;
#define all(v) v.begin(), v.end()
#define lcm(a, b) (a * b)/__gcd(a, b)
#define int long long int
#define printvecpairs(vec) for(auto it: vec) cout<<it.fr<<' '<<it.sc<<endl;
#define endl '\n'
#define float long double

const int MOD = 1e9 + 7;
const int INF = 2e15;
const int MAXN = 1e5 + 5;

vector<pair<int, int>> adj[MAXN];
int up[MAXN][100], upmn[MAXN][100], depth[MAXN], dist[MAXN];
vector<pair<int, int>> edges;
bool flag[MAXN];
int timer = 0, n, l;
int tout[MAXN], tin[MAXN];
int dp[MAXN];

void dfs(int v, int p, int d, int dpth){
	timer++;
	dist[v] = d;
	depth[v] = dpth;
	tin[v] = timer;
	up[v][0] = p;
	for(int i=1;i<=l;i++){
		up[v][i] = up[up[v][i-1]][i-1];
	}
	for(auto &[u, w]: adj[v]){
		if(u != p){
			dfs(u, v, d+w, dpth+1);
		}
	}
	timer++;
	tout[v] = timer;
}

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

void preprocess(){
	timer = 0;
	clr(tout, 0);
	clr(tin, 0);
	l = 20;
	clr(flag, 0);
	clr(depth, 0);
	clr(up, 0);
	clr(dist, 0);
}

int lca(int u, int v){
	if(isanc(u, v)) return u;
	if(isanc(v, u)) return v;
	for(int i = l;i >= 0;i--){
        if(!isanc(up[u][i], v))
            u = up[u][i];
    }
    return up[u][0];
}

int dfs0(int u, int p){
	int ans = INF;
	if(flag[u]) ans = dist[u];
	for(auto &[v, w]: adj[u]){
		if(v == p) continue;
		ans = min(ans, dfs0(v, u));
	}
	dp[u] = -2* dist[u] + ans;
	return ans;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    #endif
	int n, c, q, s;
	cin>>n>>c>>q>>s;
	preprocess();
	for(int i=0;i<n-1;i++){
		int u, v, w;
		cin>>u>>v>>w;
		adj[u].pb({v, w});
		adj[v].pb({u, w});
		edges.pb({u, v});
	}
	
	for(int i=0;i<c;i++){
		int x; cin>>x;
		flag[x] = true;
	}
	dfs(s, s, 0, 0);
	dfs0(s, -1);
	for(int i=1;i<=n;i++){
		upmn[i][0] = dp[up[i][0]];
	}
	for(int i=1;i<=l;i++){
		for(int j = 1;j<=n;j++){
			upmn[j][i]= min(upmn[j][i-1], upmn[up[j][i-1]][i-1]);
		}
	}
	while(q--){
		int i, u;
		cin>>i>>u;
		i--;
		int root = -1;
		if(depth[edges[i].fr] < depth[edges[i].sc]){
			root = edges[i].sc;
		} else {
			root = edges[i].fr;
		}
		if(!isanc(root, u)){
			cout<<"escaped"<<endl;
			continue;
		}
		int curr = u;
		int ans = dp[u];
		for(int i = l;i >= 0;i--){
			if(depth[up[curr][i]] >= depth[root]){
				ans = min(ans, upmn[curr][i]);
				curr = up[curr][i];
			}
		}
		if(ans+dist[u] >= 1e14){
			cout<<"oo"<<endl;
		} else {
			cout<<ans+dist[u]<<endl;
		}
	
	}
    return 0;
}

Compilation message (stderr)

valley.cpp: In function 'void dfs(long long int, long long int, long long int, long long int)':
valley.cpp:38:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   38 |  for(auto &[u, w]: adj[v]){
      |            ^
valley.cpp: In function 'long long int dfs0(long long int, long long int)':
valley.cpp:75:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   75 |  for(auto &[v, w]: adj[u]){
      |            ^

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