oj.uz

Submission #340680

# Submission time Handle Problem Language Result Execution time Memory
340680 2020-12-28T06:46:28 Z 8e7 Valley (BOI19_valley) C++14
100 / 100
 1970 ms 46116 KB 
//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#define maxn 100005
#define ll long long
#define ff first
#define ss second
using namespace std;
const ll inf = 1LL<<60;
vector<pair<int, ll> > adj[maxn];
bool st[maxn];
int lef[maxn], rig[maxn], anc[17][maxn];
ll mind[17][maxn];
struct edge {
	int a, b;
	ll w;
	edge(int x, int y, ll c) {
		a = x, b = y, w = c;
	}
	edge() {
		a = 0, b = 0, w = 0;
	}
};
edge ed[maxn];

ll dep[maxn], d2[maxn], seg[4 * maxn];
void init(int cur, int l, int r) {
	if (r <= l) return;
	if (r - l == 1) {
		seg[cur] = dep[l];
		return;
	}
	int mid = (l + r) / 2;
	init(cur * 2, l, mid), init(cur * 2 + 1, mid, r);
	seg[cur] = min(seg[cur * 2], seg[cur * 2 + 1]);
}
ll query(int cur, int l, int r, int ql, int qr) {
	if (r <= l || qr <= l || ql >= r) return inf;
	if (ql <= l && qr >= r) return seg[cur];
	int mid = (l + r) / 2;
	return min(query(cur * 2, l, mid, ql, qr), query(cur * 2 + 1, mid, r, ql, qr));
}
int cnt = 0;
void dfs(int n, int par, ll dis) {
	lef[n] = cnt;
	dep[cnt] = (st[n] ? dis : inf), d2[n] = dis;
	anc[0][n] = par;
	cnt++;
	for (auto v: adj[n]) {
		if (v.ff != par) {
			dfs(v.ff, n, dis + v.ss);
		}
	}
	rig[n] = cnt; //[l, r)
}
int main() {
	for (int i = 0;i < maxn;i++) mind[0][i] = inf;
	int n, s, q, e;
	cin >> n >> s >> q >> e;
	for (int i = 1;i <= n - 1;i++) {
		int a, b;
		ll w;
		cin >> a >> b >> w;
		ed[i] = edge(a, b, w);
		adj[a].push_back(make_pair(b, w));
		adj[b].push_back(make_pair(a, w));
	}
	for (int i = 0;i < s;i++) {
		int x;
		cin >> x;
		st[x] = 1;
	}
	dfs(e, 0, 1);
	for (int i = 1;i <= n;i++) cerr << lef[i] << " " << d2[i] << endl;
	init(1, 0, n);
	for (int i = 1;i <= n;i++) mind[0][i] = query(1, 0, n, lef[i], rig[i]) - 2 * d2[i], cerr << mind[0][i] << endl;
	for (int i = 1;i < 17;i++) {
		for (int j = 1;j <= n;j++) {
			anc[i][j] = anc[i - 1][anc[i - 1][j]];
			mind[i][j] = min(mind[i - 1][j], mind[i - 1][anc[i - 1][j]]);
		}
	}
	while (q--) {
		int ind, r, sub;
		cin >> ind >> r;
		if (anc[0][ed[ind].a] == ed[ind].b) sub = ed[ind].a;
		else sub = ed[ind].b;
		if (lef[r] >= lef[sub] && lef[r] < rig[sub]) {
			ll ans = inf;
			int cur = r;
			for (int j = 16;j >= 0;j--) {
				if (d2[anc[j][cur]] >= d2[sub]) {
					//cout << j << " " << cur << endl;
					ans = min(ans, d2[r] + mind[j][cur]);
					cur = anc[j][cur];
				}
			}
			ans = min(ans, d2[r] + mind[0][sub]);
			if (ans >= (inf>>1)) cout << "oo" << "\n";
			else cout << ans << "\n";
		} else {
			cout << "escaped\n";
		}
	}
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 5356 KB Output is correct
2 Correct 33 ms 5484 KB Output is correct
3 Correct 32 ms 5356 KB Output is correct
4 Correct 32 ms 5356 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 5356 KB Output is correct
2 Correct 33 ms 5484 KB Output is correct
3 Correct 32 ms 5356 KB Output is correct
4 Correct 32 ms 5356 KB Output is correct
5 Correct 20 ms 5612 KB Output is correct
6 Correct 21 ms 5632 KB Output is correct
7 Correct 21 ms 5624 KB Output is correct
8 Correct 21 ms 5612 KB Output is correct
9 Correct 21 ms 5612 KB Output is correct
10 Correct 21 ms 5612 KB Output is correct
11 Correct 21 ms 5612 KB Output is correct
12 Correct 21 ms 5612 KB Output is correct
13 Correct 23 ms 5612 KB Output is correct
14 Correct 21 ms 5612 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1872 ms 41256 KB Output is correct
2 Correct 1874 ms 41196 KB Output is correct
3 Correct 1917 ms 41620 KB Output is correct
4 Correct 1917 ms 43372 KB Output is correct
5 Correct 1890 ms 43892 KB Output is correct
6 Correct 1970 ms 45420 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 5356 KB Output is correct
2 Correct 33 ms 5484 KB Output is correct
3 Correct 32 ms 5356 KB Output is correct
4 Correct 32 ms 5356 KB Output is correct
5 Correct 20 ms 5612 KB Output is correct
6 Correct 21 ms 5632 KB Output is correct
7 Correct 21 ms 5624 KB Output is correct
8 Correct 21 ms 5612 KB Output is correct
9 Correct 21 ms 5612 KB Output is correct
10 Correct 21 ms 5612 KB Output is correct
11 Correct 21 ms 5612 KB Output is correct
12 Correct 21 ms 5612 KB Output is correct
13 Correct 23 ms 5612 KB Output is correct
14 Correct 21 ms 5612 KB Output is correct
15 Correct 1872 ms 41256 KB Output is correct
16 Correct 1874 ms 41196 KB Output is correct
17 Correct 1917 ms 41620 KB Output is correct
18 Correct 1917 ms 43372 KB Output is correct
19 Correct 1890 ms 43892 KB Output is correct
20 Correct 1970 ms 45420 KB Output is correct
21 Correct 1853 ms 41580 KB Output is correct
22 Correct 1886 ms 41324 KB Output is correct
23 Correct 1865 ms 41708 KB Output is correct
24 Correct 1898 ms 43500 KB Output is correct
25 Correct 1898 ms 46116 KB Output is correct
26 Correct 1851 ms 41608 KB Output is correct
27 Correct 1871 ms 41480 KB Output is correct
28 Correct 1912 ms 41676 KB Output is correct
29 Correct 1903 ms 42956 KB Output is correct
30 Correct 1908 ms 44140 KB Output is correct
31 Correct 1842 ms 41708 KB Output is correct
32 Correct 1852 ms 41452 KB Output is correct
33 Correct 1885 ms 41964 KB Output is correct
34 Correct 1931 ms 43372 KB Output is correct
35 Correct 1901 ms 45676 KB Output is correct
36 Correct 1868 ms 42440 KB Output is correct