oj.uz

Submission #761553

# Submission time Handle Problem Language Result Execution time Memory
761553 2023-06-20T01:56:47 Z MetalPower Valley (BOI19_valley) C++14
100 / 100
 196 ms 51936 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<ll, ll>
#define fi first
#define se second

const ll MX = 1e5 + 10;
const ll LG = 19;
const ll INF = 1e18 + 7;

ll N, S, Q, E, dep[MX], in[MX], out[MX], tim = 0;
ll isShop[MX], dist[MX], sp[MX][LG], wt[MX][LG];
vector<pii> adj[MX];

void chmin(ll& a, ll b){
	if(b < a) a = b;
}

void dfs(ll u, ll v){
	in[u] = ++tim;
	if(isShop[u]) dist[u] = 0;
	for(pii nxt : adj[u]){
		if(nxt.fi == v) continue;
		dep[nxt.fi] = dep[u] + nxt.se;
		dfs(nxt.fi, u);
		chmin(dist[u], dist[nxt.fi] + nxt.se);
	}
	out[u] = tim;
}

void dfs2(ll u, ll v){
	if(dist[u] != INF) dist[u] -= dep[u];
	sp[u][0] = v; wt[u][0] = dist[u];
	for(ll j = 1; j < LG; j++){
		sp[u][j] = sp[sp[u][j - 1]][j - 1];
		wt[u][j] = min(wt[u][j - 1], wt[sp[u][j - 1]][j - 1]);
	}
	for(pii nxt : adj[u]){
		if(nxt.fi == v) continue;
		dfs2(nxt.fi, u);
	}
}

void init(){
	for(ll i = 1; i <= N; i++) dist[i] = INF;
	for(ll j = 0; j < LG; j++) sp[0][j] = 0, wt[0][j] = INF;
}

vector<pii> edges;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> N >> S >> Q >> E;
	for(ll i = 1; i < N; i++){
		ll u, v, w; cin >> u >> v >> w;
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
		edges.push_back({u, v});
	}

	for(ll i = 1; i <= S; i++){
		ll C; cin >> C;
		isShop[C] = true;
	}

	init();
	dfs(E, 0);
	dfs2(E, 0);

	for(ll i = 0; i < Q; i++){
		ll I, R, tp, lw; cin >> I >> R; I--;
		if(dep[edges[I].fi] < dep[edges[I].se]) tp = edges[I].fi, lw = edges[I].se;
		else tp = edges[I].se, lw = edges[I].fi;

		if(in[lw] <= in[R] && in[R] <= out[lw]){ // contained

			ll curr = R, ans = INF;
			for(ll j = LG - 1; j >= 0; j--){
				if(dep[sp[curr][j]] > dep[lw]){
					chmin(ans, wt[curr][j]);
					curr = sp[curr][j];
				}
			}

			chmin(ans, wt[curr][0]);
			curr = sp[curr][0];
			chmin(ans, dist[lw]);

			if(ans == INF) cout << "oo\n";
			else cout << dep[R] + ans << '\n';

		}else{
			cout << "escaped\n";
		}
	}
}

Compilation message

valley.cpp: In function 'int main()':
valley.cpp:74:12: warning: variable 'tp' set but not used [-Wunused-but-set-variable]
   74 |   ll I, R, tp, lw; cin >> I >> R; I--;
      |            ^~

Subtask #1
9.0 / 9.0

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

Subtask #2
27.0 / 27.0

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

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 43600 KB Output is correct
2 Correct 132 ms 47356 KB Output is correct
3 Correct 158 ms 47576 KB Output is correct
4 Correct 166 ms 49468 KB Output is correct
5 Correct 149 ms 49540 KB Output is correct
6 Correct 196 ms 51792 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2772 KB Output is correct
2 Correct 3 ms 2772 KB Output is correct
3 Correct 3 ms 2820 KB Output is correct
4 Correct 5 ms 2772 KB Output is correct
5 Correct 2 ms 3156 KB Output is correct
6 Correct 3 ms 3208 KB Output is correct
7 Correct 3 ms 3156 KB Output is correct
8 Correct 2 ms 3156 KB Output is correct
9 Correct 2 ms 3156 KB Output is correct
10 Correct 2 ms 3156 KB Output is correct
11 Correct 2 ms 3080 KB Output is correct
12 Correct 2 ms 3156 KB Output is correct
13 Correct 2 ms 3076 KB Output is correct
14 Correct 2 ms 3156 KB Output is correct
15 Correct 121 ms 43600 KB Output is correct
16 Correct 132 ms 47356 KB Output is correct
17 Correct 158 ms 47576 KB Output is correct
18 Correct 166 ms 49468 KB Output is correct
19 Correct 149 ms 49540 KB Output is correct
20 Correct 196 ms 51792 KB Output is correct
21 Correct 113 ms 46220 KB Output is correct
22 Correct 127 ms 46024 KB Output is correct
23 Correct 147 ms 46260 KB Output is correct
24 Correct 163 ms 48312 KB Output is correct
25 Correct 173 ms 51388 KB Output is correct
26 Correct 115 ms 46508 KB Output is correct
27 Correct 123 ms 46316 KB Output is correct
28 Correct 134 ms 46584 KB Output is correct
29 Correct 155 ms 47984 KB Output is correct
30 Correct 169 ms 49596 KB Output is correct
31 Correct 133 ms 47152 KB Output is correct
32 Correct 129 ms 46948 KB Output is correct
33 Correct 142 ms 47196 KB Output is correct
34 Correct 168 ms 49100 KB Output is correct
35 Correct 163 ms 51936 KB Output is correct
36 Correct 150 ms 49100 KB Output is correct