Submission #696073

#	Time	Username	Problem	Language	Result	Execution time	Memory
696073		Makarooni	Valley (BOI19_valley)	C++17	100 / 100	203 ms	41768 KiB

valley

/* IN THE NAME OF GOD */
/* |\/| /-\ |\| | |\/| /-\ */

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

#define sz(x) (int)x.size()
#define endl '\n'
#define pb push_back
#define all(x) x.begin(), x.end()
#define F first
#define S second
#define mr make_pair
//#define int long long
#define pii pair<int, int>
typedef long double ld;
typedef long long ll;

mt19937 rng (chrono::high_resolution_clock::now().time_since_epoch().count());

const int N = 1e5 + 10;
const int MOD = 1e9 + 7;
const int inf = 1e9 + 1;
const ll INF = 3e18;

vector<pii> g[N];
int tin[N], tout[N], T, par[N][20], h[N];
ll b[N][20], d[N], f[N];
bool shop[N];

void pdfs(int v, int p){
	tin[v] = ++T;
	if(shop[v])
		f[v] = 0;
	for(int i = 1; i < 20; i++)
		par[v][i] = par[par[v][i - 1]][i - 1];
	for(pii u : g[v]){
		if(u.F == p)
			continue;
		par[u.F][0] = v;
		d[u.F] = d[v] + u.S;
		h[u.F] = h[v] + 1;
		pdfs(u.F, v);
		f[v] = min(f[v], f[u.F] + u.S);
	}
	tout[v] = ++T;
}

void dfs(int v, int p){
	for(int i = 1; i < 20; i++)
		b[v][i] = min(b[v][i - 1], b[par[v][i - 1]][i - 1] + d[v] - d[par[v][i - 1]]);
	for(pii u : g[v]){
		if(u.F == p)
			continue;
		b[u.F][0] = f[v] + u.S;
		b[u.F][0] = min(b[u.F][0], f[u.F]);
		dfs(u.F, v);
	}
}

int32_t main(){
	ios_base:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n, s, q, end;
	cin >> n >> s >> q >> end;
	int u, v, w;
	vector<pii> e;
	for(int i = 1; i < n; i++){
		cin >> u >> v >> w;
		g[u].pb(mr(v, w));
		g[v].pb(mr(u, w));
		e.pb(mr(u, v));
	}
	for(int i = 1; i <= s; i++){
		cin >> v;
		shop[v] = 1;
	}
	for(int i = 1; i <= n; i++)
		f[i] = INF;
	pdfs(end, 0);
	dfs(end, 0);
	while(q--){
		cin >> w >> v;
		w--;
		if(tin[e[w].F] < tin[e[w].S])
			swap(e[w].F, e[w].S);
		bool f1 = (tin[e[w].F] <= tin[v] && tout[e[w].F] >= tout[v]), f2 = (tin[e[w].F] <= tin[end] && tout[e[w].F] >= tout[end]);
		if(!(f1 ^ f2))
			cout << "escaped" << endl;
		else{
			if(f1){
				int H = h[v] - h[e[w].F];
				ll ans = f[v], D = 0;
				for(int j = 0; j < 20; j++){
					if(H & (1 << j)){
						ans = min(ans, b[v][j] + D);
						D += d[v] - d[par[v][j]];
						v = par[v][j];
					}
				}
				if(ans == INF)
					cout << "oo" << endl;
				else
					cout << ans << endl;
			}
		}
	}
}

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