Submission #1270638

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270638		thuhienne	Valley (BOI19_valley)	C++20	0 / 100	124 ms	17148 KiB

valley

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

const int LOG = 17;

int n,q,numshop,root;
int shop[100009];

vector <pair <int,int>> adj[100009];

struct {
	int u,v,w;
} edge[100009];

int h[100009],up[100009][LOG + 1];
long long depth[100009];

void dfs(int node,int par) {
	for (auto x : adj[node]) if (x.first != par) {
		int ver = x.first,w = x.second;
		h[ver] = h[node] + 1;
		depth[ver] = depth[node] + w;
		up[ver][0] = node;
		for (int i = 1;i <= LOG;i++) up[ver][i] = up[up[ver][i - 1]][i - 1];
		dfs(ver,node);
	}
}
int raise(int node,int diff) {
	for (int i = LOG;i >= 0;i--) if (diff >> i & 1) node = up[node][i];
	return node;
}

namespace sub123 {
	bool check() {
		return 1ll*n*q <= 1000000 || numshop == n;
	}
	int lca(int u,int v) {
		if (h[u] < h[v]) swap(u,v);
		u = raise(u,h[u] - h[v]);
		if (u == v) return u;
		for (int i = LOG;i >= 0;i--) if (up[u][i] != up[v][i]) {
			u = up[u][i];
			v = up[v][i];
		}
		return up[u][0];
	}
	bool _has(int child,int anc,int x,int y) {
		return lca(child,y) == y && h[x] >= h[anc];
	}
	bool has(int u,int v,int x,int y) {
		int d = lca(u,v);
		return _has(u,d,x,y) || _has(v,d,x,y);
	}
	
	void solve() {
		while (q--) {
			int vertice,_;cin >> _ >> vertice;
			int u = edge[_].u,v = edge[_].v;
			
			//check escape
			if (!has(vertice,1,u,v)) {
				cout << "escaped\n";
				continue;
			}
			//check shop
			if (numshop == n) {
				cout << 0 << '\n';
				continue;
			}
			long long ret = 1e18;
			for (int i = 1;i <= numshop;i++) if (!has(vertice,shop[i],u,v)) {
				ret = min(ret,depth[vertice] + depth[shop[i]] - 2*depth[lca(vertice,shop[i])]);
			}
			if (ret == 1e18) cout << "oo\n";
			else cout << ret << '\n';
		}
	}
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(nullptr);
//  freopen(".inp","r",stdin);
//  freopen(".out","w",stdout);
	cin >> n >> numshop >> q >> root;
	for (int i = 1;i < n;i++) {
		int u,v,w;cin >> u >> v >> w;
		adj[u].push_back({v,w});
		adj[v].push_back({u,w});
		edge[i] = {u,v,w};
	}
	for (int i = 1;i <= numshop;i++) {
		cin >> shop[i];
	}
	dfs(root,-1);
	for (int i = 1;i < n;i++) if (h[edge[i].u] > h[edge[i].v]) swap(edge[i].u,edge[i].v);
	if (sub123::check()) {
		sub123::solve();
		return 0;
	}
}

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