Submission #1282073

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282073		hanguyendanghuy	Valley (BOI19_valley)	C++20	23 / 100	705 ms	20692 KiB

valley

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fi first
#define se second
const ll MAXN=4e5+5,INF=1e18,MOD=1e9+7,MAXV=4e5+2;
ll n,m,i,j,k,p,dem,cnt,ans,S,Q,root,dtr[MAXN],shop[MAXN],mark[MAXN],par[MAXN],dist[MAXN],chain[MAXN],headchain[MAXN],st[MAXN],en[MAXN],cntchain=1,de[MAXN],sz[MAXN];
vector<pair<ll,ll>> adj[MAXN];
pair<ll,ll> edge[MAXN];
ll dfs(ll st){
	sz[st]=1;
	for(auto x:adj[st]){
		if(de[x.fi]) continue;
		de[x.fi]=de[st]+1;
		dtr[x.fi]=dtr[st]+x.se;
		par[x.fi]=st;
		dist[st]=min(dist[st],dfs(x.fi)+x.se);
		sz[st]+=sz[x.fi];
	}
	if(shop[st]&1)
	  dist[st]=0;
	return dist[st];
}
void HLD(ll u){
	if(!headchain[cntchain])
		headchain[cntchain]=u;
	chain[u]=cntchain;
	ll v=-1;
	for(auto x:adj[u])
		if(!chain[x.fi]&&(u==-1||sz[x.fi]>sz[v])) v=x.fi;
	if(v>0) HLD(v);
	for(auto x:adj[u]){
		if(!chain[x.fi]){
			cntchain++;
			HLD(x.fi);
		}
	} 
	en[u]=cntchain;
}
ll lca(ll u,ll v){
  while(chain[u]!=chain[v]){
      if(chain[u]>chain[v])
          u=par[headchain[chain[u]]];
      else v=par[headchain[chain[v]]];
  }
  return (de[u]<de[v]?u:v);
}
ll tinh(ll u,ll v){
  return de[u]+de[v]-2*de[lca(u,v)];
}
void check(ll u,ll st){
  ll stchain=chain[u],enchain=en[u];
  for(ll i=stchain;i<=enchain;i++){
  	if(de[par[headchain[i]]]<de[u]) continue;
    ans=min(ans,dist[par[headchain[i]]]+abs(-dtr[par[headchain[i]]]+dtr[st]));
  }
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>S>>Q>>root;
	for(i=1;i<n;i++){
		ll u,v,c;
		cin>>u>>v>>c;
		edge[i]={u,v};
		adj[u].pb({v,c});
		adj[v].pb({u,c});
	}
	for(i=1;i<=S;i++)
	  cin>>k,shop[k]=1;
	de[root]=1;
	fill(dist+1,dist+n+1,INF);
	dfs(root);
	HLD(root);
	for(i=1;i<=Q;i++){
	  ll block,E;
	  cin>>block>>E;
	  ll u=edge[block].fi,v=edge[block].se;
	  if(de[u]<de[v]) swap(u,v);
	  if(tinh(u,E)+tinh(v,root)+1==tinh(E,root)){
	    ans=min(dist[E],dist[u]-dtr[u]+dtr[E]);
	    check(u,E);
	    if(ans>=INF){
	      cout<<"oo"<<'\n';
	    }
	    else cout<<ans<<'\n';
	  }
	  else cout<<"escaped"<<'\n';;
	}
}
	

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