Submission #545805

#	Time	Username	Problem	Language	Result	Execution time	Memory
545805		jamezzz	Valley (BOI19_valley)	C++17	100 / 100	2930 ms	227852 KiB

valley

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

#ifdef DEBUG
#define dbg(...) printf(__VA_ARGS__);
#define getchar_unlocked getchar
#else
#define dbg(...)
#endif
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)x.size()
#define mnto(x,y) x=min(x,(__typeof__(x))y)
#define mxto(x,y) x=max(x,(__typeof__(x))y)
#define INF 1023456789
#define LINF 1023456789123456789
#define all(x) x.begin(), x.end()
#define disc(x) sort(all(x));x.resize(unique(all(x))-x.begin());
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<int, ll> il;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<pll> vll;
mt19937 rng(time(0));

#define mod 1000000007

inline int add(int a,int b){
	int r=a+b;
	while(r>=mod)r-=mod;
	while(r<0)r+=mod;
	return r;
}

inline int mult(int a,int b){
	return (int)(((ll)(a*b))%mod);
}

inline int rd(){
	int x=0;
	char ch=getchar_unlocked();
	while(!(ch&16))ch=getchar();//keep reading while current character is whitespace
    while(ch&16){//this will break when ‘\n’ or ‘ ‘ is encountered
		x=(x<<3)+(x<<1)+(ch&15);
		ch=getchar_unlocked();
	}
	return x;
}

#define maxn 100005

struct node{
	int n;
	vector<ll> lz;
	vector<il> v;
	void init(int _n){
		n=_n;
		v.resize(4*n,{0,0});
		lz.resize(4*n,0);
	}
	void ppo(int i,int s,int e){
		v[i].se+=lz[i];
		if(s!=e){
			lz[2*i+1]+=lz[i];
			lz[2*i+2]+=lz[i];
		}
		lz[i]=0;
	}
	void up(int i,int s,int e,int x,int y,ll nv){
		if(s==x&&e==y){
			lz[i]+=nv;return;
		}
		int m=(s+e)>>1;
		if(y<=m)up(2*i+1,s,m,x,y,nv);
		else if(x>m)up(2*i+2,m+1,e,x,y,nv);
		else up(2*i+1,s,m,x,m,nv),up(2*i+2,m+1,e,m+1,y,nv);
		ppo(2*i+1,s,m);ppo(2*i+2,m+1,e);
		v[i]=min(v[2*i+1],v[2*i+2]);
	}
	void up(int x,int y,ll nv){
		up(0,0,n-1,x,y,nv);
	}
	void set(int i,int s,int e,int x,int t){
		if(s==x&&e==x){
			v[i].fi=t;return;
		}
		int m=(s+e)>>1;
		if(x<=m)set(2*i+1,s,m,x,t);
		else set(2*i+2,m+1,e,x,t);
		ppo(2*i+1,s,m);ppo(2*i+2,m+1,e);
		v[i]=min(v[2*i+1],v[2*i+2]);
	}
	void set(int x,int t){
		set(0,0,n-1,x,t);
	}
	il qry(int i,int s,int e,int x,int y){
		ppo(i,s,e);
		if(s==x&&e==y)return v[i];
		int m=(s+e)>>1;
		if(y<=m)return qry(2*i+1,s,m,x,y);
		if(x>m)return qry(2*i+2,m+1,e,x,y);
		return min(qry(2*i+1,s,m,x,m),qry(2*i+2,m+1,e,m+1,y));
	}
	il qry(int x,int y){
		if(x>y)return {2,LINF};
		return qry(0,0,n-1,x,y);
	}
}seg[maxn];

int n,q,s,e,w[maxn],sub[maxn];
vii AL[maxn];
bool shop[maxn],done[maxn];
vi nodeComp[maxn],edgeComp[maxn];
vii nodeRange[maxn],edgeRange[maxn];
ii block[maxn];
int cnt;

void calc(int u,int p){
	sub[u]=1;
	for(auto[v,i]:AL[u]){
		if(v==p||done[v])continue;
		calc(v,u);
		sub[u]+=sub[v];
	}
}

void dfs(int u,int p,int c){
	ii rng={cnt,cnt};++cnt;
	for(auto[v,i]:AL[u]){
		if(v==p||done[v])continue;
		dfs(v,u,c);
		ii tmp=nodeRange[v].back();
		rng.se=max(rng.se,tmp.se);
		edgeComp[i].pb(c);
		edgeRange[i].pb(tmp);
	}
	nodeComp[u].pb(c);
	nodeRange[u].pb(rng);
}

void decomp(int u){
	calc(u,-1);
	int c=u;
	while(true){
		bool val=true;
		for(auto[v,i]:AL[c]){
			if(done[v])continue;
			if(sub[v]<sub[c]&&sub[v]>sub[u]/2){
				c=v;val=false;
			}
		}
		if(val)break;
	}
	
	cnt=0;
	dfs(c,-1,c);
	seg[c].init(cnt);
	
	done[c]=true;
	for(auto[v,i]:AL[c]){
		if(!done[v])decomp(v);
	}
}

int main(){
	n=rd();s=rd();q=rd();e=rd();
	for(int i=1;i<n;++i){
		int a=rd(),b=rd();
		w[i]=rd();
		AL[a].pb({b,i});
		AL[b].pb({a,i});
	}
	for(int i=0;i<s;++i){
		int c=rd();
		shop[c]=true;
	}
	
	decomp(1);
	
	for(int i=1;i<n;++i){
		for(int j=0;j<sz(edgeComp[i]);++j){
			int c=edgeComp[i][j];
			ii r=edgeRange[i][j];
			seg[c].up(r.fi,r.se,w[i]);
		}
	}
	for(int i=1;i<=n;++i){
		for(int j=0;j<sz(nodeComp[i]);++j){
			int c=nodeComp[i][j];
			ii r=nodeRange[i][j];
			if(i==e)seg[c].set(r.fi,0);
			else if(shop[i])seg[c].set(r.fi,1);
			else seg[c].set(r.fi,2);
		}
	}
	
	for(int i=1;i<=n;++i)block[i]={seg[i].n,-1};
	
	for(int i=0;i<q;++i){
		int x=rd(),s=rd();
		
		for(int i=0;i<sz(edgeComp[x]);++i){
			block[edgeComp[x][i]]=edgeRange[x][i];
		}
		
		ll ans=LINF;
		for(int i=0;i<sz(nodeComp[s]);++i){
			int c=nodeComp[s][i];
			ii r=nodeRange[s][i];
			if(block[c].fi<=r.fi&&r.fi<=block[c].se)continue;//path to this is blocked
			il d1=seg[c].qry(r.fi,r.fi);
			if(d1.fi==0)ans=-1;
			else if(d1.fi==1)ans=min(ans,0ll);
			il d2=min(seg[c].qry(0,block[c].fi-1),seg[c].qry(block[c].se+1,seg[c].n-1));
			if(d2.fi==0)ans=-1;
			else if(d2.fi==1)ans=min(ans,d1.se+d2.se);
		}
		
		for(int i=0;i<sz(edgeComp[x]);++i){
			int c=edgeComp[x][i];
			block[c]={seg[c].n,-1};
		}
		
		if(ans==LINF)pf("oo\n");
		else if(ans==-1)pf("escaped\n");
		else pf("%lld\n",ans);
	}
}

/*
5 2 3 1
1 2 3
1 3 2
3 4 1
3 5 2
2
4
2 2
2 5
4 5
*/

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