oj.uz

Submission #730734

# Submission time Handle Problem Language Result Execution time Memory
730734 2023-04-26T10:39:04 Z gagik_2007 Valley (BOI19_valley) C++17
100 / 100
 282 ms 60364 KB 
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <chrono>
#include <ctime>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <limits>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <fstream>
#include <functional>
#include <random>
#include <cassert>
#include <bitset>
using namespace std;

typedef long long ll;
typedef long double ld;

#pragma GCC optimize("Ofast")

#define ff first
#define ss second

ll ttt;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const ll N = 100007;
const ll LG = 21;
ll n, m, k;
vector<pair<int, ll>>g[N];
int up[N][LG];
ll dist[N][LG]; // the distance between v and up[v][i]
ll dp[N][LG]; // the distance to the closest marked node to v in the subtree of up[v][i]
int tin[N], tout[N];
ll st[N]; // dp for v's subtree
int timer = 0;
bool marked[N];
int lft[N], rgh[N];

void dfs(int v, int par, ll w) {
	tin[v] = timer++;
	up[v][0] = par;
	dist[v][0] = w;
	st[v] = INF;
	if (marked[v]) {
		st[v] = 0;
	}
	for (auto e : g[v]) {
		int to = e.ff;
		ll d = e.ss;
		if (to != par) {
			dfs(to, v, d);
			st[v] = min(st[v], st[to] + d);
		}
	}
	tout[v] = timer++;
}

void precalc(int root) {
	dfs(root, root, 0);
	for (int v = 1; v <= n; v++) {
		dp[v][0] = min(st[up[v][0]] + dist[v][0], st[v]);
	}
	for (int i = 1; i < LG; i++) {
		for (int v = 1; v <= n; v++) {
			up[v][i] = up[up[v][i - 1]][i - 1];
			dist[v][i] = dist[v][i - 1] + dist[up[v][i - 1]][i - 1];
			dp[v][i] = min(dp[v][i - 1], dp[up[v][i - 1]][i - 1] + dist[v][i - 1]);
		}
	}
}

bool is_papa(int v, int u) {
	return (tin[v] <= tin[u] && tout[v] >= tout[u]);
}

ll get_ans(int v, int u) {
	if (v == u) {
		return st[v];
	}
	ll cur_dist = 0;
	ll cur_ans = INF;
	for (int i = LG - 1; i >= 0; i--) {
		if (!is_papa(up[v][i], u)) {
			cur_ans = min(cur_ans, cur_dist + dp[v][i]);
			cur_dist += dist[v][i];
			v = up[v][i];
		}
	}
	cur_ans = min(cur_ans, cur_dist + dp[v][0]);
	return cur_ans;
}

int get_lower(int e) {
	if (is_papa(lft[e], rgh[e]))return rgh[e];
	return lft[e];
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int root;
	cin >> n >> k >> m >> root;
	for (int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		ll w;
		cin >> w;
		g[x].push_back({ y,w });
		g[y].push_back({ x,w });
		lft[i] = x;
		rgh[i] = y;
	}
	for (int i = 0; i < k; i++) {
		int v;
		cin >> v;
		marked[v] = true;
	}
	precalc(root);
	for (int i = 0; i < m; i++) {
		int e, v;
		cin >> e >> v;
		int u = get_lower(e);
		if (!is_papa(u, v)) {
			cout << "escaped\n";
		}
		else {
			ll vl = get_ans(v, u);
			if (vl >= INF) {
				cout << "oo" << endl;
			}
			else {
				cout << vl << endl;
			}
		}
	}
}

/// ---- - --------  ------ -------- -- - - -
/// Just a reminder. Ubuntu password is I O I
/// ---- - --------  ------ -------- -- - - -

Subtask #1
9.0 / 9.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 2772 KB Output is correct
2 Correct 9 ms 2816 KB Output is correct
3 Correct 7 ms 2900 KB Output is correct
4 Correct 8 ms 2820 KB Output is correct
5 Correct 4 ms 3224 KB Output is correct
6 Correct 3 ms 3156 KB Output is correct
7 Correct 3 ms 3204 KB Output is correct
8 Correct 3 ms 3200 KB Output is correct
9 Correct 3 ms 3156 KB Output is correct
10 Correct 3 ms 3156 KB Output is correct
11 Correct 4 ms 3156 KB Output is correct
12 Correct 4 ms 3156 KB Output is correct
13 Correct 3 ms 3204 KB Output is correct
14 Correct 3 ms 3196 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 55760 KB Output is correct
2 Correct 238 ms 55608 KB Output is correct
3 Correct 280 ms 56040 KB Output is correct
4 Correct 282 ms 57732 KB Output is correct
5 Correct 190 ms 57896 KB Output is correct
6 Correct 269 ms 59980 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 2772 KB Output is correct
2 Correct 9 ms 2816 KB Output is correct
3 Correct 7 ms 2900 KB Output is correct
4 Correct 8 ms 2820 KB Output is correct
5 Correct 4 ms 3224 KB Output is correct
6 Correct 3 ms 3156 KB Output is correct
7 Correct 3 ms 3204 KB Output is correct
8 Correct 3 ms 3200 KB Output is correct
9 Correct 3 ms 3156 KB Output is correct
10 Correct 3 ms 3156 KB Output is correct
11 Correct 4 ms 3156 KB Output is correct
12 Correct 4 ms 3156 KB Output is correct
13 Correct 3 ms 3204 KB Output is correct
14 Correct 3 ms 3196 KB Output is correct
15 Correct 238 ms 55760 KB Output is correct
16 Correct 238 ms 55608 KB Output is correct
17 Correct 280 ms 56040 KB Output is correct
18 Correct 282 ms 57732 KB Output is correct
19 Correct 190 ms 57896 KB Output is correct
20 Correct 269 ms 59980 KB Output is correct
21 Correct 222 ms 55196 KB Output is correct
22 Correct 239 ms 54964 KB Output is correct
23 Correct 249 ms 55248 KB Output is correct
24 Correct 279 ms 57448 KB Output is correct
25 Correct 242 ms 60364 KB Output is correct
26 Correct 216 ms 55244 KB Output is correct
27 Correct 228 ms 55116 KB Output is correct
28 Correct 253 ms 55360 KB Output is correct
29 Correct 282 ms 56856 KB Output is correct
30 Correct 267 ms 58400 KB Output is correct
31 Correct 229 ms 55312 KB Output is correct
32 Correct 264 ms 55280 KB Output is correct
33 Correct 254 ms 55580 KB Output is correct
34 Correct 280 ms 57548 KB Output is correct
35 Correct 249 ms 60328 KB Output is correct
36 Correct 233 ms 57268 KB Output is correct