Submission #496570

#	Time	Username	Problem	Language	Result	Execution time	Memory
496570		Ierus	Valley (BOI19_valley)	C++17	100 / 100	513 ms	54604 KiB

valley

#include<bits/stdc++.h>
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
*/
using namespace std;
#pragma GCC optimize ("unroll-loops,Ofast,O3")
#pragma GCC target("avx,avx2,fma")
#define F first
#define S second
#define sz(x) (int)x.size()
#define pb push_back
#define eb emplace_back
#define int long long
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define NFS ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
//#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
typedef long long ll;
const int E = 1e6+777;
const long long inf = 1e18+777;
const int N = 1e5+777;
const int MOD = 1e9+7;
const bool I = 1;
const int LG = 19;
int up[N][LG+2], tin[N], tout[N], timer, dp[N][LG+2];
int n, s, q, e, h[N], dist[N];
bool mag[N];
struct edge{int x, y, w;}edge[N];
vector<pair<int,int>> g[N];
vector<int> d(N, inf);
void dfs(int v, int p = 1){
	tin[v] = ++timer;
	h[v] = h[p] + 1;
	if(mag[v]) d[v] = 0;
	for(auto to : g[v]){
		if(to.F == p) continue;
		dist[to.F] = dist[v] + to.S;
		dfs(to.F, v);
 		d[v] = min(d[v], d[to.F] + to.S);
	}
	tout[v] = timer;
}
void dfs1(int v, int p) {
	up[v][0] = p;
	dp[v][0] = min(d[v] - dist[v], d[p] - dist[p]);
	for (int i = 1; i <= LG; ++i){
		up[v][i] = up[up[v][i-1]][i-1];
		dp[v][i] = min(dp[v][i-1], dp[up[v][i-1]][i-1]);	
	}
	for (auto to: g[v]){
		if (to.F != p){
			dfs1(to.F, v);
		}
	}
}
bool upper(int a, int b) {
	return tin[a] <= tin[b] && tout[b] <= tout[a] ;
}
//int lca (int a, int b){
//	if (upper(a, b)) return a;
//	if (upper(b, a)) return b;
//	for (int i = LG; i>=0; --i)
//		if (!upper(up[a][i], b))
//			a = up[a][i];
//	return up[a][0];
//}
int get(int v, int u){
	if(v == u) return d[v] - dist[u];
//	cerr << "Get: " << v << " step: " << step << "\n";
	int res = inf;
	for(int i = LG; i >= 0; --i){
		if(!upper(up[v][i], u)){
			res = min(res, dp[v][i]);
			
//			cerr << "DO: " << res << '\n';
			v = up[v][i];
		}
	}
	return min(res,dp[v][0]);
}
signed main(){
	cin >> n >> s >> q >> e;
	for(int i = 1; i < n; ++i){
		int x, y, w;
		cin >> x >> y >> w;
		g[x].pb({y, w});
		g[y].pb({x, w});
		edge[i] = {x, y, w};
	}
	for(int i = 1; i <= s; ++i){
		int xx; cin >> xx;
		mag[xx] = true;
	}
	dfs(e, e);
	dfs1(e,e);
//	for(int i = 1; i <= n; ++i){
//		cout << "d["<<i<<"]: " << d[i] << '\n';
//	}
//	for(int i = 1; i <= n; ++i){
//		cout << "dist["<<i<<"]: " << dist[i] << '\n';
//	}
	for(int i, v; q--;){
		cin >> i >> v;
		if(h[edge[i].x] < h[edge[i].y]){
			swap(edge[i].x, edge[i].y);
		}
//		cerr << "x: " << edge[i].x << " lca: " << lca(edge[i].x, v) << '\n';
		if(!upper(edge[i].x, v)){
			cout << "escaped\n";
			continue;
		}
		int cur = min(d[v], get(v, edge[i].x) + dist[v]);
		if(cur == inf) cout << "oo\n";
		else cout << cur << '\n';
	}
}

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