oj.uz

Submission #503720

# Submission time Handle Problem Language Result Execution time Memory
503720 2022-01-08T17:43:30 Z Arnch Valley (BOI19_valley) C++17
36 / 100
 168 ms 262148 KB 
// oooo
/*
 be hengam shena mesle y dasto pa cholofti ~
 bepa to masire dahane koose neyofti ~
 ;Amoo_Hasan;
*/

#include<bits/stdc++.h>
#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
#pragma GCC target("avx2,fma")

using namespace std;

typedef long long ll;
typedef long double ld;

#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define Sz(x) int((x).size())
#define all(x) (x).begin(), (x).end()

const ll inf = 1e18, N = 1e6 + 10, mod = 1e9 + 7, pr = 1000696969, Log = 25;

int n, s, q, e;
ll par[N][Log], ans[N][Log], ans_h[N][Log], h[N], d[N];

bool mark[N], S[N];

vector<pair<int, int> > G[N], vc;

void get_input() {
	cin >>n >>s >>q >>e;
	for(int i = 1; i <= n - 1; i++) {
		int u, v, w; cin >>u >>v >>w;
		vc.push_back({u, v});
		G[u].push_back({v, w}), G[v].push_back({u, w});
	}
	for(int i = 0; i < s; i++) {
		int u; cin >>u; S[u] = 1;
	}
}

void dfs(int x, int p) {
	mark[x] = 1, par[x][0] = p; 
	if(S[x]) d[x] = 0;
	
	for(int i = 1; i < Log; i++) par[x][i] = par[par[x][i - 1]][i - 1];

	for(auto i : G[x]) if(!mark[i.first]) {
		h[i.first] = h[x] + 1;
		dfs(i.first, x);
		d[x] = min(d[x], d[i.first] + i.second);
	}
}

void main_dfs(int x, int val) {
	mark[x] = 1, ans[x][0] = d[x], ans_h[x][0] = val;
	
	for(int i = 1; i < Log; i++) {
		if(par[x][i - 1] == 0) break;
		
		ans_h[x][i] = ans_h[x][i - 1] + ans_h[par[x][i - 1]][i - 1];
		
		ans[x][i] = min(ans[x][i - 1], ans[par[x][i - 1]][i - 1] + ans_h[x][i - 1]);
	}


	for(auto i : G[x]) if(!mark[i.first]) {
		main_dfs(i.first, i.second);
	}
}

int get_par(int x, int y) {
	for(int i = 0; i < Log; i++) 
		if((y >> i) & 1) 
			x = par[x][i];

	return x;
}

int lca(int x, int y) {
	if(h[x] > h[y]) swap(x, y);
	y = get_par(y, h[y] - h[x]);
	if(x == y) return x;

	for(int i = Log - 1; i >= 0; i--) {
		if(par[x][i] != par[y][i]) {
			x = par[x][i], y = par[y][i];
		}
	}

	return par[x][0];
}

void solve() {
	int e, u; cin >>e >>u;
	e--;

	int l = vc[e].first;
	if(par[l][0] != vc[e].second) l = vc[e].second;
	
	if(lca(l, u) != l) {
		cout<<"escaped" <<'\n';
		return;
	}

	l = par[l][0];
	
	ll cnt = h[u] - h[l], sum = inf, eq = 0;

	for(int i = 0; i < Log; i++) {
		if((cnt >> i) & 1) {
			sum = min(sum, ans[u][i] + eq);

			eq += ans_h[u][i];
		
			u = par[u][i];
		}
	}

	if(sum >= inf) cout<<"oo" <<'\n';
	else cout<<sum <<'\n';
}

int main() {
    fast_io;
	
	get_input();
	
	memset(d, 63, sizeof(d));

	dfs(e, 0);

	memset(mark, 0, sizeof(mark)), memset(ans, 63, sizeof(ans));

	main_dfs(e, 0);	

	while(q--) solve();


    return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 228348 KB Output is correct
2 Correct 97 ms 228472 KB Output is correct
3 Correct 90 ms 228472 KB Output is correct
4 Correct 105 ms 228484 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 228348 KB Output is correct
2 Correct 97 ms 228472 KB Output is correct
3 Correct 90 ms 228472 KB Output is correct
4 Correct 105 ms 228484 KB Output is correct
5 Correct 95 ms 228804 KB Output is correct
6 Correct 87 ms 228804 KB Output is correct
7 Correct 85 ms 228804 KB Output is correct
8 Correct 95 ms 228736 KB Output is correct
9 Correct 133 ms 228740 KB Output is correct
10 Correct 91 ms 228800 KB Output is correct
11 Correct 86 ms 228680 KB Output is correct
12 Correct 94 ms 228740 KB Output is correct
13 Correct 94 ms 228772 KB Output is correct
14 Correct 101 ms 228732 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 168 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 228348 KB Output is correct
2 Correct 97 ms 228472 KB Output is correct
3 Correct 90 ms 228472 KB Output is correct
4 Correct 105 ms 228484 KB Output is correct
5 Correct 95 ms 228804 KB Output is correct
6 Correct 87 ms 228804 KB Output is correct
7 Correct 85 ms 228804 KB Output is correct
8 Correct 95 ms 228736 KB Output is correct
9 Correct 133 ms 228740 KB Output is correct
10 Correct 91 ms 228800 KB Output is correct
11 Correct 86 ms 228680 KB Output is correct
12 Correct 94 ms 228740 KB Output is correct
13 Correct 94 ms 228772 KB Output is correct
14 Correct 101 ms 228732 KB Output is correct
15 Runtime error 168 ms 262148 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -