oj.uz

Submission #498155

# Submission time Handle Problem Language Result Execution time Memory
498155 2021-12-24T13:04:36 Z Mukhitali Valley (BOI19_valley) C++17
100 / 100
 227 ms 38652 KB 
//bit chass 1
#include <bits/stdc++.h>

#define x first
#define y second
#define el "\n"
#define ll long long
#define pb push_back
#define pll pair <ll, ll>
#define pii pair <int, int>
#define all(x) x.begin(), x.end()
#define lcm(x,y) x * y / __gcd(x, y)
#define ibase ios_base::sync_with_stdio(0), cin.tie(0)

using namespace std;

const int N = 1e5 + 5, inf = 1e9 + 7, M = 2e5, K = 300;
const ll MI = 2e18, mm = 1e15 + 5;
const double P = 3.14;

int n, s, q, e, p, tim = 1, tin[2 * N], tout[2 * N], up[N][20];
ll dist[N], dp[N], mn[N][20];
bool c[N];
vector <pair <int, int>> g[N];
pair <int, int> ed[N];

void dfs(int v, int pr = 0) {
	tin[v] = tim++;
	if (c[v])
		dp[v] = 0;
	up[v][0] = pr;
	for (int i = 1; i < 20; i++) 
		up[v][i] = up[up[v][i - 1]][i - 1];
	for (auto to : g[v]) {
		if (to.x != pr) {
			dist[to.x] = dist[v] + to.y;
			dfs(to.x, v);
			dp[v] = min(dp[to.x] + to.y, dp[v]);
		}
	}
	tout[v] = tim++;
}

void dfs2(int v, int pr) {
	mn[v][0] = dp[pr] - dist[pr];
	for (int i = 1; i < 20; i++)
		mn[v][i] = min(mn[up[v][i - 1]][i - 1], mn[v][i - 1]);
	for (pii to : g[v])
		if (to.x != pr)
			dfs2(to.x, v);
}

bool upper(int x, int y) {
	return (tin[x] <= tin[y] && tout[y] <= tout[x]);
}

void solve() {
	cin >> n >> s >> q >> e;
	for (int i = 1, x, y, w; i < n; i++) {
		cin >> x >> y >> w;
		g[x].pb({y, w});
		g[y].pb({x, w});
		ed[i] = {x, y};
		dp[i] = dp[i + 1] = mm;
	}
	for (int i = 1; i <= n; i++)
		for (int j = 0; j < 20; j++)
			mn[i][j] = mm;
	for (int i = 1, x; i <= s; i++) {
		cin >> x;
		c[x] = 1;
	}
	dfs(e);
	dfs2(e, 0);
	tout[0] = tim;
	while (q--) {
		int i, r, v;
		cin >> i >> r;
		pii x = ed[i];
		if (upper(x.x, x.y))
			v = x.y;
		else 
			v = x.x;
		if (upper(v, r)) {
			if (v == r) {
				if (dp[v] == mm)
					cout << "oo" << el;
				else
					cout << dp[v] << el;
				continue;
			}
			ll ans = mm, rr = r;
			for (int i = 19; i >= 0; i--) {
				if (upper(v, up[r][i]))
					ans = min(mn[r][i], ans), r = up[r][i];
			}
			if (ans + dist[rr] >= mm && dp[rr] == mm)
				cout << "oo" << el;
			else 	
				cout << min(ans + dist[rr], dp[rr]) << el;
		}
		else {
			cout << "escaped" << el;
		}
		
	}
}

int main() {
	ibase;
	int T = 1;
//	cin >> T;
	for (int i = 1; i <= T; i++) {
//		cout << "Case " << i << ": ";
		solve();
		cout << el;
	}
}

Subtask #1
9.0 / 9.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2764 KB Output is correct
2 Correct 6 ms 2808 KB Output is correct
3 Correct 6 ms 2808 KB Output is correct
4 Correct 5 ms 2808 KB Output is correct
5 Correct 2 ms 2944 KB Output is correct
6 Correct 2 ms 3020 KB Output is correct
7 Correct 3 ms 3020 KB Output is correct
8 Correct 2 ms 2944 KB Output is correct
9 Correct 2 ms 2940 KB Output is correct
10 Correct 2 ms 3020 KB Output is correct
11 Correct 2 ms 2944 KB Output is correct
12 Correct 2 ms 3020 KB Output is correct
13 Correct 2 ms 3020 KB Output is correct
14 Correct 3 ms 3148 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 33908 KB Output is correct
2 Correct 196 ms 33528 KB Output is correct
3 Correct 161 ms 33504 KB Output is correct
4 Correct 226 ms 35268 KB Output is correct
5 Correct 181 ms 35424 KB Output is correct
6 Correct 223 ms 37268 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2764 KB Output is correct
2 Correct 6 ms 2808 KB Output is correct
3 Correct 6 ms 2808 KB Output is correct
4 Correct 5 ms 2808 KB Output is correct
5 Correct 2 ms 2944 KB Output is correct
6 Correct 2 ms 3020 KB Output is correct
7 Correct 3 ms 3020 KB Output is correct
8 Correct 2 ms 2944 KB Output is correct
9 Correct 2 ms 2940 KB Output is correct
10 Correct 2 ms 3020 KB Output is correct
11 Correct 2 ms 2944 KB Output is correct
12 Correct 2 ms 3020 KB Output is correct
13 Correct 2 ms 3020 KB Output is correct
14 Correct 3 ms 3148 KB Output is correct
15 Correct 164 ms 33908 KB Output is correct
16 Correct 196 ms 33528 KB Output is correct
17 Correct 161 ms 33504 KB Output is correct
18 Correct 226 ms 35268 KB Output is correct
19 Correct 181 ms 35424 KB Output is correct
20 Correct 223 ms 37268 KB Output is correct
21 Correct 131 ms 34196 KB Output is correct
22 Correct 181 ms 33928 KB Output is correct
23 Correct 164 ms 33840 KB Output is correct
24 Correct 182 ms 35832 KB Output is correct
25 Correct 214 ms 38652 KB Output is correct
26 Correct 150 ms 34372 KB Output is correct
27 Correct 163 ms 33992 KB Output is correct
28 Correct 197 ms 33976 KB Output is correct
29 Correct 220 ms 35320 KB Output is correct
30 Correct 227 ms 36704 KB Output is correct
31 Correct 147 ms 34364 KB Output is correct
32 Correct 153 ms 33996 KB Output is correct
33 Correct 190 ms 34164 KB Output is correct
34 Correct 215 ms 35856 KB Output is correct
35 Correct 200 ms 38564 KB Output is correct
36 Correct 199 ms 36468 KB Output is correct