Submission #1096297

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096297		boclobanchat	Valley (BOI19_valley)	C++14	100 / 100	215 ms	32852 KiB

valley

#include<bits/stdc++.h>
using namespace std;
#define ii pair<long long,long long>
#define fi first
#define se second
struct path { long long l,r,v; };
const int MAXN=1e5+5;
const long long INF=1e18;
int L[MAXN],R[MAXN],dis[MAXN],tdfs=0,n,s,q,h;
long long seg[MAXN*4],lazy[MAXN*4],ans[MAXN],D[MAXN];
path P[MAXN];
ii Q[MAXN];
vector<ii> ds[MAXN];
vector<int> vq[MAXN];
bool ck[MAXN];
void dfs(int i,int pre)
{
	L[i]=++tdfs;
	for(auto v:ds[i]) if(v.fi!=pre)
	{
		dis[v.fi]=dis[i]+1,D[v.fi]=D[i]+v.se;
		dfs(v.fi,i);
	}
	R[i]=tdfs;
}
void down(int pos)
{
	long long val=lazy[pos];
	seg[pos*2]+=val,seg[pos*2+1]+=val;
	lazy[pos*2]+=val,lazy[pos*2+1]+=val,lazy[pos]=0;
}
void update(int l,int r,int u,int v,long long val,int pos)
{
	if(v<l||r<u) return ;
	if(u<=l&&r<=v)
	{
		seg[pos]+=val,lazy[pos]+=val;
		return ;
	}
	int mid=(l+r)/2;
	down(pos);
	update(l,mid,u,v,val,pos*2);
	update(mid+1,r,u,v,val,pos*2+1);
	seg[pos]=min(seg[pos*2],seg[pos*2+1]);
}
long long get(int l,int r,int u,int v,int pos)
{
	if(u<=l&&r<=v) return seg[pos];
	int mid=(l+r)/2;
	down(pos);
	if(v<=mid) return get(l,mid,u,v,pos*2);
	if(mid+1<=u) return get(mid+1,r,u,v,pos*2+1);
	return min(get(l,mid,u,v,pos*2),get(mid+1,r,u,v,pos*2+1));
}
long long inr(int l,int r) { return get(1,n,l,r,1); }
long long onr(int l,int r)
{
	long long ans=INF;
	if(l>1) ans=min(ans,get(1,n,1,l-1,1));
	if(r<n) ans=min(ans,get(1,n,r+1,n,1));
	return ans;
}
bool check(int a,int b) { return L[a]<=L[b]&&R[b]<=R[a]; }
void dfsus(int i,int pre)
{
	for(auto v:vq[i])
	{
		int p=Q[v].fi,a=P[p].l,b=P[p].r;
		if(dis[a]<dis[b]) swap(a,b);
		if((check(a,h)^check(a,i))==0) ans[v]=-1;
		else if(check(a,i)) ans[v]=inr(L[a],R[a]);
		else ans[v]=onr(L[a],R[a]);
	}
	for(auto v:ds[i]) if(v.fi!=pre)
	{
		update(1,n,1,n,v.se,1);
		update(1,n,L[v.fi],R[v.fi],-v.se*2,1);
		dfsus(v.fi,i);
		update(1,n,1,n,-v.se,1);
		update(1,n,L[v.fi],R[v.fi],v.se*2,1);
	}
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>s>>q>>h;
    for(int i=1;i<n;i++)
    {
    	int l,r,v;
    	cin>>l>>r>>v;
    	ds[l].push_back({r,v}),ds[r].push_back({l,v}),P[i]={l,r,v};
	}
	dfs(1,1);
	for(int i=1;i<=s;i++)
	{
		int res;
		cin>>res;
		ck[res]=true;
	}
	for(int i=1;i<=n;i++) if(ck[i]) update(1,n,L[i],L[i],D[i],1);
	else update(1,n,L[i],L[i],INF,1);
	for(int i=1;i<=q;i++)
	{
		cin>>Q[i].fi>>Q[i].se;
		vq[Q[i].se].push_back(i);
	}
	dfsus(1,1);
	for(int i=1;i<=q;i++) if(ans[i]==-1) cout<<"escaped\n";
	else if(ans[i]<1e16) cout<<ans[i]<<"\n";
	else cout<<"oo\n";
}

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