oj.uz

Submission #411566

# Submission time Handle Problem Language Result Execution time Memory
411566 2021-05-25T13:55:28 Z ak2006 Valley (BOI19_valley) C++14
100 / 100
 572 ms 75372 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vl = vector<ll>;
using vvl = vector<vl>;
using vvvl = vector<vvl>;
using vi = vector<int>;
using vvi = vector<vi>;
using vb = vector<bool>;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
const ll inf = 1e15;
void setIO()
{
	fast;
}
int n = 1e5 + 5,s,q,root;
vi in(n),out(n),num(n);
vl magic(n,inf),dist(n);
vvl anc(n,vl(21)),dp(n,vl(21));
vvvl adj(n);
vb shop(n);
int t;
void dfs(int u,int p,ll wt)
{
	if (p != -1)dist[u] = dist[p] + wt,num[u] = num[p] + 1;
	in[u] = t++;
	if (shop[u])magic[u] = dist[u];

	for (auto x:adj[u]){
		int v = x[0];
		ll w = x[1];
		if (v == p)continue;
		dfs(v,u,w);
		magic[u] = min(magic[u],magic[v]);
	}
	
	out[u] = t++;
}
bool is_ancestor(int u,int v)
{
	return in[u] <= in[v] && out[u] >= out[v];
}
void dfs2(int u,int p)
{
	anc[u][0] = p;
	dp[u][0] = magic[u];
	for (int i = 1;i<=20;i++){
		anc[u][i] = anc[anc[u][i - 1]][i - 1];
		dp[u][i] = min(dp[u][i - 1],dp[anc[u][i - 1]][i - 1]);
	}
	for (auto x:adj[u]){
		int v = x[0];
		if (v == p)continue;
		dfs2(v,u);
	}
}
int main()
{
	setIO();	
	cin>>n>>s>>q>>root;
	vvi edges;
	for (int i = 1;i<n;i++){
		int u,v,w;
		cin>>u>>v>>w;
		adj[u].pb({v,w});
		adj[v].pb({u,w});
		edges.pb({u,v});
	}
	for (int i = 1;i<=s;i++){
		int x;
		cin>>x;
		shop[x] = 1;
	}
	dfs(root,-1,0);
	for (int i = 1;i<=n;i++)if (magic[i] < inf)magic[i] += -2 * dist[i];
	dfs2(root,root);
	while (q--){
		int pos,u;
		cin>>pos>>u;
		int child = edges[pos - 1][0],par = edges[pos - 1][1];
		if (in[child] < in[par])swap(child,par);
		if (!is_ancestor(child,u))cout<<"escaped"<<'\n';
		else {
			//now find min of magic[v] for all v on the path from u to child
			int distance = - num[child] + num[u] + 1;
			int node = u;
			ll val = magic[u];
			for (int i = 0;i<=20;i++){
				if (distance&(1<<i)){
					val = min(val,dp[u][i]);
					u = anc[u][i];
				}
			}
			if (val >= inf)cout<<"oo"<<'\n';
			else cout<<dist[node] + val<<'\n';
		}
	}
	return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 44664 KB Output is correct
2 Correct 42 ms 44696 KB Output is correct
3 Correct 37 ms 44632 KB Output is correct
4 Correct 36 ms 44700 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 44664 KB Output is correct
2 Correct 42 ms 44696 KB Output is correct
3 Correct 37 ms 44632 KB Output is correct
4 Correct 36 ms 44700 KB Output is correct
5 Correct 35 ms 44748 KB Output is correct
6 Correct 35 ms 44716 KB Output is correct
7 Correct 36 ms 44728 KB Output is correct
8 Correct 35 ms 44708 KB Output is correct
9 Correct 34 ms 44748 KB Output is correct
10 Correct 35 ms 44680 KB Output is correct
11 Correct 34 ms 44712 KB Output is correct
12 Correct 35 ms 44736 KB Output is correct
13 Correct 35 ms 44704 KB Output is correct
14 Correct 34 ms 44740 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 337 ms 63300 KB Output is correct
2 Correct 379 ms 63332 KB Output is correct
3 Correct 369 ms 63344 KB Output is correct
4 Correct 435 ms 66676 KB Output is correct
5 Correct 407 ms 66672 KB Output is correct
6 Correct 572 ms 70532 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 44664 KB Output is correct
2 Correct 42 ms 44696 KB Output is correct
3 Correct 37 ms 44632 KB Output is correct
4 Correct 36 ms 44700 KB Output is correct
5 Correct 35 ms 44748 KB Output is correct
6 Correct 35 ms 44716 KB Output is correct
7 Correct 36 ms 44728 KB Output is correct
8 Correct 35 ms 44708 KB Output is correct
9 Correct 34 ms 44748 KB Output is correct
10 Correct 35 ms 44680 KB Output is correct
11 Correct 34 ms 44712 KB Output is correct
12 Correct 35 ms 44736 KB Output is correct
13 Correct 35 ms 44704 KB Output is correct
14 Correct 34 ms 44740 KB Output is correct
15 Correct 337 ms 63300 KB Output is correct
16 Correct 379 ms 63332 KB Output is correct
17 Correct 369 ms 63344 KB Output is correct
18 Correct 435 ms 66676 KB Output is correct
19 Correct 407 ms 66672 KB Output is correct
20 Correct 572 ms 70532 KB Output is correct
21 Correct 321 ms 66616 KB Output is correct
22 Correct 352 ms 66708 KB Output is correct
23 Correct 369 ms 66608 KB Output is correct
24 Correct 425 ms 70384 KB Output is correct
25 Correct 473 ms 75372 KB Output is correct
26 Correct 328 ms 66676 KB Output is correct
27 Correct 365 ms 66604 KB Output is correct
28 Correct 370 ms 66636 KB Output is correct
29 Correct 468 ms 69120 KB Output is correct
30 Correct 494 ms 71736 KB Output is correct
31 Correct 336 ms 66672 KB Output is correct
32 Correct 353 ms 66676 KB Output is correct
33 Correct 369 ms 66892 KB Output is correct
34 Correct 441 ms 70028 KB Output is correct
35 Correct 477 ms 75132 KB Output is correct
36 Correct 422 ms 70260 KB Output is correct