Submission #916438

#	Time	Username	Problem	Language	Result	Execution time	Memory
916438		OAleksa	Valley (BOI19_valley)	C++14	0 / 100	297 ms	36056 KiB

valley

#include <bits/stdc++.h>
//ako ovaj vaso daso misli da me pobedjuje.....
using namespace std;
#define int long long
#define f first
#define s second
const int N	= 1e5 + 69;
const int K = 18;
const int inf = 1e18;
int up[N][K];
int n, s, q, e, cnt[N], dep[N], par[N], sz[N], b[N];
int st[4 * N];
int tin[N], tout[N], timer, vis[N];
vector<int> shop;
vector<pair<int, int>> g[N];
vector<tuple<int, int, int>> edges;
void modify(int v, int tl, int tr, int l, int r, int val) {
	if (tl > r || tr < l)
		return;
	else if (tl >= l && tr <= r) {
		if (val == 1)
			st[v] = inf;
		else {
			if (tl == tr)
				st[v] = b[tl];
			else
				st[v] = min(st[v * 2], st[v * 2 + 1]);
		}
	}
	else {
		int mid = (tl + tr) / 2;
		modify(v * 2, tl, mid, l, r, val);
		modify(v * 2 + 1, mid + 1, tr, l, r, val);
		st[v] = min(st[v * 2], st[v * 2 + 1]);
	}
}
int get(int v, int tl, int tr, int l, int r) {
	if (tl > r || tr < l || st[v] == inf)
		return inf;
	else if (tl >= l && tr <= r)
		return st[v];
	else {
		int mid = (tl + tr) / 2;
		return min(get(v * 2, tl, mid, l, r), get(v * 2 + 1, mid + 1, tr, l, r));
	}
}
void dfs_sz(int v, int p) {
	if (vis[v]) {
		sz[v] = 0;
		return;
	}
	sz[v] = 1;
	for (auto u : g[v]) {
		if (u.f == p)
			continue;
		dfs_sz(u.f, v);
		sz[v] += sz[u.f];
	}
}
int find_cent(int v, int p, int x) {
	for (auto u : g[v]) {
		if (u.f != p && !vis[u.f] && sz[u.f] > x / 2)
			return find_cent(u.f, v, x);
	}
	return v;
}
void build(int v, int p) {
	dfs_sz(v, -1);
	int c = find_cent(v, -1, sz[v]);
	vis[c] = 1;
	par[c] = p;
	for (auto u : g[c]) {
		if (!vis[u.f])
			build(u.f, c);
	}
}
bool anc(int a, int b) {
	return tin[a] <= tin[b] && tout[a] >= tout[b];
}
int Lca(int a, int b) {
	if (anc(a, b))
		return a;
	else if (anc(b, a))
		return b;
	for (int i = K - 1;i >= 0;i--) {
		if (!anc(up[a][i], b) && up[a][i] > 0)
			a = up[a][i];
	}
	return up[a][0];
}
int distance(int a, int b) {
	return dep[a] + dep[b] - 2 * dep[Lca(a, b)];
}
void dfs(int v, int p) {
	tin[v] = ++timer;
	up[v][0] = p;
	b[tin[v]] = dep[v];
	for (int i = 1;i < K;i++)
		up[v][i] = up[up[v][i - 1]][i - 1];
	for (auto u : g[v]) {
		if (u.f == p)
			continue;
		dep[u.f] = dep[v] + u.s;
		dfs(u.f, v);
	}
	tout[v] = timer;
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int tt = 1;
  //cin >> tt;
  while (tt--) {
  	cin >> n >> s >> q >> e;
  	for (int i = 1;i <= n - 1;i++) {
  		int a, b, w;
  		cin >> a >> b >> w;
  		g[a].push_back({b, w});
  		g[b].push_back({a, w});
  		edges.push_back({a, b, w});
  	}
  	dfs(1, -1);
  	build(1, -1);
  	for (int i = 0;i <= 4 * n;i++)
  		st[i] = inf;
  	for (int i = 1;i <= s;i++) {
  		int x;
  		cin >> x;
  		modify(1, 1, n, tin[x], tin[x], 0);
  	}
  	for (int j = 0;j < q;j++) {
  		int i, start;
  		cin >> i >> start;
  		--i;
  		int x, a, b, w;
  		tie(a, b, w) = edges[i];	
  		x = (dep[a] > dep[b] ? a : b);
  		int ans = inf;
  		if (anc(x, e) && anc(x, start)) 
  			ans = -1;
  		else if (!anc(x, e) && !anc(x, start)) 
  			ans = -1;
  		else {
  			int t = start;
  			if (!anc(x, start))
  				modify(1, 1, n, tin[x], tout[x], 1);
  			while (t != -1) {
  				if (anc(x, t) == anc(x, start)) {
  					int y = get(1, 1, n, tin[t], tout[t]);
  					if (y != inf)
  						ans = min(ans, y + distance(t, start) - dep[t]);
  				}
  				t = par[t];
  			}
  			if (!anc(x, start))
  				modify(1, 1, n, tin[x], tout[x], 0);
  		}
  		if (ans == inf)
  			cout << "oo\n";
  		else if (ans == -1)
  			cout << "escaped\n";
  		else
  			cout << ans << '\n';
  	}
	}
  return 0;
}

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