oj.uz

Submission #696544

# Submission time Handle Problem Language Result Execution time Memory
696544 2023-02-06T18:07:04 Z AmirAli_H1 Valley (BOI19_valley) C++17
100 / 100
 243 ms 59640 KB 
// In the name of Allah

#include <bits/stdc++.h>
using namespace std;

typedef long long int	ll;
typedef long double	ld;
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pll;

#define all(x)		(x).begin(),(x).end()
#define len(x)		((ll) (x).size())
#define F		first
#define S		second
#define pb		push_back
#define sep             ' '
#define endl            '\n'
#define Mp		make_pair
#define debug(x)	cerr << #x << ": " <<  x << endl;
#define kill(x)		cout << x << '\n', exit(0);
#define set_dec(x)	cout << fixed << setprecision(x);
#define file_io(x,y)	freopen(x, "r", stdin); freopen(y, "w", stdout);

int n, s, q, e;
const int maxn = 1e5 + 5;
const int maxlg = 20;
const ll oo = 1e18;
vector<pll> adj[maxn];
vector<pair<pii, ll>> E;
bool M[maxn];
bool mark[maxn]; int h[maxn]; ll dp[maxn];
int st[maxn], ft[maxn], timer = 0;
int up[maxn][maxlg]; ll W[maxn][maxlg], res[maxn][maxlg];

bool is_gr(int v, int u) {
	return st[v] <= st[u] && ft[v] >= ft[u];
}

void pre_dfs(int v) {
	mark[v] = 1;
	st[v] = timer++;
	if (M[v]) dp[v] = 0;
	else dp[v] = oo;
	for (auto f : adj[v]) {
		auto [u, w] = f;
		if (!mark[u]) {
			h[u] = h[v] + 1;
			pre_dfs(u);
			dp[v] = min(oo, min(dp[v], dp[u] + w));
		}
	}
	ft[v] = timer++;
}

ll get_ans(int u, int k) {
	ll ans = oo, w = 0;
	for (int i = 0; i < maxlg; i++) {
		if (k & (1 << i)) {
			ans = min(ans, w + res[u][i]);
			w += W[u][i]; u = up[u][i];
		}
	}
	return ans;
}

void dfs_res(int v, int p = -1, ll wx = 0) {
	mark[v] = 1;
	
	up[v][0] = (p != -1) ? p : v;
	W[v][0] = wx; res[v][0] = dp[v];
	for (int i = 1; i < maxlg; i++) {
		int u = up[v][i - 1];
		up[v][i] = up[u][i - 1];
		W[v][i] = W[v][i - 1] + W[u][i - 1];
		res[v][i] = min(oo, min(res[v][i - 1], W[v][i - 1] + res[u][i - 1]));
	}
	
	for (auto f : adj[v]) {
		auto [u, w] = f;
		if (!mark[u]) {
			dfs_res(u, v, w);
		}
	}
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	cin >> n >> s >> q >> e; e--;
	for (int i = 0; i < n - 1; i++) {
		int u, v; ll w;
		cin >> u >> v >> w; u--; v--;
		adj[u].pb(Mp(v, w)); adj[v].pb(Mp(u, w));
		E.pb(Mp(Mp(u, v), w));
	}
	
	for (int i = 0; i < s; i++) {
		int u;
		cin >> u; u--;
		M[u] = 1;
	}
	
	fill(mark, mark + n, 0); pre_dfs(e);
	fill(mark, mark + n, 0); dfs_res(e);
	
	while (q--) {
		int i, u;
		cin >> i >> u; i--; u--;
		auto [u1, v1] = E[i].F;
		if (h[u1] < h[v1]) swap(u1, v1);
		if (is_gr(u1, u)) {
			int k = h[u] - h[u1] + 1;
			ll ans = get_ans(u, k);
			if (ans < oo) cout << ans << endl;
			else cout << "oo" << endl;
		}
		else {
			cout << "escaped" << endl;
		}
	}
	
	return 0;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
27.0 / 27.0

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

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 55140 KB Output is correct
2 Correct 149 ms 54964 KB Output is correct
3 Correct 184 ms 55296 KB Output is correct
4 Correct 227 ms 57020 KB Output is correct
5 Correct 183 ms 57204 KB Output is correct
6 Correct 241 ms 59268 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2900 KB Output is correct
2 Correct 6 ms 2820 KB Output is correct
3 Correct 4 ms 2900 KB Output is correct
4 Correct 4 ms 2812 KB Output is correct
5 Correct 3 ms 3156 KB Output is correct
6 Correct 2 ms 3200 KB Output is correct
7 Correct 3 ms 3156 KB Output is correct
8 Correct 4 ms 3184 KB Output is correct
9 Correct 3 ms 3148 KB Output is correct
10 Correct 3 ms 3200 KB Output is correct
11 Correct 3 ms 3200 KB Output is correct
12 Correct 3 ms 3156 KB Output is correct
13 Correct 4 ms 3196 KB Output is correct
14 Correct 3 ms 3156 KB Output is correct
15 Correct 181 ms 55140 KB Output is correct
16 Correct 149 ms 54964 KB Output is correct
17 Correct 184 ms 55296 KB Output is correct
18 Correct 227 ms 57020 KB Output is correct
19 Correct 183 ms 57204 KB Output is correct
20 Correct 241 ms 59268 KB Output is correct
21 Correct 150 ms 54460 KB Output is correct
22 Correct 172 ms 54368 KB Output is correct
23 Correct 202 ms 54720 KB Output is correct
24 Correct 197 ms 56688 KB Output is correct
25 Correct 212 ms 59640 KB Output is correct
26 Correct 150 ms 54536 KB Output is correct
27 Correct 149 ms 54428 KB Output is correct
28 Correct 156 ms 54644 KB Output is correct
29 Correct 200 ms 56116 KB Output is correct
30 Correct 243 ms 57704 KB Output is correct
31 Correct 143 ms 54700 KB Output is correct
32 Correct 162 ms 54564 KB Output is correct
33 Correct 170 ms 54852 KB Output is correct
34 Correct 211 ms 56688 KB Output is correct
35 Correct 238 ms 59624 KB Output is correct
36 Correct 207 ms 56656 KB Output is correct