Submission #511175

#	Time	Username	Problem	Language	Result	Execution time	Memory
511175		akhan42	Valley (BOI19_valley)	C++17	100 / 100	164 ms	23504 KiB

valley

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
//using namespace __gnu_pbds;

#define F first
#define S second
#define forn(i, n) for(int i = 0; i < n; ++i)
#define forbn(i, b, n) for(int i = b; i < n; ++i)
#define sz(v) (int)v.size()
#define pb push_back
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define mp make_pair
#define at(m, k) (m.find(k) != m.end() ? m[k] : 0)

typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long long ll;
//typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

template <class T> inline void mineq(T &a, T b) { a = min(a, b); }
template <class T> inline void maxeq(T &a, T b) { a = max(a, b); }

const int MX = 100 * 1000 + 10;
ll INF = 1ll * 1000 * 1000 * 1000 * 1000 * 1000 * 1000;

struct Seg {
	int n;
	vector<ll> t;

	Seg(int n): n(n) {
		t.assign(2 * n, 0);
	}

	void update(int p, ll val) {
		for(t[p += n] = val; p > 1; p >>= 1)
			t[p >> 1] = min(t[p], t[p ^ 1]);
	}

	ll query(int l, int r) {
		ll res = INF;
		for(l += n, r += n + 1; l < r; l >>=1, r >>= 1) {
			if(l & 1) mineq(res, t[l++]);
			if(r & 1) mineq(res, t[--r]);
		}
		return res;
	}
};

int n, s, q, e;
vii gr[MX];
ii edge[MX];
int tin[MX], tout[MX];
bool magaz[MX];
int node2depth[MX];
int timer = -1;

Seg mag2rast(MX);
Seg rd(MX);

vii v2q[MX];
ll ans[MX];


void dfs(int node = e, int par = 0, int depth = 0, ll dist = 0) {
	tin[node] = ++timer;
	mag2rast.update(timer, magaz[node] ? dist : INF);
	node2depth[node] = depth;

	for(ii nb_w: gr[node]) {
		int nb = nb_w.F, w = nb_w.S;
		if(nb == par) continue;

		dfs(nb, node, depth + 1, dist + w);
	}
	tout[node] = timer;
}


void dfs2(int node = e, int par = 0, int depth = 0, ll dist = 0) {
	ll rast_mag = mag2rast.query(tin[node], tout[node]);
	rd.update(depth, rast_mag == INF ? INF : (rast_mag - 2 * dist));

	if(sz(v2q[node])) {
		for(ii par1qi: v2q[node]) {
			int par = par1qi.F, qi = par1qi.S;
			int par_depth = node2depth[par];
//			cerr << node << ' ' << par_depth << ' ' << depth << '\n';
//			cerr << dist << ' ' << rd.query(par_depth, depth) << '\n';
			ll tmp = rd.query(par_depth, depth);
			ans[qi] = tmp == INF ? INF : dist + tmp;
		}
	}

	for(ii nb_w: gr[node]) {
		int nb = nb_w.F, w = nb_w.S;
		if(nb == par) continue;

		dfs2(nb, node, depth + 1, dist + w);
	}
}


bool par_son(int par, int son) {
	return tin[par] <= tin[son] && tout[son] <= tout[par];
}


void solve() {
	cin >> n >> s >> q >> e;
	forbn(i, 1, n) {
		int a, b, w;
		cin >> a >> b >> w;
		edge[i] = mp(a, b);
		gr[a].eb(b, w);
		gr[b].eb(a, w);
	}
	forn(_, s) {
		int a;
		cin >> a;
		magaz[a] = true;
	}

	dfs();

	forn(qi, q) {
		int i, r;
		cin >> i >> r;
		int a = edge[i].F, b = edge[i].S;
		if(!par_son(a, b))
			swap(a, b);

		if(par_son(b, r)) {
//			cerr << b << ' ' << r << '\n';
			v2q[r].eb(b, qi);
		} else {
			ans[qi] = -1;
		}
	}

	dfs2();

	forn(qi, q) {
		if(ans[qi] == -1) {
			cout << "escaped\n";
		}
		else if(ans[qi] == INF) {
			cout << "oo\n";
		}
		else {
			cout << ans[qi] << '\n';
		}
	}
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

//	freopen("262144.in", "r", stdin);
//	freopen("262144.out", "w", stdout);

	int t = 1;
//	cin >> t;
	while(t--) {
		solve();
	}
}

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