oj.uz

Submission #643396

# Submission time Handle Problem Language Result Execution time Memory
643396 2022-09-22T01:44:27 Z thiago_bastos Valley (BOI19_valley) C++17
100 / 100
 464 ms 35900 KB 
#include "bits/stdc++.h"

using namespace std;

#define INF 1000000000
#define INFLL 1000000000000000000ll
#define EPS 1e-9
#define all(x) x.begin(),x.end()
#define pb push_back
#define fi first
#define sc second

using i64 = long long;
using u64 = unsigned long long;
using ld = long double;
using ii = pair<int, int>;

const int N = 1e5 + 100, K = 17, M = 1 << 18;
const i64 L = 1e14L + 10;

vector<ii> adj[N];
int sp[K][N], depth[N], in[N], out[N], t;
int n, s, q, e;
i64 pre[N];

void dfs(int u, int p) {
	in[u] = t++;
	sp[0][u] = p;
	for(int i = 1; (1 << i) <= n; ++i) sp[i][u] = sp[i - 1][sp[i - 1][u]];
	for(auto [v, w] : adj[u]) {
		if(v == p) continue;
		depth[v] = 1 + depth[u];
		pre[t] = pre[in[u]] + w;
		dfs(v, u);
	}
	out[u] = t - 1;		
}

int LCA(int u, int v) {
	if(depth[u] > depth[v]) swap(u, v);
	int d = depth[v] - depth[u];
	for(int i = 0; (1 << i) <= d; ++i) if(d & (1 << i)) v = sp[i][v];
	if(u == v) return u;
	for(int i = 31 - __builtin_clz(n); i >= 0; --i) {
		if(sp[i][u] == sp[i][v]) continue;
		u = sp[i][u], v = sp[i][v];
	}
	return sp[0][u];
}

i64 dist(int a, int b) {
	return pre[in[a]] + pre[in[b]] - 2 * pre[in[LCA(a, b)]];
}

bool is_on_path(int a, int b, int c) {
	return dist(a, c) + dist(c, b) == dist(a, b);
}

i64 st[M], lazy[M];

void push(int k) {
	if(!lazy[k]) return;
	for(int i : {2*k,2*k+1}) {
		st[i] += lazy[k];
		lazy[i] += lazy[k];
	}
	lazy[k] = 0;
}

void build(int l, int r, int k = 1) {
	lazy[k] = 0;
	if(l == r) st[k] = pre[l];
	else {
		int m = (l + r) / 2;
		build(l, m, 2 * k);
		build(m + 1, r, 2 * k + 1);
		st[k] = min(st[2*k], st[2*k+1]);
	}
}

void upd(int l, int r, int x, int lo, int hi, int k = 1) {
	if(l > r) return;
	else if(hi - lo == r - l) {
		st[k] += x;
		lazy[k] += x;
	} else {
		int m = (lo + hi) / 2;
		push(k);
		upd(l, min(r, m), x, lo, m, 2 * k);
		upd(max(m + 1, l), r, x, m + 1, hi, 2 * k + 1);
		st[k] = min(st[2*k], st[2*k+1]);
	}
}

i64 query(int l, int r, int lo, int hi, int k = 1) {
	if(l > r) return INFLL;
	else if(hi - lo == r - l) return st[k];
	int m = (lo + hi) / 2;
	push(k);
	return min(query(l, min(r, m), lo, m, 2 * k), query(max(m + 1, l), r, m + 1, hi, 2 * k + 1));
}

vector<ii> queries[N];
ii ed[N];
i64 ans[N];

void dfsquery(int u, int p) {

	for(auto [v, w] : adj[u]) {
		if(v == p) continue;
		
		upd(in[v], out[v], -w, 0, n - 1);
		upd(0, in[v] - 1, w, 0, n - 1);
		upd(out[v] + 1, n - 1, w, 0, n - 1);
		
		dfsquery(v, u);

		upd(in[v], out[v], w, 0, n - 1);
		upd(0, in[v] - 1, -w, 0, n - 1);
		upd(out[v] + 1, n - 1, -w, 0, n - 1);
	}

	for(auto [ed_pos, k] : queries[u]) {
		auto [x, y] = ed[ed_pos];
		i64 cost;

		if(depth[x] < depth[y]) swap(x, y);	
		
		if(in[u] < in[x] || in[u] > out[x])
			cost = min(query(0, in[x] - 1, 0, n - 1), query(out[x] + 1, n - 1, 0, n - 1));
		else
			cost = query(in[x], out[x], 0, n - 1);

		ans[k] = cost;
	}
}

void solve() {
	cin >> n >> s >> q >> e;

	--e;

	for(int i = 1; i < n; ++i) {
		int a, b, c;
		cin >> a >> b >> c;
		--a, --b;
		ed[i - 1] = {a, b};
		adj[a].pb({b, c});
		adj[b].pb({a, c});
	}

	dfs(0, 0);

	vector<bool> shop(n, false);

	for(int i = 0; i < s; ++i) {
		int v;
		cin >> v;
		shop[--v] = true;
	}

	for(int i = 0; i < q; ++i) {
		int ed_pos, src;
		cin >> ed_pos >> src;
		--src, --ed_pos;
		auto [u, v] = ed[ed_pos];
		if(is_on_path(src, e, u) && is_on_path(src, e, v))
			queries[src].pb({ed_pos, i});
		else
			ans[i] = -1;
	}

	for(int i = 0; i < n; ++i) if(!shop[i]) pre[in[i]] = INFLL;

	build(0, n - 1);
	dfsquery(0, 0);

	for(int i = 0; i < q; ++i) {
		if(ans[i] < 0) cout << "escaped\n";
		else if(ans[i] > L) cout << "oo\n";
		else cout << ans[i] << '\n';
	}
}

int main() {
	ios_base :: sync_with_stdio(false);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--) solve();
	return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5332 KB Output is correct
2 Correct 6 ms 5332 KB Output is correct
3 Correct 5 ms 5332 KB Output is correct
4 Correct 6 ms 5336 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5332 KB Output is correct
2 Correct 6 ms 5332 KB Output is correct
3 Correct 5 ms 5332 KB Output is correct
4 Correct 6 ms 5336 KB Output is correct
5 Correct 4 ms 5304 KB Output is correct
6 Correct 4 ms 5204 KB Output is correct
7 Correct 5 ms 5300 KB Output is correct
8 Correct 4 ms 5204 KB Output is correct
9 Correct 6 ms 5204 KB Output is correct
10 Correct 5 ms 5204 KB Output is correct
11 Correct 5 ms 5308 KB Output is correct
12 Correct 5 ms 5304 KB Output is correct
13 Correct 4 ms 5304 KB Output is correct
14 Correct 5 ms 5332 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 306 ms 28836 KB Output is correct
2 Correct 356 ms 28492 KB Output is correct
3 Correct 345 ms 28528 KB Output is correct
4 Correct 464 ms 31056 KB Output is correct
5 Correct 370 ms 29716 KB Output is correct
6 Correct 365 ms 35900 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5332 KB Output is correct
2 Correct 6 ms 5332 KB Output is correct
3 Correct 5 ms 5332 KB Output is correct
4 Correct 6 ms 5336 KB Output is correct
5 Correct 4 ms 5304 KB Output is correct
6 Correct 4 ms 5204 KB Output is correct
7 Correct 5 ms 5300 KB Output is correct
8 Correct 4 ms 5204 KB Output is correct
9 Correct 6 ms 5204 KB Output is correct
10 Correct 5 ms 5204 KB Output is correct
11 Correct 5 ms 5308 KB Output is correct
12 Correct 5 ms 5304 KB Output is correct
13 Correct 4 ms 5304 KB Output is correct
14 Correct 5 ms 5332 KB Output is correct
15 Correct 306 ms 28836 KB Output is correct
16 Correct 356 ms 28492 KB Output is correct
17 Correct 345 ms 28528 KB Output is correct
18 Correct 464 ms 31056 KB Output is correct
19 Correct 370 ms 29716 KB Output is correct
20 Correct 365 ms 35900 KB Output is correct
21 Correct 304 ms 28472 KB Output is correct
22 Correct 305 ms 28020 KB Output is correct
23 Correct 363 ms 28012 KB Output is correct
24 Correct 389 ms 29800 KB Output is correct
25 Correct 389 ms 34072 KB Output is correct
26 Correct 278 ms 28360 KB Output is correct
27 Correct 317 ms 28100 KB Output is correct
28 Correct 322 ms 27960 KB Output is correct
29 Correct 413 ms 30600 KB Output is correct
30 Correct 387 ms 32308 KB Output is correct
31 Correct 283 ms 28508 KB Output is correct
32 Correct 325 ms 28076 KB Output is correct
33 Correct 361 ms 28136 KB Output is correct
34 Correct 375 ms 30052 KB Output is correct
35 Correct 395 ms 32836 KB Output is correct
36 Correct 370 ms 30160 KB Output is correct