Submission #1276103

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276103		WH8	Valley (BOI19_valley)	C++20	100 / 100	279 ms	42752 KiB

valley

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

#define int long long 
#define pll pair<int, int>
#define mp make_pair
#define pb push_back
#define f first
#define s second

int n,q,s,e;
vector<vector<pair<int,int>>> al(100005);
vector<bool> shop(100005, 0), inpath(100005, 0);
vector<int> ans(100005, 0),len(100005, 0),dist(100005, 1e15), dep(100005, 0), par(100005, 0);
vector<vector<pair<int,int>>> qry(100005);
void calc(int x, int pind){
	for(auto [to, ind]:al[x]){
		if(ind==pind)continue;
		dep[ind]=dep[pind]+1;
		par[to]=ind;
		calc(to, ind);
		dist[x]=min(dist[x], dist[to]+len[ind]);
	}
	if(shop[x])dist[x]=0;
}

struct node{
	int s,e,m,lz,v;
	node *l, *r;
	node (int S,int E){
		s=S,e=E,m=(s+e)/2,lz=0,v=0;
		if(s!=e){
			l=new node(s, m);
			r=new node(m+1, e);
		}
	}
	void prop(){
		if(s==e or lz==0)return;
		l->v+=lz, r->v+=lz, r->lz += lz, l->lz += lz;
		lz=0;
	}
	void rangeadd(int S,int E, int V){
		prop();
		if(S<=s and e<=E){
			v+=V;
			lz+=V;
			return;
		}
		prop();
		if(E <= m)l->rangeadd(S, E, V);
		else if(S > m)r->rangeadd(S, E, V);
		else l->rangeadd(S,m, V), r->rangeadd(m+1, E, V);
		v=min(l->v, r->v);
	}
	int rangemin(int S, int E){
		prop();
		if(S<=s and e<=E){
			return v;
		}
		prop();
		if(E <= m)return l->rangemin(S, E);
		else if(S>m)return r->rangemin(S,E);
		return min(l->rangemin(S, m), r->rangemin(m+1, E));
	}
} *root;
	
void dfs(int x, int pind){
	// enter
	root->rangeadd(0, max(0ll, dep[pind]-1), len[par[x]]);
	root->rangeadd(dep[pind], dep[pind], dist[x]);
	//~ printf("at %lld, dep of pind is %lld, len is %lld, added to %lld, value%lld\n",
	//~ x, dep[par[x]], len[par[x]], dep[pind], dist[x]);
	//~ assert(pind==par[x]);
	//~ for(int i=0;i<n;i++){
		//~ cout<<root->rangemin(i, i)<<" ";
	//~ }
	//~ cout<<endl;
	inpath[pind]=true;
	for(auto [ind, cutind]:qry[x]){
		//ans[ind]
		if(inpath[cutind]){
			ans[ind]=root->rangemin(dep[cutind], dep[pind]);
		}
		else {
			ans[ind]=-1; 
		}
	}
	for(auto [to, ind]:al[x]){
		if(ind==pind)continue;
		dfs(to, ind);
	}
	root->rangeadd(0, max(0ll, dep[pind]-1), -len[par[x]]);
	root->rangeadd(dep[pind], dep[pind], -dist[x]);
	//~ printf("leaving %lld, dep of pind is %lld, len is %lld, minusing indiv to %lld, value%lld\n",
	//~ x, dep[par[x]], len[par[x]], dep[pind], dist[x]);

	inpath[pind]=false;
}
	
signed main(){
	cin>>n>>s>>q>>e;
	root=new node(0, n);
	for(int i=1;i<n;i++){
		int a,b,w;cin>>a>>b>>w;
		len[i]=w;
		al[a].pb({b, i});
		al[b].pb({a, i});
	}
	for(int i=0;i<s;i++){
		int k;cin>>k;shop[k]=true;
	}
	for(int i=0;i<q;i++){
		int cutind, x;cin>>cutind>>x;
		qry[x].pb({i, cutind});
	}
	calc(e, 0);
	dfs(e, 0);
	//~ for(int i=1;i<=n;i++){
		//~ cout<<dist[i]<<" ";
	//~ }cout<<endl;
	for(int i=0;i<q;i++){
		if(ans[i] >= 1e15){
			cout<<"oo\n";
		}
		else if(ans[i]==-1){
			cout<<"escaped\n";
		}
		else {
			cout<<ans[i]<<"\n";
		}
	}
}		

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