Submission #1093322

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093322		emptypringlescan	Valley (BOI19_valley)	C++17	100 / 100	142 ms	47436 KiB

valley

#include <bits/stdc++.h>
using namespace std;
#define int long long
struct node{
	int s,e,m;
	long long val;
	node *l,*r;
	node(int S, int E){
		s=S; e=E; m=(s+e)/2;
		val=1e16;
		if(s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
		else l=r=NULL;
	}
	void update(int S, long long V){
		if(s==e){
			val=V;
			return;
		}
		if(S<=m) l->update(S,V);
		else r->update(S,V);
		val=min(l->val,r->val);
	}
	long long query(int S, int E){
		if(S<=s&&e<=E) return val;
		if(E<=m) return l->query(S,E);
		else if(S>m) return r->query(S,E);
		else return min(l->query(S,m),r->query(m+1,E));
	}
} *root;
vector<pair<int,long long> > adj[100005];
pair<int,int> edge[100005];
vector<pair<int,int> > qu[100005];
long long ans[100005],uwu[100005];
int shop[100005],pre[100005],pos[100005],dep[100005],dist[100005],cnt;
void onk(int x, int p){
	cnt++;
	pre[x]=cnt;
	for(auto i:adj[x]) if(i.first!=p) dist[i.first]=dist[x]+i.second,dep[i.first]=dep[x]+1,onk(i.first,x);
	pos[x]=cnt;
}
long long dfs(int x, int p){
	long long clos=1e16;
	for(auto i:adj[x]){
		if(i.first!=p){
			long long kid=dfs(i.first,x)+i.second;
			clos=min(clos,kid);
		}
	}
	if(shop[x]) clos=0;
	uwu[x]=clos;
	return clos;
}
void sadsad(int x, int p){
	root->update(dep[x],uwu[x]-dist[x]);
	for(auto i:qu[x]){
		ans[i.second]=root->query(i.first,dep[x])+dist[x];
	}
	for(auto i:adj[x]){
		if(i.first!=p){
			sadsad(i.first,x);
		}
	}
}
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,s,q,e;
	cin >> n >> s >> q >> e;
	for(int i=0; i<n-1; i++){
		int a,b;
		long long c;
		cin >> a >> b >> c;
		adj[a].push_back({b,c});
		adj[b].push_back({a,c});
		edge[i+1]={a,b};
	}
	for(int i=0; i<s; i++){
		int x;
		cin >> x;
		shop[x]=1;
	}
	onk(e,-1);
	for(int i=1; i<n; i++) if(dep[edge[i].first]<dep[edge[i].second]) swap(edge[i].first,edge[i].second);
	for(int i=0; i<q; i++){
		int a,b;
		cin >> a >> b;
		if(pre[edge[a].first]<=pre[b]&&pos[edge[a].first]>=pos[b]){
			qu[b].push_back({dep[edge[a].first],i});
		}
		else ans[i]=-1;
	}
	root=new node(0,100005);
	dfs(e,-1);
	sadsad(e,-1);
	for(int i=0; i<q; i++){
		if(ans[i]==-1) cout << "escaped\n";
		else if(ans[i]>=1e16) cout << "oo\n";
		else cout << ans[i] << '\n',assert(ans[i]>=0LL);
	}
}

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