Submission #564962

#	Time	Username	Problem	Language	Result	Execution time	Memory
564962		inluminas	Valley (BOI19_valley)	C++17	100 / 100	443 ms	50496 KiB

valley

#include"bits/stdc++.h"
using namespace std;

#define ll long long
#define endl "\n"
#define fastio ios_base::sync_with_stdio(false)
#define inf LLONG_MAX
#define l first
#define r second

const int lmt=2e5+10;
int n,s,q,e,par[lmt][20],a[lmt],idx,lvl[lmt];
vector<pair<ll,ll>>adj[lmt];
vector<pair<int,int>>ed,Q[lmt];
array<int,2>id[lmt];
bool ok[lmt];
ll mn[3*lmt],Val[lmt],ans[lmt],lazy[lmt*3];

void build(int at,int L,int R){
	if(L==R){
		mn[at]=Val[L];
		return;
	}
	int mid=(L+R)>>1;
	build(at*2,L,mid);
	build(at*2+1,mid+1,R);
	mn[at]=min(mn[at*2],mn[at*2+1]);
}

void propagate(int at,int L,int R){
	mn[at]+=lazy[at];
	if(L==R){
		lazy[at]=0;
		return;
	}
	lazy[at*2]+=lazy[at],lazy[at*2+1]+=lazy[at],lazy[at]=0;
	return;
}

void updet(int at,int L,int R,int l,int r,ll val){
	propagate(at,L,R);
	if(r<L || R<l || r<l) return;
	if(l<=L && R<=r){
		lazy[at]+=val;
		propagate(at,L,R);
		return;
	}
	int mid=(L+R)>>1;
	updet(at*2,L,mid,l,r,val);
	updet(at*2+1,mid+1,R,l,r,val);
	mn[at]=min(mn[at*2],mn[at*2+1]);
}

ll query(int at,int L,int R,int l,int r){
	propagate(at,L,R);
	if(r<L || R<l || r<l) return (ll)1e16;
	if(l<=L && R<=r) return mn[at];
	int mid=(L+R)>>1;
	return min(query(at*2,L,mid,l,r),query(at*2+1,mid+1,R,l,r));
}

void dfs(int u,int p){
	a[++idx]=u;
	for(auto [v,w]:adj[u]){
		if(v==p) continue;
		par[v][0]=u,lvl[v]=lvl[u]+1;
		dfs(v,u);
	}
	a[++idx]=u;
}

void dfS(int u,int p,ll val){
	if(ok[u]){
		Val[id[u][0]]=val,Val[id[u][1]]=val;
	}else{
		Val[id[u][0]]=1e16,Val[id[u][1]]=1e16;
	}

	for(auto [v,w]:adj[u]){
		if(v==p) continue;
		ll val2=val+w;
		dfS(v,u,val2);
	}
}

ll lca(ll p,ll q){
  if(lvl[p]<lvl[q]) swap(p,q);
  for(ll i=19;i>=0;i--){
    if(lvl[p]-(1<<i)>=lvl[q]){
      p=par[p][i];
    }
  }
  if(p==q) return p;
  for(ll i=19;i>=0;i--){
    if(par[p][i]!=-1 && par[p][i]!=par[q][i]){
      p=par[p][i],q=par[q][i];
    }
  }
  return par[p][0];
}

ll Up(ll p,ll val){
	for(ll j=19;j>=0;j--){
		if(val>=(1<<j) && par[p][j]!=-1){
			p=par[p][j];
			val-=(1<<j);
		}
	}
	return p;
}

bool yes(ll o,ll p,ll q){
	ll l=lca(p,q);
 
	if(lvl[l]<=lvl[o] && lvl[o]<=lvl[p] && o==Up(p,lvl[p]-lvl[o])) return true;
	else if(lvl[l]<=lvl[o] && lvl[o]<=lvl[q] && o==Up(q,lvl[q]-lvl[o])) return true;
	return false;
}

void Dfs(int u,int p){
	for(auto [ID,i]:Q[u]){
		int U=ed[ID-1].l,V=ed[ID-1].r;

		if(!yes(U,u,e) || !yes(V,u,e)){
			ans[i]=-1;
			continue;
		}

		if(yes(U,1,u) && yes(V,1,u)){
			if(lvl[U]<lvl[V]) swap(U,V);

			updet(1,1,n+n,1,n+n,2e15);
			updet(1,1,n+n,id[U][0],id[U][1],-2e15);

			ans[i]=query(1,1,n+n,1,n+n);

			updet(1,1,n+n,1,n+n,-2e15);
			updet(1,1,n+n,id[U][0],id[U][1],2e15);
		}else{
			if(lvl[U]<lvl[V]) swap(U,V);

			updet(1,1,n+n,id[U][0],id[U][1],2e15);

			ans[i]=query(1,1,n+n,1,n+n);

			updet(1,1,n+n,id[U][0],id[U][1],-2e15);
		}
	}

	for(auto [v,w]:adj[u]){
		if(v==p) continue;

		updet(1,1,n+n,1,n+n,w);
		updet(1,1,n+n,id[v][0],id[v][1],-w-w);

		Dfs(v,u);

		updet(1,1,n+n,id[v][0],id[v][1],+w+w);
		updet(1,1,n+n,1,n+n,-w);
	}
}

int main(){
	fastio;

	cin>>n>>s>>q>>e;
	for(int i=0;i<=n;i++){
		for(int j=0;j<20;j++) par[i][j]=-1;
	}
	for(int i=1;i<n;i++){
		ll u,v,w;
		cin>>u>>v>>w;
		adj[u].push_back({v,w});
		adj[v].push_back({u,w});
		ed.push_back({u,v});
	}
	dfs(1,0);

	for(int i=1;i<=s;i++){
		int x;
		cin>>x;
		ok[x]=1;
	}

	for(int i=1;i<=n+n;i++){
		if(id[a[i]][0]) id[a[i]][1]=i;
		else id[a[i]][0]=i;
	}

	dfS(1,0,0);

	for(int i=1;i<=q;i++){
		int ID,u;
		cin>>ID>>u;

		Q[u].push_back({ID,i});
	}

	for(int j=1;j<20;j++){
		for(int i=1;i<=n;i++){
			if(par[i][j-1]==-1) continue;
			par[i][j]=par[par[i][j-1]][j-1];
		}
	}

	build(1,1,n+n);

	Dfs(1,0);

	for(int i=1;i<=q;i++){
		if(ans[i]==-1){
			cout<<"escaped"<<endl;
			continue;
		}

		if(ans[i]>1e15) cout<<"oo"<<endl;
		else cout<<ans[i]<<endl;
	}

	return 0;
}

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