Submission #1085252

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085252		goduadzesaba	Valley (BOI19_valley)	C++17	100 / 100	168 ms	55228 KiB

valley

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
int n,s,q,e,x,y,z,cur,tin[N],tout[N];
int val[N],dp[N],d[N],par[N][20],a[N][20];
vector <pair<int,int> > v[N],edg;
bool b[N]; vector <int> sv;
void dfs(int i,int p,int dd){
	cur++; tin[i]=cur;
	dp[i]=dp[p]+dd; d[i]=d[p]+1;
	par[i][0]=p; val[i]=(b[i]?0:1e15);
	for (int j=1; j<20; j++)
		par[i][j]=par[par[i][j-1]][j-1];
	for (auto j:v[i]){
		if (j.first==p) continue;
		dfs(j.first,i,j.second);
		val[i]=min(val[i],val[j.first]+j.second);
	}
	tout[i]=cur;
}
void dfs2(int i,int p){
	int xx=1e15;
	a[i][0]=min(xx,val[i]-dp[i]);
	for (int j=1; j<20; j++)
		a[i][j]=min(a[i][j-1],a[par[i][j-1]][j-1]);
	for (auto j:v[i]){
		if (j.first==p) continue;
		dfs2(j.first,i);
	}
}
bool ispar(int a,int b){
	if (tin[a]<=tin[b] && tout[a]>=tout[b])
		return 1;
	return 0;
}
int cnt(int i,int k){
	int res=1e15;
	for (int j=19; j>=0; j--)
		if ((1<<j)<=k){
			k-=(1<<j);
			res=min(res,a[i][j]);
			i=par[i][j];
		}
	return res;
}
signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>n>>s>>q>>e; edg.push_back({0,0});
	for (int i=1; i<n; i++){
		cin>>x>>y>>z;
		edg.push_back({x,y});
		v[x].push_back({y,z});
		v[y].push_back({x,z});
	}
	for (int i=1; i<=s; i++){
		cin>>x; b[x]=1;
	}
	for (int j=0; j<20; j++) a[0][j]=1e15;
	d[0]=-1; dfs(e,0,0); dfs2(e,0);
	/*for (int i=1; i<=n; i++)
		for (int j=0; j<20; j++)
			cout<<i<<" "<<j<<"-->"<<a[i][j]<<"\n";*/
	for (int i=1; i<=n; i++)
		if (b[i]) sv.push_back(tin[i]);
	sort(sv.begin(),sv.end());
	while (q--){
		cin>>x>>y;
		if (ispar(edg[x].second,edg[x].first))
			x=edg[x].first;
		else x=edg[x].second;
		if (!ispar(x,y)){
			cout<<"escaped\n"; continue;
		}
		auto it=lower_bound(sv.begin(),sv.end(),tin[x]);
		if (it==sv.end() || *it>tout[x]){
			cout<<"oo\n"; continue;
		}
		cout<<cnt(y,d[y]-d[x]+1)+dp[y]<<"\n";
	}
}

• Subtask 1: 9 / 9
• Subtask 2: 27 / 27
• Subtask 3: 23 / 23
• Subtask 4: 41 / 41