Submission #144304

#	Time	Username	Problem	Language	Result	Execution time	Memory
144304		Evirir	Valley (BOI19_valley)	C++17	23 / 100	251 ms	24440 KiB

valley

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define watch(x) cout<<(#x)<<"="<<(x)<<endl
#define mset(d,val) memset(d,val,sizeof(d))
#define setp(x) cout<<fixed<<setprecision(x)
#define forn(i,a,b) for(int i=a;i<b;i++)
#define fore(i,a,b) for(int i=a;i<=b;i++)
#define pb push_back
#define F first
#define S second
#define PI 3.14159265358979323846264338327
#define INF 2e14
#define MOD 998244353
#define pqueue priority_queue
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef unsigned long long ull;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;

#define MAXN 100005
#define LG 18

int n,s,q,e;
bool shop[MAXN];
vii adj[MAXN];
ii edges[MAXN];

int depth[MAXN],prt[MAXN][LG+1];

void dfs_prt(int u,int p){
	prt[u][0]=p;
	forn(j,1,LG){
		if(prt[u][j-1]!=-1) prt[u][j]=prt[prt[u][j-1]][j-1];
	}
	for(ii tmp: adj[u]){
		int v=tmp.F;
		if(v==p) continue;
		depth[v]=depth[u]+1;
		dfs_prt(v,u);
	}
}

ll dist[MAXN];
void dfs(int u,int p,int xu,int xv){
	for(ii tmp: adj[u]){
		int v=tmp.F; ll w=tmp.S;
		if(v==p) continue;
		if((u==xu&&v==xv)||(u==xv&&v==xu)) continue;
		dist[v]=dist[u]+w;
		dfs(v,u,xu,xv);
	}
}

bool findprt(int u,int v){
	for(int i=LG-1;i>=0;i--){
		if(prt[u][i]!=-1&&depth[prt[u][i]]>=depth[v]) u=prt[u][i];
	}
	return u==v;
}

void S2()
{
	forn(it,0,q)
	{
		int xe,b; cin>>xe>>b; xe--; b--;
		int xu=edges[xe].F, xv=edges[xe].S;
		forn(i,0,n) dist[i]=INF;
		dist[b]=0;
		
		dfs(b,-1,xu,xv);
		
		ll minn = INF;
		forn(i,0,n){
			if(shop[i]) minn=min(minn,dist[i]);
		}
		
		if(dist[e]<INF) cout<<"escaped"<<'\n';
		else if(minn<INF) cout<<minn<<'\n';
		else cout<<"oo"<<'\n';
	}
}

void S3()
{
	forn(it,0,q)
	{
		int xe,b; cin>>xe>>b; xe--; b--;
		int xu=edges[xe].F,xv=edges[xe].S;
		
		if(depth[xu]<depth[xv]) swap(xu,xv); //xu is the lower end
		if(depth[b]<depth[xu]){
			cout<<"escaped"<<'\n';
			continue;
		}
		if(depth[b]==depth[xu]){
			if(b==xu) cout<<0<<'\n';
			else cout<<"escaped"<<'\n';
			continue;
		}
		
		if(findprt(b,xu)) cout<<0<<'\n';
		else cout<<"escaped"<<'\n';
	}
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	mset(prt,-1);
	
	cin>>n>>s>>q>>e; e--;
	forn(i,0,n-1){
		int u,v; ll w;
		cin>>u>>v>>w; u--; v--;
		adj[u].pb({v,w});
		adj[v].pb({u,w});
		edges[i]={u,v};
	}
	
	forn(i,0,s){
		int u; cin>>u; u--;
		shop[u]=true;
	}
	
	dfs_prt(e,-1);
	
	if(n<=1000&&q<=1000) S2();
	else S3();
	
	return 0;
}

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