Submission #847341

#	Time	Username	Problem	Language	Result	Execution time	Memory
847341		mat_jur	Valley (BOI19_valley)	C++17	100 / 100	225 ms	43956 KiB

valley

#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
auto&operator<<(auto &o, pair<auto, auto> p) {o << "(" << p.first << ", " << p.second << ")"; return o;}
auto operator<<(auto &o, auto x)->decltype(x.end(), o) {o<<"{"; for(auto e : x) o<<e<<", "; return o<<"}";}
#define debug(X) cerr << "["#X"]: " << X << '\n';
#else 
#define debug(X) ;
#endif
#define ll long long
#define all(v) (v).begin(), (v).end()
#define FOR(i,l,r) for(int i=(l);i<=(r);++i)
#define ROF(i,r,l) for(int i=(r);i>=(l);--i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) int(x.size())
#define fi first
#define se second
#define eb emplace_back

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

	int n, S, q, e;
	cin >> n >> S >> q >> e;
	e--;
	vector<tuple<int, int, int>> kr(n-1);
	vector<bool> s(n);
	vector<vector<pair<int, int>>> G(n);
	for (auto &[u, v, w] : kr) {
		cin >> u >> v >> w;
		u--; v--;
		G[u].eb(make_pair(v, w));
		G[v].eb(make_pair(u, w));
	}
	REP(i, S) {
		int c;
		cin >> c;
		c--;
		s[c] = true;
	}

	constexpr ll inf = 1e18;
	int timer = 0;
	int l = int(log2(n));
	vector p(n, vector(l+1, -1));
	vector minn(n, vector(l+1, inf));
	vector<int> start(n), end(n);
	vector<ll> d(n);
	vector<ll> magic(n);
	function<void(int, int)> dfs = [&](int v, int P) {
		p[v][0] = P; 
		start[v] = timer++;
		for(auto e : G[v]) {
			int u = e.fi, w = e.se;  
			if (u == P) continue;
			d[u] = d[v]+w;
			dfs(u, v);
		}
		if (s[v]) magic[v] = d[v]; 
		else {
			magic[v] = inf;
			for (auto e : G[v]) {
				int u = e.fi;
				if (u == P) continue;
				magic[v] = min(magic[v], magic[u]);
			}
		}
		end[v] = timer++;
	};
	dfs(e, -1);
	REP(v, n) if(magic[v] != inf) magic[v] -= 2*d[v];
	REP(i, n) {
		if (p[i][0] == -1) minn[i][0] = inf;
		else minn[i][0] = magic[p[i][0]];
	}
	FOR(j, 1, l) {
		REP(i, n) {
			if (p[i][j-1] != -1) {p[i][j] = p[p[i][j-1]][j-1]; minn[i][j] = min(minn[i][j-1], minn[p[i][j-1]][j-1]);}
		}
	}
	debug(magic);
	debug(p);
	REP(J, q) {
		int I, r;
		cin >> I >> r;
		I--; r--;
		int a = get<0>(kr[I]), b = get<1>(kr[I]);
		if (d[a] > d[b]) swap(a, b);
//		cerr << a << ' ' << b << '\n';
		if (!(start[b] <= start[r] && end[r] <= end[b])) {cout << "escaped \n"; continue;}
		//binlift
		ll mn = magic[r];
		ll D = d[r];
		ROF(i, l, 0) {
			if (p[r][i] == -1) continue;
			if (start[p[r][i]] < start[b] && end[b] < end[p[r][i]]) continue;
			mn = min(mn, minn[r][i]);
			r = p[r][i];
//			cerr << r << '\n';
		}
		if (mn >= inf) cout << "oo \n";
		else cout << mn+D << '\n';
//		cout << '\n';
	}

	return 0;
}

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