oj.uz

Submission #470806

# Submission time Handle Problem Language Result Execution time Memory
470806 2021-09-05T17:27:39 Z wind_reaper Valley (BOI19_valley) C++17
100 / 100
 266 ms 38080 KB 
#include <bits/stdc++.h>
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
*/

using namespace std;
// using namespace __gnu_pbds;
using namespace chrono;

// mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());
/*
template <class T> using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
*/

//***************** CONSTANTS *****************

const int MXN = 100000;
const int K = 17;
const int64_t INF = 1000000000000000000;

//***************** GLOBAL VARIABLES *****************

vector<array<int, 2>> g[MXN];
int N, S, Q, root;
int up[K][MXN], tin[MXN], tout[MXN], timer;
int64_t s[MXN], D[MXN], mn[K][MXN];
array<int, 2> e[MXN];

//***************** AUXILIARY STRUCTS *****************

void dfs(int u, int p, int64_t d){
	tin[u] = timer++;
	D[u] = d;
	for(auto& [v, w] : g[u]) if(v != p){
		dfs(v, u, d + w);
		s[u] = min(s[u], s[v] + w);
	}
	tout[u] = timer++;
}
	
void calc(int u, int p){
	up[0][u] = p;
	mn[0][u] = min(s[u] - D[u], s[p] - D[p]);

	for(int i = 1; i < K; 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& [v, w] : g[u]) if(v != p){
		calc(v, u);
	}
}

inline bool is_ancestor(int u, int k, int v){
	u = up[k][u];
	return tin[u] <= tin[v] && tout[u] >= tout[v];
}

//***************** MAIN BODY *****************

void solve(){
	cin >> N >> S >> Q >> root;
	--root;

	for(int i = 0; i < N - 1; i++){
		int u, v, w;
		cin >> u >> v >> w;
		--u, --v;
		g[u].push_back({v, w});
		g[v].push_back({u, w});
		e[i] = {u, v};
	}

	fill(s, s + N, INF);

	for(int i = 0; i < S; i++){
		int u;
		cin >> u;
		--u;
		s[u] = 0;
	}

	dfs(root, root, 0);
	calc(root, root);

	for(int _ = 0; _ < Q; _++){
		int x, u;
		cin >> x >> u;
		--x, --u;

		if(tin[e[x][0]] > tin[e[x][1]])
			swap(e[x][0], e[x][1]);

		x = e[x][1];
		if(tin[x] <= tin[u] && tout[x] >= tout[u]){
			int64_t ans = s[u] - D[u];
			int y = u;
			for(int i = K - 1; i >= 0; --i)
				if(!is_ancestor(u, i, x)){
					ans = min(ans, mn[i][u]);
					u = up[i][u];
				}

			ans = min(ans, s[x] - D[x]);

			if(ans + D[y] >= INF / 2) cout << "oo\n";
			else cout << ans + D[y] << '\n'; 
		}
		else cout << "escaped\n";
	}
}

//***************** *****************

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

	#ifdef LOCAL
		auto begin = high_resolution_clock::now();
	#endif

	int tc = 1;
	// cin >> tc; 
	for (int t = 0; t < tc; t++)
		solve();

	#ifdef LOCAL 
		auto end = high_resolution_clock::now();
		cout << fixed << setprecision(4);
		cout << "Execution Time: " << duration_cast<duration<double>>(end - begin).count() << "seconds" << endl;
	#endif

	return 0;
}

/*
If code gives a WA, check for the following : 
1. I/O format

2. Are you clearing all global variables in between tests if multitests are a thing

3. Can you definitively prove the logic

4. If the code gives an inexplicable TLE, and you are sure you have the best possible complexity,
use faster io
*/

Subtask #1
9.0 / 9.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2892 KB Output is correct
2 Correct 5 ms 3020 KB Output is correct
3 Correct 4 ms 3020 KB Output is correct
4 Correct 5 ms 2892 KB Output is correct
5 Correct 3 ms 3148 KB Output is correct
6 Correct 3 ms 3148 KB Output is correct
7 Correct 3 ms 3148 KB Output is correct
8 Correct 3 ms 3148 KB Output is correct
9 Correct 3 ms 3148 KB Output is correct
10 Correct 3 ms 3148 KB Output is correct
11 Correct 3 ms 3148 KB Output is correct
12 Correct 3 ms 3148 KB Output is correct
13 Correct 3 ms 3148 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 201 ms 30252 KB Output is correct
2 Correct 195 ms 33848 KB Output is correct
3 Correct 198 ms 33736 KB Output is correct
4 Correct 262 ms 35564 KB Output is correct
5 Correct 203 ms 35656 KB Output is correct
6 Correct 266 ms 37484 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2892 KB Output is correct
2 Correct 5 ms 3020 KB Output is correct
3 Correct 4 ms 3020 KB Output is correct
4 Correct 5 ms 2892 KB Output is correct
5 Correct 3 ms 3148 KB Output is correct
6 Correct 3 ms 3148 KB Output is correct
7 Correct 3 ms 3148 KB Output is correct
8 Correct 3 ms 3148 KB Output is correct
9 Correct 3 ms 3148 KB Output is correct
10 Correct 3 ms 3148 KB Output is correct
11 Correct 3 ms 3148 KB Output is correct
12 Correct 3 ms 3148 KB Output is correct
13 Correct 3 ms 3148 KB Output is correct
14 Correct 3 ms 3148 KB Output is correct
15 Correct 201 ms 30252 KB Output is correct
16 Correct 195 ms 33848 KB Output is correct
17 Correct 198 ms 33736 KB Output is correct
18 Correct 262 ms 35564 KB Output is correct
19 Correct 203 ms 35656 KB Output is correct
20 Correct 266 ms 37484 KB Output is correct
21 Correct 170 ms 33572 KB Output is correct
22 Correct 184 ms 33204 KB Output is correct
23 Correct 213 ms 33264 KB Output is correct
24 Correct 235 ms 35216 KB Output is correct
25 Correct 232 ms 38080 KB Output is correct
26 Correct 192 ms 33656 KB Output is correct
27 Correct 197 ms 33288 KB Output is correct
28 Correct 192 ms 33192 KB Output is correct
29 Correct 248 ms 34692 KB Output is correct
30 Correct 244 ms 36020 KB Output is correct
31 Correct 200 ms 33708 KB Output is correct
32 Correct 217 ms 33360 KB Output is correct
33 Correct 229 ms 33412 KB Output is correct
34 Correct 266 ms 35116 KB Output is correct
35 Correct 227 ms 37956 KB Output is correct
36 Correct 229 ms 35264 KB Output is correct