oj.uz

Submission #729274

# Submission time Handle Problem Language Result Execution time Memory
729274 2023-04-23T17:57:03 Z WonderfulWhale Valley (BOI19_valley) C++17
100 / 100
 240 ms 53784 KB 
#include<bits/stdc++.h>
using namespace std;

#define int int64_t
#define pb push_back
#define st first
#define nd second
#define pii pair<int, int>
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()

int n, s, q, e;

vector<pii> G[100009];
bool shop[100009];
int shop_dis[100009];
int dep[100009];
int val[100009];
int tin[100009], tout[100009], T;
pii jp2[100009][20];

int dis(int x, int y) {
	return abs(dep[x]-dep[y]);
}

void dfs(int x, int y) {
	tin[x] = ++T;
	shop_dis[x] = 1e18;
	if(shop[x]) shop_dis[x] = 0;
	for(auto [z, d]:G[x]) {
		if(z==y) continue;
		dep[z] = dep[x] + d;
		dfs(z, x);
		shop_dis[x] = min(shop_dis[x], shop_dis[z]+d);
	}
	val[x] = shop_dis[x]-dis(x, e);
	tout[x] = ++T;
}

void dfs2(int x, int y) {
	jp2[x][0] = {y, val[y]};
	for(int i=1;i<20;i++) {
		jp2[x][i].st = jp2[jp2[x][i-1].st][i-1].st;
		jp2[x][i].nd = min(jp2[x][i-1].nd, jp2[jp2[x][i-1].st][i-1].nd);
	}
	for(auto [z, d]:G[x]) {
		if(z!=y) dfs2(z, x);
	}
}

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

int solve(int a, int b) {
	if(a==b) return val[a];
	int ans = val[a];
	for(int i=19;i>=0;i--) {
		if(!is_ancestor(jp2[a][i].st, b)) {
			ans = min(ans, jp2[a][i].nd);
			a = jp2[a][i].st;
		}
	}
	ans = min(ans, jp2[a][0].nd);
	return ans;
}

vector<pii> edges;

int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> s >> q >> e;
	for(int i=0;i<n-1;i++) {
		int a, b, c;
		cin >> a >> b >> c;
		edges.pb({a, b});
		G[a].pb({b, c});
		G[b].pb({a, c});
	}
	for(int i=0;i<s;i++) {
		int x;
		cin >> x;
		shop[x] = true;
	}
	dfs(e, 0);
	tout[0] = ++T;
	val[e] = 1e18;
	dfs2(e, 0);
	for(int i=0;i<q;i++) {
		int x, a;
		cin >> x >> a;
		x--;
		int b = edges[x].nd;
		if(dep[edges[x].st]>dep[edges[x].nd]) b = edges[x].st;
		if(a!=b&&!is_ancestor(b, a)) {
			cout << "escaped\n";
			continue;
		}
		int ans = solve(a, b);
		if(ans>1e17) {
			cout << "oo\n";
		} else {
			cout << ans+dis(a, e) << "\n";
		}
	}
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2772 KB Output is correct
2 Correct 4 ms 2900 KB Output is correct
3 Correct 4 ms 2900 KB Output is correct
4 Correct 4 ms 2820 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2772 KB Output is correct
2 Correct 4 ms 2900 KB Output is correct
3 Correct 4 ms 2900 KB Output is correct
4 Correct 4 ms 2820 KB Output is correct
5 Correct 2 ms 3156 KB Output is correct
6 Correct 3 ms 3156 KB Output is correct
7 Correct 2 ms 3156 KB Output is correct
8 Correct 2 ms 3132 KB Output is correct
9 Correct 3 ms 3076 KB Output is correct
10 Correct 3 ms 3108 KB Output is correct
11 Correct 3 ms 3156 KB Output is correct
12 Correct 2 ms 3076 KB Output is correct
13 Correct 3 ms 3148 KB Output is correct
14 Correct 3 ms 3068 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 49208 KB Output is correct
2 Correct 163 ms 49020 KB Output is correct
3 Correct 190 ms 49328 KB Output is correct
4 Correct 213 ms 51108 KB Output is correct
5 Correct 198 ms 51256 KB Output is correct
6 Correct 240 ms 53432 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2772 KB Output is correct
2 Correct 4 ms 2900 KB Output is correct
3 Correct 4 ms 2900 KB Output is correct
4 Correct 4 ms 2820 KB Output is correct
5 Correct 2 ms 3156 KB Output is correct
6 Correct 3 ms 3156 KB Output is correct
7 Correct 2 ms 3156 KB Output is correct
8 Correct 2 ms 3132 KB Output is correct
9 Correct 3 ms 3076 KB Output is correct
10 Correct 3 ms 3108 KB Output is correct
11 Correct 3 ms 3156 KB Output is correct
12 Correct 2 ms 3076 KB Output is correct
13 Correct 3 ms 3148 KB Output is correct
14 Correct 3 ms 3068 KB Output is correct
15 Correct 150 ms 49208 KB Output is correct
16 Correct 163 ms 49020 KB Output is correct
17 Correct 190 ms 49328 KB Output is correct
18 Correct 213 ms 51108 KB Output is correct
19 Correct 198 ms 51256 KB Output is correct
20 Correct 240 ms 53432 KB Output is correct
21 Correct 153 ms 48544 KB Output is correct
22 Correct 156 ms 48348 KB Output is correct
23 Correct 164 ms 48568 KB Output is correct
24 Correct 228 ms 50656 KB Output is correct
25 Correct 211 ms 53736 KB Output is correct
26 Correct 135 ms 48692 KB Output is correct
27 Correct 173 ms 48452 KB Output is correct
28 Correct 176 ms 48712 KB Output is correct
29 Correct 220 ms 50140 KB Output is correct
30 Correct 211 ms 51800 KB Output is correct
31 Correct 141 ms 48704 KB Output is correct
32 Correct 180 ms 48624 KB Output is correct
33 Correct 162 ms 48836 KB Output is correct
34 Correct 207 ms 50760 KB Output is correct
35 Correct 239 ms 53784 KB Output is correct
36 Correct 197 ms 50636 KB Output is correct