oj.uz

Submission #903848

# Submission time Handle Problem Language Result Execution time Memory
903848 2024-01-11T12:22:58 Z PM1 Valley (BOI19_valley) C++17
100 / 100
 372 ms 54428 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define fr first
#define sc second
const ll mxn=1e5+5;
ll n,s,q,e,st[mxn],fn[mxn],cnt=0,mark[mxn];
ll par[mxn][20],bl[mxn][20],dp[mxn],yal[mxn],ras[mxn],val[mxn];
vector<pair<ll,ll> >v[mxn];
void pre(ll z){
	dp[z]=(mark[z])?0:1e15;
	st[z]=++cnt;
	for(ll i=1;i<20;i++){
		par[z][i]=par[par[z][i-1]][i-1];
	}
	for(auto i:v[z]){
		if(par[z][0]!=i.fr){
			bl[i.fr][0]=yal[i.sc];
			ras[i.sc]=i.fr;
			par[i.fr][0]=z;
			val[i.fr]=val[z]+yal[i.sc];
			pre(i.fr);
			dp[z]=min(dp[z],dp[i.fr]+yal[i.sc]);
		}
	}
	bl[z][0]=dp[z]-val[z];
	fn[z]=cnt;
}
void dfs(int z){
	for(int i=1;i<20;i++){
		bl[z][i]=min(bl[z][i-1],bl[par[z][i-1]][i-1]);
	}
	for(auto i:v[z]){
		if(par[z][0]!=i.fr){
			dfs(i.fr);
		}
	}
}
ll lca(ll x,ll y){
	ll res=1e15;
	for(ll i=19;i>=0;i--){
		if(par[x][i]==0)
			continue;
		if(st[par[x][i]]>st[y] || fn[par[x][i]]<fn[y]){
			res=min(res,bl[x][i]);
			x=par[x][i];
		}
	}
	//cout<<x<<" ";
	if(x!=y)
		return min(res,bl[x][1]);
	return min(res,bl[x][0]);
}
int main(){
	ios::sync_with_stdio(false);
	
	cin>>n>>s>>q>>e;
	for(ll i=1;i<n;i++){
		ll x,y,w;
		cin>>x>>y>>yal[i];
		v[x].push_back({y,i});
		v[y].push_back({x,i});
	}
	for(ll i=1;i<=s;i++){
		ll x;
		cin>>x;
		mark[x]=1;
	}
	pre(e);
	dfs(e);
	while(q--){
		ll x,y;
		cin>>x>>y;
		swap(x,y);
		y=ras[y];
		//cout<<x<<" "<<y<<endl;
		if(st[y]>st[x] || fn[y]<fn[x])
			cout<<"escaped"<<'\n';
		else{
			if(dp[y]==1e15)
				cout<<"oo"<<'\n';
			else{
				cout<<lca(x,y)+val[x]<<'\n';
			}
		}
	}
	return 0;
}

Compilation message

valley.cpp: In function 'int main()':
valley.cpp:59:10: warning: unused variable 'w' [-Wunused-variable]
   59 |   ll x,y,w;
      |          ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 8796 KB Output is correct
2 Correct 14 ms 8916 KB Output is correct
3 Correct 18 ms 8796 KB Output is correct
4 Correct 14 ms 8792 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 8796 KB Output is correct
2 Correct 14 ms 8916 KB Output is correct
3 Correct 18 ms 8796 KB Output is correct
4 Correct 14 ms 8792 KB Output is correct
5 Correct 4 ms 9052 KB Output is correct
6 Correct 3 ms 9052 KB Output is correct
7 Correct 3 ms 9052 KB Output is correct
8 Correct 3 ms 9052 KB Output is correct
9 Correct 3 ms 9052 KB Output is correct
10 Correct 3 ms 8920 KB Output is correct
11 Correct 5 ms 9052 KB Output is correct
12 Correct 5 ms 9052 KB Output is correct
13 Correct 3 ms 9052 KB Output is correct
14 Correct 4 ms 9052 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 49128 KB Output is correct
2 Correct 256 ms 48864 KB Output is correct
3 Correct 294 ms 49156 KB Output is correct
4 Correct 298 ms 51564 KB Output is correct
5 Correct 274 ms 51548 KB Output is correct
6 Correct 322 ms 54056 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 8796 KB Output is correct
2 Correct 14 ms 8916 KB Output is correct
3 Correct 18 ms 8796 KB Output is correct
4 Correct 14 ms 8792 KB Output is correct
5 Correct 4 ms 9052 KB Output is correct
6 Correct 3 ms 9052 KB Output is correct
7 Correct 3 ms 9052 KB Output is correct
8 Correct 3 ms 9052 KB Output is correct
9 Correct 3 ms 9052 KB Output is correct
10 Correct 3 ms 8920 KB Output is correct
11 Correct 5 ms 9052 KB Output is correct
12 Correct 5 ms 9052 KB Output is correct
13 Correct 3 ms 9052 KB Output is correct
14 Correct 4 ms 9052 KB Output is correct
15 Correct 243 ms 49128 KB Output is correct
16 Correct 256 ms 48864 KB Output is correct
17 Correct 294 ms 49156 KB Output is correct
18 Correct 298 ms 51564 KB Output is correct
19 Correct 274 ms 51548 KB Output is correct
20 Correct 322 ms 54056 KB Output is correct
21 Correct 234 ms 48208 KB Output is correct
22 Correct 243 ms 47600 KB Output is correct
23 Correct 248 ms 48064 KB Output is correct
24 Correct 271 ms 50476 KB Output is correct
25 Correct 294 ms 54360 KB Output is correct
26 Correct 235 ms 48296 KB Output is correct
27 Correct 230 ms 48204 KB Output is correct
28 Correct 263 ms 48468 KB Output is correct
29 Correct 250 ms 50004 KB Output is correct
30 Correct 326 ms 52076 KB Output is correct
31 Correct 230 ms 48724 KB Output is correct
32 Correct 266 ms 48416 KB Output is correct
33 Correct 264 ms 48864 KB Output is correct
34 Correct 292 ms 50936 KB Output is correct
35 Correct 372 ms 54428 KB Output is correct
36 Correct 272 ms 51080 KB Output is correct