oj.uz

Submission #784118

# Submission time Handle Problem Language Result Execution time Memory
784118 2023-07-15T17:49:05 Z raysh07 Valley (BOI19_valley) C++17
100 / 100
 144 ms 53712 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

int n, s, q, r;
const int N = 1e5 + 69;
vector <pair<int, int>> adj[N];
int dp[N], l1[N][20], l2[N][20], tin[N], tout[N], d[N], ok1[N], timer = 0;
bool ok[N];

void dfs(int u, int p){
	dp[u] = INF;
	tin[u] = ++timer;
	if (ok[u]) dp[u] = 0;
	for (auto [v, w] : adj[u]){
		if (v != p){
			l2[v][0] = u;
			d[v] = d[u] + w;
			ok1[v] = ok1[u] + 1;
			dfs(v, u);
			dp[u] = min(dp[u], dp[v] + w);
		}
	}
	tout[u] = timer;
}

void Solve()
{
	cin >> n >> s >> q >> r;

	vector <pair<int, int>> e;

	for (int i = 1; i < n; i++){
		int u, v, w; cin >> u >> v >> w;

		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
		e.push_back({u, v});
	}

	while (s--){
		int x; cin >> x;
		ok[x] = true;
	}

	dfs(r, -1);

	for (int i = 1; i <= n; i++){
		l1[i][0] = dp[i];
	}

	for (int j = 1; j < 20; j++){
		for (int i = 1; i <= n; i++){
			l2[i][j] = l2[l2[i][j - 1]][j - 1];
			int x = l2[i][j - 1];
			if (x == 0) continue;

			l1[i][j] = min(l1[i][j - 1], l1[x][j - 1] + d[i] - d[x]);
		}
	}

	while (q--){
		int id, x; cin >> id >> x;

		--id;
		if (d[e[id].first] < d[e[id].second]) swap(e[id].first, e[id].second);

		int u = e[id].first;
		int v = e[id].second;

		if (tin[u] <= tin[x] && tout[u] >= tout[x]){
			int ans = INF;
			int add = 0;

			int lol = ok1[x] - ok1[v];
		//	cout << lol << "\n";

			for (int i = 0; i < 20; i++){
				if (lol >> i & 1){
					ans = min(ans, add + l1[x][i]);
					add += d[x] - d[l2[x][i]];
					x = l2[x][i];
				}
			}

			if (ans == INF) cout << "oo\n";
			else cout << ans << "\n";
		} else {
			cout << "escaped\n";
		}
	}
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;

   // freopen("in",  "r", stdin);
   // freopen("out", "w", stdout);

  //  cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
27.0 / 27.0

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

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 49268 KB Output is correct
2 Correct 110 ms 48968 KB Output is correct
3 Correct 119 ms 49256 KB Output is correct
4 Correct 136 ms 51140 KB Output is correct
5 Correct 126 ms 51176 KB Output is correct
6 Correct 144 ms 53388 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2824 KB Output is correct
2 Correct 3 ms 2820 KB Output is correct
3 Correct 3 ms 2900 KB Output is correct
4 Correct 3 ms 2820 KB Output is correct
5 Correct 2 ms 3076 KB Output is correct
6 Correct 2 ms 3156 KB Output is correct
7 Correct 2 ms 3156 KB Output is correct
8 Correct 2 ms 3080 KB Output is correct
9 Correct 3 ms 3156 KB Output is correct
10 Correct 2 ms 3156 KB Output is correct
11 Correct 2 ms 3156 KB Output is correct
12 Correct 3 ms 3080 KB Output is correct
13 Correct 2 ms 3156 KB Output is correct
14 Correct 3 ms 3144 KB Output is correct
15 Correct 122 ms 49268 KB Output is correct
16 Correct 110 ms 48968 KB Output is correct
17 Correct 119 ms 49256 KB Output is correct
18 Correct 136 ms 51140 KB Output is correct
19 Correct 126 ms 51176 KB Output is correct
20 Correct 144 ms 53388 KB Output is correct
21 Correct 95 ms 48520 KB Output is correct
22 Correct 106 ms 48324 KB Output is correct
23 Correct 116 ms 48540 KB Output is correct
24 Correct 130 ms 50660 KB Output is correct
25 Correct 140 ms 53712 KB Output is correct
26 Correct 98 ms 48608 KB Output is correct
27 Correct 102 ms 48420 KB Output is correct
28 Correct 114 ms 48676 KB Output is correct
29 Correct 133 ms 50216 KB Output is correct
30 Correct 141 ms 51768 KB Output is correct
31 Correct 101 ms 48780 KB Output is correct
32 Correct 111 ms 48568 KB Output is correct
33 Correct 116 ms 48880 KB Output is correct
34 Correct 134 ms 50696 KB Output is correct
35 Correct 138 ms 53684 KB Output is correct
36 Correct 125 ms 50668 KB Output is correct