Submission #1128943

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128943		lanplot	Valley (BOI19_valley)	C++20	100 / 100	2146 ms	256920 KiB

valley

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (100005)
ll N,S,Q,E;
ll shop[MAXN];
vector<pair<ll,ll> > v[MAXN];
ll sub[MAXN];
ll par[MAXN];
ll lvl[MAXN];
ll dist[MAXN][20]; //each node has at most 20 ancestors (dist[i][k] represents the distance between node i and its ancestor with lvl = k [i.e. the (lvl[i] - k)th ancestor of node i]
ll dfs1(ll x,ll p,ll l){
	sub[x] = 1;
	for(auto u : v[x]){
		if(u.first != p && lvl[u.first] == -1){ //unvisited
			sub[x] += dfs1(u.first,x,l);
		}
	}
	return sub[x];
}
ll dfs2(ll x,ll p,ll siz){ //siz is total size of this centroid tree 
	for(auto u : v[x]){
		if(u.first != p && lvl[u.first] == -1 && sub[u.first] > siz / 2){
			return dfs2(u.first,x,siz); //remember that siz remains constant
		}
	}
	return x;
}
void dfsdist(ll x,ll p,ll curlvl,ll curdist){
	dist[x][curlvl] = curdist;
	for(auto u : v[x]){
		if(u.first != p && lvl[u.first] == -1){ //unvisited
			dfsdist(u.first,x,curlvl,curdist + u.second);
			//Note: curlvl is unchanged since we are moving down so
			//the relative lvl has already changed
		}
	}
}
void build(ll x,ll p,ll l){
	ll siz = dfs1(x,p,l);
	ll cent = dfs2(x,p,siz);
	if(p == -1) p = cent;
	par[cent] = p;
	lvl[cent] = l;
	dfsdist(cent,-1,l,0);
	for(auto u : v[cent]){
		if(lvl[u.first] == -1){ //unvisited
			build(u.first,cent,l + 1);
		}
	}
}
ll pre[MAXN], post[MAXN], distfromroot[MAXN];
ll cnt = 0;
void dfsprepost(ll x,ll p){
	pre[x] = cnt++;
	for(auto u : v[x]){
		if(u.first != p){
			distfromroot[u.first] = distfromroot[x] + u.second;
			dfsprepost(u.first,x);
		}
	}
	post[x] = cnt - 1;
}
struct node{
	ll s,e,m,v;
	node *l, *r;
	node(ll _s,ll _e){
		s = _s;
		e = _e;
		m = (s + e) / 2;
		v = 1e18;
		if(s != e){
			l = new node(s,m);
			r = new node(m + 1,e);
		}
	}
	void update(ll x,ll nval){
		if(s == e){
			v = nval;
		}else{
			if(x > m) r -> update(x,nval);
			else l -> update(x,nval);
			v = min(l->v,r->v);
		}
	}
	ll rminq(ll x,ll y){
		if(s == x && e == y){
			return v;
		}else{
			if(x > m) return r->rminq(x,y);
			else if(y <= m) return l->rminq(x,y);
			else return min(l->rminq(x,m),r->rminq(m + 1,y));
		}
	}
} *root[MAXN];
int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);
	cin>>N>>S>>Q>>E;
	E--;
	vector<pair<pair<ll,ll>,ll> > edges;
	for(ll i = 0;i < N - 1;i++){
		ll a,b,c;
		cin>>a>>b>>c;
		a--, b--;
		v[a].push_back({b,c});
		v[b].push_back({a,c});
		edges.push_back({{a,b},c});
	}
	for(ll i = 0;i < S;i++){
		cin>>shop[i];
		shop[i]--;
	}
	for(ll i = 0;i < MAXN;i++){
		for(ll j = 0;j < 20;j++){
			dist[i][j] = 1e18;
		}
	}
	memset(lvl,-1,sizeof(lvl)); //need lvl to find dist[i][lvl]
	build(0,-1,0);
	dfsprepost(0,-1);
	ll ans[Q];
	for(ll q = 0;q < Q;q++){
		ans[q] = 1e18;
	}
	
	vector<pair<ll,ll> > ancestorof[N]; //node i is the ancestor of (pre[j],dist between nodes i and j)
	for(ll i = 0;i < N;i++){
		ll curlevel = lvl[i];
		ll curnode = i;
		while(curlevel >= 0){
			ancestorof[curnode].push_back({pre[i],dist[i][curlevel]});
			curnode = par[curnode];
			curlevel--;
		}
	}
	for(ll i = 0;i < N;i++){
		sort(ancestorof[i].begin(),ancestorof[i].end()); //to faciliate the lower_bounds later on
	}
	for(ll i = 0;i < N;i++){
		if(!ancestorof[i].empty()){
			root[i] = new node(0,ancestorof[i].size() - 1); //Note that we do not need lazy create as the total size of all N segment trees combined will definitely be <= NlogN (since each node contributes at most logN times since each node has at most logN ancestors)
		}
	}
	for(ll i = 0;i < S;i++){
		ll curlevel = lvl[shop[i]];
		ll curnode = shop[i];
		while(curlevel >= 0){
			auto it = lower_bound(ancestorof[curnode].begin(),ancestorof[curnode].end(),make_pair(pre[shop[i]],dist[shop[i]][curlevel]));
			if(it != ancestorof[curnode].end()){
				ll pos = it - ancestorof[curnode].begin();
				root[curnode] -> update(pos,dist[shop[i]][curlevel]);
			}
			curnode = par[curnode];
			curlevel--;
		}
	}
	
	for(ll q = 0;q < Q;q++){
		ll edgeind,friendnode;
		cin>>edgeind>>friendnode;
		edgeind--, friendnode--;
		ll A = edges[edgeind].first.first;
		ll B = edges[edgeind].first.second;
		ll C = edges[edgeind].second;
		if(distfromroot[A] > distfromroot[B]) swap(A,B); //B is the deeper node, block B's subtree
		
		bool friendnodeinsidesubtree = false;
		bool Exitinsidesubtree = false;
		if(pre[B] <= pre[friendnode] && pre[friendnode] <= post[B]){
			friendnodeinsidesubtree = true;
		}
		if(pre[B] <= pre[E] && pre[E] <= post[B]){
			Exitinsidesubtree = true;
		}
		if(friendnodeinsidesubtree && Exitinsidesubtree){ //both E and friendnode are inside that blocked subtree, can reach each other
			ans[q] = -1;
			continue;
		}else if(!friendnodeinsidesubtree && !Exitinsidesubtree){ //both E and friendnode are not inside that blocked subtree, can reach each other
			ans[q] = -1;
			continue;
		}
		
		if(pre[B] <= pre[friendnode] && pre[friendnode] <= post[B]){ //Case 1: the friend is living inside the blocked subtree so he is trapped inside that subtree
			ll L = pre[B];
			ll R = post[B];
			ll curlevel = lvl[friendnode];
			ll curnode = friendnode;
			while(curlevel >= 0){
				auto Lit = lower_bound(ancestorof[curnode].begin(),ancestorof[curnode].end(),make_pair(L,-1ll));
				auto Rit = lower_bound(ancestorof[curnode].begin(),ancestorof[curnode].end(),make_pair(R + 1,-1ll));
				if(Lit != ancestorof[curnode].end() && Rit != ancestorof[curnode].begin()){
					Rit--;
					ll Lpos = Lit - ancestorof[curnode].begin();
					ll Rpos = Rit - ancestorof[curnode].begin();
					ll add = root[curnode] -> rminq(Lpos,Rpos);
					ans[q] = min(ans[q],add + dist[friendnode][curlevel]);
				}
				curnode = par[curnode];
				curlevel--;
			}
		}else{ //Case 2: the friend is living outside the blocked subtree so he cannot enter that subtree
			if(pre[B] - 1 >= 0){ //handle prefix [0,pre[B] - 1]
				ll X = pre[B] - 1;
				ll curlevel = lvl[friendnode];
				ll curnode = friendnode;
				while(curlevel >= 0){
					auto Rit = lower_bound(ancestorof[curnode].begin(),ancestorof[curnode].end(),make_pair(X + 1,-1ll));
					if(Rit != ancestorof[curnode].begin()){
						Rit--;
						ll Rpos = Rit - ancestorof[curnode].begin();
						ll add = root[curnode] -> rminq(0,Rpos);
						ans[q] = min(ans[q],add + dist[friendnode][curlevel]);
					}
					curnode = par[curnode];
					curlevel--;
				}
			}
			if(post[B] + 1 <= N - 1){ //handle suffix [post[B] + 1,N - 1]
				ll X = post[B] + 1;
				ll curlevel = lvl[friendnode];
				ll curnode = friendnode;
				while(curlevel >= 0){
					auto Lit = lower_bound(ancestorof[curnode].begin(),ancestorof[curnode].end(),make_pair(X,-1ll));
					if(Lit != ancestorof[curnode].end()){
						ll Lpos = Lit - ancestorof[curnode].begin();
						ll add = root[curnode] -> rminq(Lpos,ancestorof[curnode].size() - 1);
						ans[q] = min(ans[q],add + dist[friendnode][curlevel]);
					}
					curnode = par[curnode];
					curlevel--;
				}
			}
		}
	}	
	
	for(ll q = 0;q < Q;q++){
		if(ans[q] == -1){
			cout<<"escaped"<<'\n';
		}else if(ans[q] == 1e18){
			cout<<"oo"<<'\n';
		}else{
			cout<<ans[q]<<'\n';
		}
	}
}

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