Submission #943983

#	Time	Username	Problem	Language	Result	Execution time	Memory
943983		pcc	Valley (BOI19_valley)	C++17	100 / 100	778 ms	64852 KiB

valley

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

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>


const int mxn = 4e5+10;
vector<pii> t1[mxn],t2[mxn];
int w[mxn];
int N,S,Q,E;
pair<pii,int> req[mxn];
bitset<mxn> esc;
ll ans[mxn];
pii eid[mxn];
bitset<mxn> shop;

bool peko(pii r,int p){
	return r.fs<=p&&p<=r.sc;
}

namespace ESC{
	int pt = 0;
	pii eul[mxn];
	void dfs(int now,int par){
		eul[now].fs = ++pt;
		for(auto nxt:t1[now]){
			if(nxt.fs == par)continue;
			dfs(nxt.fs,now);
		}
		eul[now].sc = pt;
	}
	void GO(){
		dfs(E,E);
		esc.set();
		for(int i = 1;i<=Q;i++){
			auto [a,b] = req[i].fs;
			auto c = req[i].sc;
			if(peko(eul[a],eul[c].fs)&&peko(eul[b],eul[c].fs))esc[i] = false;
		}
		return;
	}
}


const ll inf = 1e14;
namespace CD{
	bitset<mxn> del;
	int sz[mxn];
	ll dep[mxn];
	pii eul[mxn];
	int pt;
	vector<array<int,3>> ask[mxn];
	pll seg[mxn*4];
	void modify(int now,int l,int r,int s,int e,ll v){
		if(l>=s&&e>=r){
			seg[now].sc += v;
			return;
		}
		int mid = (l+r)>>1;
		if(mid>=s)modify(now*2+1,l,mid,s,e,v);
		if(mid<e)modify(now*2+2,mid+1,r,s,e,v);
		seg[now].fs = min(seg[now*2+1].fs+seg[now*2+1].sc,seg[now*2+2].fs+seg[now*2+2].sc);
		return;
	}
	int szdfs(int now,int par){
		sz[now] = 1;
		for(auto nxt:t1[now]){
			if(nxt.fs == par||del[nxt.fs])continue;
			sz[now] += szdfs(nxt.fs,now);
		}
		return sz[now];
	}
	int find_centroid(int now,int par,int tar){
		for(auto nxt:t1[now]){
			if(nxt.fs == par||del[nxt.fs])continue;
			if(sz[nxt.fs]>tar)return find_centroid(nxt.fs,now,tar);
		}
		return now;
	}
	void dfs(int now,int par){
		eul[now].fs = ++pt;
		if(shop[now])modify(0,1,N,eul[now].fs,eul[now].fs,dep[now]-inf);
		for(auto nxt:t1[now]){
			if(nxt.fs == par||del[nxt.fs])continue;
			dep[nxt.fs] = dep[now]+nxt.sc;
			dfs(nxt.fs,now);
		}
		eul[now].sc = pt;
		return;
	}
	void dfs1(int now,int par){
		//cerr<<"DFS1:"<<now<<endl;
		for(auto [a,b,id]:ask[now]){
			if(peko(eul[a],eul[now].fs)&&peko(eul[b],eul[now].fs))continue;
			if(peko(eul[b],eul[a].fs))swap(a,b);
			if(eul[a].fs != -1&&eul[b].fs != -1)modify(0,1,N,eul[b].fs,eul[b].sc,inf);
			ans[id] = min(ans[id],dep[now]+seg[0].fs+seg[0].sc);
			if(eul[a].fs != -1&&eul[b].fs != -1)modify(0,1,N,eul[b].fs,eul[b].sc,-inf);
		}
		for(auto nxt:t1[now]){
			if(nxt.fs == par||del[nxt.fs])continue;
			dfs1(nxt.fs,now);
		}
		return;
	}
	void dfs2(int now,int par){
		//cerr<<"DFS2:"<<now<<endl;
		if(shop[now])modify(0,1,N,eul[now].fs,eul[now].fs,-dep[now]+inf);
		eul[now].fs = eul[now].sc = -1;
		for(auto nxt:t1[now]){
			if(nxt.fs == par||del[nxt.fs])continue;
			dfs2(nxt.fs,now);
		}
		return;
	}
	void CD(int now){
		//cerr<<"CD:"<<now<<endl;
		szdfs(now,now);
		now = find_centroid(now,now,(sz[now]-1)/2);
		pt = 0;
		dep[now] = 0;
		dfs(now,now);
		dfs1(now,now);
		dfs2(now,now);
		del[now] = true;
		for(auto nxt:t1[now]){
			if(del[nxt.fs])continue;
			CD(nxt.fs);
		}
		return;
	}
	void GO(){
		for(int i = 1;i<=N;i++)modify(0,1,N,i,i,inf);
		for(int i = 1;i<=Q;i++){
			ans[i] = inf;
			auto [a,b] = req[i].fs;
			auto c = req[i].sc;
			ask[c].push_back(array<int,3>({a,b,i}));
		}
		CD(1);
		return;
	}
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>S>>Q>>E;
	for(int i = 1;i<N;i++){
		int a,b,c;
		cin>>a>>b>>c;
		t1[a].push_back({b,c});
		t1[b].push_back({a,c});
		eid[i] = {a,b};
	}
	for(int i = 1;i<=S;i++){
		int k;
		cin>>k;
		shop[k] = true;
	}
	for(int i = 1;i<=Q;i++){
		int id,p;
		cin>>id>>p;
		req[i] = {eid[id],p};
	}
	ESC::GO();
	CD::GO();
	for(int i = 1;i<=Q;i++){
		if(esc[i])cout<<"escaped\n";
		else if(ans[i]>=inf)cout<<"oo\n";
		else cout<<ans[i]<<'\n';
	}
	return 0;
}

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