Submission #230624

#	Time	Username	Problem	Language	Result	Execution time	Memory
230624		Fasho	Valley (BOI19_valley)	C++14	0 / 100	292 ms	79580 KiB

valley

#include <bits/stdc++.h>
#define N 300005
#define ll long long int 	
#define MP make_pair
#define pb push_back
#define ppb pop_back
#define sp " "
#define endl "\n"
#define fi first
#define se second
#define ii pair<int,int>
#define lli pair<ll,ll>
#define fast cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false)
#define fast2 freopen ("badhair.gir","r",stdin);freopen ("badhair.cik","w",stdout);
#define mod 1000000007
#define fs(x,y) for(ll i=1;i<=y;i++) cin>>x[i]
#define fo(i,x,y) for(ll i=x;i<=y;i++)
#define INF 1000000000005
#define ull unsigned long long int
using namespace std;

ll n,m,ar[N],sum,t,s,q,e,dist[N],mark[N],magic[N],jumpvertex[N][30],jumpmagic[N][30],shop[N],cnt,tut[N],dp[N],ilk[N],pw[N];

lli tree[10*N],edg[N];

vector<lli> v[N];

void f1(ll ind,ll back,ll dst)
{
	dist[ind]=dst;
	tut[++cnt]=ind;
	ilk[ind]=cnt;
	dp[ind]=1e16;
	jumpvertex[ind][0]=back;
	fo(i,1,20)
	{
		jumpvertex[ind][i]=jumpvertex[jumpvertex[ind][i-1]][i-1];
	}
	if(shop[ind])
		dp[ind]=dst;
	// jumpmagic[ind][0]=-2*dst+dp[ind];	
	// fo(i,1,20)
	// {
	// 	jumpmagic[ind][i]=min(jumpmagic[ind][i-1],jumpmagic[jumpvertex[ind][i-1]][i-1]);
	// }
	for(int i=0;i<v[ind].size();i++)
	{
		ll a=v[ind][i].fi;
		ll b=v[ind][i].se;
		if(a==back)
			continue;
		f1(a,ind,dst+b);
		tut[++cnt]=ind;
		if(dp[a]<1e15)
			dp[ind]=min(dp[ind],dp[a]);
	}
	magic[ind]=-2*dst+dp[ind];
	if(dp[ind]==1e16)
		magic[ind]=1e16;

}
void f2(int ind,int back,int dst)
{
	jumpmagic[ind][0]=magic[ind];
	fo(i,1,20)
	{
		jumpmagic[ind][i]=min(jumpmagic[ind][i-1],jumpmagic[jumpvertex[ind][i-1]][i-1]);
	}
	for(int i=0;i<v[ind].size();i++)
	{
		ll a=v[ind][i].fi;
		ll b=v[ind][i].se;
		if(a==back)
			continue;
		f2(a,ind,dst+b);

	}
}

void build(int ind,int l,int r)
{
	if(l==r)
	{
		tree[ind]={dist[tut[l]],tut[l]};
		return;
	}
	int mid=(l+r)/2;
	build(ind*2,l,mid);
	build(ind*2+1,mid+1,r);

	tree[ind]=min(tree[ind*2],tree[ind*2+1]);
}

lli query(int ind,int l,int r,int a,int b)
{
	if(l>b || r<a)
		return {1e16,0};
	if(l>=a && r<=b)
		return tree[ind];
	int mid=(l+r)/2;
	return min(query(ind*2,l,mid,a,b),query(ind*2+1,mid+1,r,a,b));
}

ll lca(ll a,ll b)
{
	return query(1,1,cnt,min(ilk[a],ilk[b]),max(ilk[a],ilk[b])).se;
}

int main()
{
	fast;
	// cout<<endl<<endl;
	cin>>n>>s>>q>>e;
	pw[0]=1;
	fo(i,1,20)
	pw[i]=pw[i-1]*2;
	fo(i,1,n-1)
	{
		ll a,b,c;
		cin>>a>>b>>c;
		edg[i]={a,b};
		v[a].pb({b,c});
		v[b].pb({a,c});
	}
	fo(i,1,s)
	{
		int a;
		cin>>a;
		shop[a]=1;
	}
	f1(e,e,0);

	f2(e,e,0);
	// fo(i,1,n)
	// cout<<i<<sp<<magic[i]<<endl;
	build(1,1,cnt);
	// cout<<cnt<<endl;
	// fo(i,1,cnt)
	// cout<<tut[i]<<sp;
	// cout<<endl;

	fo(i,1,q)
	{
		int a,b;
		cin>>a>>b;
		int x=edg[a].fi;
		int y=edg[a].se;
		if(lca(x,b)!=x || lca(y,b)!=y)
		{
			cout<<"escaped"<<endl;
			continue;
		}
		ll z=dist[b];
		// cout<<z<<sp;
		z-=max(dist[x],dist[y]);
		// cout<<++z<<sp;
		sum=1e17;
		int ind=b;
		for(int j=20;j>=0;j--)
		{
			if(pw[j]<=z)
			{
				z-=pw[j],sum=min(sum,jumpmagic[ind][j]);
				ind=jumpvertex[ind][j];
			}
		}
		if(sum>=1e16)
		{
			cout<<"oo"<<endl;
			continue;
		}
		cout<<sum+dist[b]<<endl;
	}
	// cout<<endl<<endl;
	// fo(i,1,n)
	// {
	// 	cout<<i<<": ";
		// for(int j=0;j<=2;j++)
		// 	cout<<jumpmagic[i][j]<<sp;
		// 	cout<<endl;
		// cout<<i<<": ";

		// for(int j=0;j<=2;j++)
		// 	cout<<jumpvertex[jumpvertex[i][j-1]][j-1]<<sp;
		// cout<<endl;
		// cout<<endl;

	// }
}

Compilation message (stderr)

valley.cpp: In function 'void f1(long long int, long long int, long long int)':
valley.cpp:46:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<v[ind].size();i++)
              ~^~~~~~~~~~~~~~
valley.cpp: In function 'void f2(int, int, int)':
valley.cpp:69:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<v[ind].size();i++)
              ~^~~~~~~~~~~~~~

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