Submission #202862

#	Time	Username	Problem	Language	Result	Execution time	Memory
202862		Fasho	Valley (BOI19_valley)	C++14	23 / 100	255 ms	56952 KiB

valley

#include <bits/stdc++.h>
#define N 1000005
#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,tut,flag,mark[N],tutmac[N],cnt,tuttur[N],ff[N],height[N];
lli tree[4*N];
vector<pair<int,ii> > v[N];

lli p[N];

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

void build(int ind,int l,int r)
{
	if(l==r)
	{
		tree[ind].fi=height[tuttur[l]];
		tree[ind].se=tuttur[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]);
}

void f(int ind,ll len)
{
	if(mark[ind])
		return;
	mark[ind]++;
	// cout<<"[d]"<<sp<<ind<<endl;
	tuttur[++cnt]=ind;
	ff[ind]=cnt;
	height[ind]=len;
	// if(ind==e)
	// {
	// 	flag=1;
	// 	return;
	// }
	if(tutmac[ind])
		sum=min(sum,len);
	for(int i=0;i<v[ind].size();i++)
	{
		int a=v[ind][i].fi;
		ll b=v[ind][i].se.fi;
		if(!mark[a])
			f(a,len+1);
		tuttur[++cnt]=ind;
	}
}

void pre()
{
	f(e,0);
	build(1,1,cnt);
}
ll lca(int a,int b)
{
	int x=ff[a];
	int y=ff[b];
	if(x>y)
		swap(x,y);

	return query(1,1,cnt,x,y).se;
}


int main()
{
	fast;
	cin>>n>>s>>q>>e;
	fo(i,1,n-1)
	{
		ll a,b,c;
		cin>>a>>b>>c;
		v[a].pb({b,{c,i}});
		v[b].pb({a,{c,i}});
		p[i].fi=a;
		p[i].se=b;
	}
	fo(i,1,s)
	{
		int a;
		cin>>a;
	}

	pre();
	// cout<<endl;
	// cout<<cnt<<endl;
	// fo(i,1,cnt)
	// cout<<tuttur[i]<<sp;


	// cout<<endl;
	// cout<<endl;
	// cout<<endl;

	fo(i,1,q)
	{
		int a,b;
		cin>>b>>a;
		ll x=p[b].fi;
		ll y=p[b].se;
		// cout<<a<<sp<<x<<sp<<y<<endl;
		// cout<<lca(a,x)<<sp<<lca(a,y)<<endl<<endl;
		if(lca(a,x)==x && lca(a,y)==y)
			cout<<0<<endl;
		else
			cout<<"escaped"<<endl;
	}

}



/*     cd onedrive\desktop\kod
cls

Sinav:21-22 aralik
Aciklama: Muhtemelen 25 aralik
*/

Compilation message (stderr)

valley.cpp: In function 'void f(int, long long int)':
valley.cpp:72:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<v[ind].size();i++)
              ~^~~~~~~~~~~~~~
valley.cpp:75:6: warning: unused variable 'b' [-Wunused-variable]
   ll b=v[ind][i].se.fi;
      ^

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