oj.uz

Submission #473704

# Submission time Handle Problem Language Result Execution time Memory
473704 2021-09-15T21:00:01 Z disastah Valley (BOI19_valley) C++17
100 / 100
 236 ms 42692 KB 
#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#define ar array
using namespace std;
typedef long double ld;
typedef long long ll;
const int inf=1e9+1e8;
const ll linf=4e18+18;
const int N=1e5;

int n, shops, q, st;
ar<int,3> e[N];
vector<ar<int,2>> g[N];
bool shop[N];
int par[N], lvl[N], tin[N], tout[N], timer=0;
ll h[N], trshop[N];
void dfs(int v, int p=-1) {
	tin[v]=timer++;
	trshop[v]=linf;
	if (shop[v]) trshop[v]=0LL;
	for (auto &[u,c] : g[v]) {
		if (u!=p) {
			par[u]=v;
			lvl[u]=lvl[v]+1;
			h[u]=h[v]+c;
			dfs(u,v);
			trshop[v]=min(trshop[v],min(linf,trshop[u]+c));
		}
	}
	tout[v]=timer++;
}
int bup[N][20]; ll bshop[N][20];
void solve() {
	cin >> n >> shops >> q >> st; --st;
	for (int i=0; i<n-1; ++i) {
		int u, v, c; cin >> u >> v >> c; --u, --v;
		e[i]={u,v,c};
		g[u].push_back({v,c});
		g[v].push_back({u,c});
	}
	for (int i=0; i<shops; ++i) {
		int x; cin >> x; --x;
		shop[x]=1;
	}
	par[st]=st, h[st]=0LL;
	dfs(st);
	for (int d=0; d<20; ++d) {
		for (int i=0; i<n; ++i) {
			if (!d) {
				bup[i][d]=par[i];
				bshop[i][d]=h[i]-h[par[i]]+trshop[par[i]];
			}
			else {
				bup[i][d]=bup[bup[i][d-1]][d-1];
				bshop[i][d]=min(bshop[i][d-1],bshop[bup[i][d-1]][d-1]+h[i]-h[bup[i][d-1]]);
			}
		}
	}
	int ind, x;
	while(q--) {
		cin >> ind >> x; --ind, --x;
		auto &[v1,v2,c]=e[ind];
		if (tin[v2]<tin[v1]&&tout[v2]>tout[v1]) swap(v1,v2);
		if (tin[v2]<=tin[x]&&tout[v2]>=tout[x]) {
			ll ans=trshop[x];
			int v=x, dh=lvl[x]-lvl[v2];
			for (int i=0; i<20; ++i) {
				if ((dh>>i)&1) {
					ans=min(ans,h[x]-h[v]+bshop[v][i]);
					v=bup[v][i];
				}
			}
			if (ans<linf) cout << ans << "\n";
			else cout << "oo\n";
		}
		else cout << "escaped\n";
	}
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
#ifdef disastah
	cout << "Output\n\n";
#endif
	int tt=1;
//	cin >> tt;
	while (tt--) {
		solve();
		cout << "\n";
	}
}

Subtask #1
9.0 / 9.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2764 KB Output is correct
2 Correct 5 ms 2892 KB Output is correct
3 Correct 4 ms 2764 KB Output is correct
4 Correct 4 ms 2764 KB Output is correct
5 Correct 3 ms 2984 KB Output is correct
6 Correct 3 ms 3020 KB Output is correct
7 Correct 3 ms 3020 KB Output is correct
8 Correct 3 ms 3068 KB Output is correct
9 Correct 3 ms 3020 KB Output is correct
10 Correct 3 ms 3072 KB Output is correct
11 Correct 3 ms 3020 KB Output is correct
12 Correct 3 ms 3020 KB Output is correct
13 Correct 3 ms 3020 KB Output is correct
14 Correct 3 ms 3076 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 38900 KB Output is correct
2 Correct 176 ms 38604 KB Output is correct
3 Correct 205 ms 38536 KB Output is correct
4 Correct 212 ms 40348 KB Output is correct
5 Correct 215 ms 40336 KB Output is correct
6 Correct 236 ms 42308 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2764 KB Output is correct
2 Correct 5 ms 2892 KB Output is correct
3 Correct 4 ms 2764 KB Output is correct
4 Correct 4 ms 2764 KB Output is correct
5 Correct 3 ms 2984 KB Output is correct
6 Correct 3 ms 3020 KB Output is correct
7 Correct 3 ms 3020 KB Output is correct
8 Correct 3 ms 3068 KB Output is correct
9 Correct 3 ms 3020 KB Output is correct
10 Correct 3 ms 3072 KB Output is correct
11 Correct 3 ms 3020 KB Output is correct
12 Correct 3 ms 3020 KB Output is correct
13 Correct 3 ms 3020 KB Output is correct
14 Correct 3 ms 3076 KB Output is correct
15 Correct 171 ms 38900 KB Output is correct
16 Correct 176 ms 38604 KB Output is correct
17 Correct 205 ms 38536 KB Output is correct
18 Correct 212 ms 40348 KB Output is correct
19 Correct 215 ms 40336 KB Output is correct
20 Correct 236 ms 42308 KB Output is correct
21 Correct 161 ms 38224 KB Output is correct
22 Correct 175 ms 38040 KB Output is correct
23 Correct 198 ms 37928 KB Output is correct
24 Correct 225 ms 39944 KB Output is correct
25 Correct 231 ms 42692 KB Output is correct
26 Correct 163 ms 38424 KB Output is correct
27 Correct 158 ms 38004 KB Output is correct
28 Correct 166 ms 37956 KB Output is correct
29 Correct 194 ms 39376 KB Output is correct
30 Correct 209 ms 40740 KB Output is correct
31 Correct 153 ms 38384 KB Output is correct
32 Correct 161 ms 38096 KB Output is correct
33 Correct 187 ms 38144 KB Output is correct
34 Correct 213 ms 39960 KB Output is correct
35 Correct 206 ms 42620 KB Output is correct
36 Correct 188 ms 40080 KB Output is correct