Submission #394223

#	Time	Username	Problem	Language	Result	Execution time	Memory
394223		ritul_kr_singh	Valley (BOI19_valley)	C++17	100 / 100	238 ms	49604 KiB

valley

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << ' ' <<
#define nl << '\n'

const int MAXN = 1e5, INF = 1e18;

vector<array<int, 2>> g[MAXN];
array<int, 18> p [MAXN], m[MAXN];
vector<int> s(MAXN, INF), d(MAXN), depth(MAXN), t0(MAXN), t1(MAXN);
int dfsTimer = 0;

int dfs0(int u, int par, int dist){
	d[u] = dist;
	t0[u] = dfsTimer++;
	for(auto &e : g[u]) if(e[0] != par) s[u] = min(s[u], dfs0(e[0], u, dist + e[1]) + e[1]);
	t1[u] = dfsTimer++;
	return s[u];
}

void dfs1(int u, int par, int dep){
	depth[u] = dep;
	p[u][0] = par;
	m[u][0] = min(s[u] - d[u], s[par] - d[par]);
	for(int i=0; i<17; ++i){
		m[u][i+1] = min(m[u][i], m[p[u][i]][i]);
		p[u][i+1] = p[p[u][i]][i];
	}
	for(auto &e : g[u]) if(e[0] != par) dfs1(e[0], u, dep + 1);
}

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	int n, shops, q, root, x, y, z; cin >> n >> shops >> q >> root;
	array<int, 2> edges[n-1];

	for(int i=1; i<n; ++i){
		cin >> x >> y >> z; --x, --y;
		g[x].push_back({y, z});
		g[y].push_back({x, z});
		edges[i-1] = {x, y};
	}

	while(shops--) cin >> x, s[x-1] = 0;
	--root;
	dfs0(root, root, 0);
	dfs1(root, root, 0);

	while(q--){
		cin >> x >> y; --x, --y;
		x = edges[x][p[edges[x][1]][0] == edges[x][0]];
		if(t0[x] <= t0[y] and t1[y] <= t1[x]){ //ancestor
			int res = s[y], j = d[y];
			int diff = depth[y] - depth[x];
			for(int i=0; i<18; ++i) if(diff & (1<<i)) res = min(res, m[y][i]+j), y = p[y][i];
			if(res >= INF) cout << "oo" nl;
			else cout << res nl;
		}else cout << "escaped" nl;
	}
}

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