oj.uz

Submission #504005

# Submission time Handle Problem Language Result Execution time Memory
504005 2022-01-09T12:54:58 Z Meloric Valley (BOI19_valley) C++17
100 / 100
 357 ms 69912 KB 
#include <bits/stdc++.h>
#define pb push_back
#define int int64_t
#define pii pair<int, int>
#define X first
#define Y second
#define all(x) (x).begin(),(x).end()

using namespace std;

const int inf  = 1e18;

int n, s, q, root;

int timer = 0;

struct edge{
	int id, v, w;
};

vector<vector<edge>> g;
vector<int> shops, down, lvl, val, mp, pre, pst;
vector<vector<int>> up, mn;

void p(vector<int>& A){
	for(auto e : A)cout << e << ' ';
	cout << '\n';
}

void dfs1(int u, int p){
	for(auto [id, v, w] : g[u]){
		if(v == p)continue;
		mp[id] = v;
		lvl[v] = lvl[u] + w;
		dfs1(v, u);
	}
	if(shops[u])down[u] = 0;
	for(auto [id, v, w] : g[u]){
		if(v == p)continue;
		down[u] = min(down[u], down[v] + w);
	}
	val[u] = down[u] - lvl[u];
}

void dfs2(int u, int p){
	pre[u] = timer++;
	up[0][u] = p;
	mn[0][u] = min(val[u], val[up[0][u]]);
	for(int i = 1; i< 30; i++){
		up[i][u] = up[i-1][up[i-1][u]];
		mn[i][u] = min(mn[i-1][u], mn[i-1][up[i-1][u]]);
	}
	for(auto [id, v, w] : g[u]){
		if(v == p)continue;
		dfs2(v, u);
	}
	pst[u] = timer++;
}

int is_anc(int u, int a){
	return pre[u] >= pre[a] && pst[u] <= pst[a];
}

	
void solve(){
	cin >> n >> s >> q >> root; root--;
	mp.assign(n-1, 0);
	g.assign(n, vector<edge>());
	shops.assign(n, 0);
	down.assign(n, inf);
	lvl.assign(n, 0);
	val.assign(n, 0);
	pre.assign(n, 0);
	pst.assign(n, 0);
	
	up.assign(30, vector<int>(n));
	mn.assign(30, vector<int>(n, inf));
	
	for(int i = 0; i< n-1; i++){
		int a, b, w; cin >> a >> b >> w; a--; b--;
		g[a].pb({i, b, w});
		g[b].pb({i, a, w});
	}
	for(int i = 0; i< s; i++){
		int c; cin >> c; c--;
		shops[c] = 1;
	}
	dfs1(root, root);
	dfs2(root, root);
	
	//p(mp); p(pre); p(pst);
	
	for(int i = 0; i< q; i++){
		int id, r; cin >> id >> r; id--; r--;
		//cerr << "NODE: " << mp[id] << '\n';
		if(!is_anc(r, mp[id])){
			cout << "escaped\n";
			continue;
		}
		int start = r;
		int ans = val[r];
		for(int j = 29; j>= 0; j--){
			if(is_anc(up[j][r], mp[id])){
				ans = min(ans, mn[j][r]);
				r = up[j][r];
			}
		}
		ans += lvl[start];
		if(ans == 1e18){
			cout << "oo\n";
			continue;
		}else{
			cout << ans << '\n';
		}
	}
}

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

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 460 KB Output is correct
2 Correct 3 ms 436 KB Output is correct
3 Correct 2 ms 452 KB Output is correct
4 Correct 2 ms 460 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 460 KB Output is correct
2 Correct 3 ms 436 KB Output is correct
3 Correct 2 ms 452 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 2 ms 960 KB Output is correct
6 Correct 2 ms 896 KB Output is correct
7 Correct 2 ms 972 KB Output is correct
8 Correct 2 ms 844 KB Output is correct
9 Correct 2 ms 960 KB Output is correct
10 Correct 2 ms 972 KB Output is correct
11 Correct 2 ms 844 KB Output is correct
12 Correct 2 ms 972 KB Output is correct
13 Correct 1 ms 972 KB Output is correct
14 Correct 2 ms 968 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 64276 KB Output is correct
2 Correct 256 ms 66056 KB Output is correct
3 Correct 271 ms 66300 KB Output is correct
4 Correct 303 ms 67792 KB Output is correct
5 Correct 290 ms 67880 KB Output is correct
6 Correct 357 ms 69560 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 460 KB Output is correct
2 Correct 3 ms 436 KB Output is correct
3 Correct 2 ms 452 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 2 ms 960 KB Output is correct
6 Correct 2 ms 896 KB Output is correct
7 Correct 2 ms 972 KB Output is correct
8 Correct 2 ms 844 KB Output is correct
9 Correct 2 ms 960 KB Output is correct
10 Correct 2 ms 972 KB Output is correct
11 Correct 2 ms 844 KB Output is correct
12 Correct 2 ms 972 KB Output is correct
13 Correct 1 ms 972 KB Output is correct
14 Correct 2 ms 968 KB Output is correct
15 Correct 242 ms 64276 KB Output is correct
16 Correct 256 ms 66056 KB Output is correct
17 Correct 271 ms 66300 KB Output is correct
18 Correct 303 ms 67792 KB Output is correct
19 Correct 290 ms 67880 KB Output is correct
20 Correct 357 ms 69560 KB Output is correct
21 Correct 235 ms 65440 KB Output is correct
22 Correct 269 ms 65444 KB Output is correct
23 Correct 251 ms 65672 KB Output is correct
24 Correct 322 ms 67488 KB Output is correct
25 Correct 323 ms 69912 KB Output is correct
26 Correct 249 ms 65480 KB Output is correct
27 Correct 236 ms 65472 KB Output is correct
28 Correct 286 ms 65708 KB Output is correct
29 Correct 293 ms 67004 KB Output is correct
30 Correct 349 ms 68388 KB Output is correct
31 Correct 224 ms 65536 KB Output is correct
32 Correct 249 ms 65548 KB Output is correct
33 Correct 277 ms 65948 KB Output is correct
34 Correct 346 ms 67688 KB Output is correct
35 Correct 322 ms 69816 KB Output is correct
36 Correct 286 ms 67552 KB Output is correct