Submission #1091600

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091600		4QT0R	Valley (BOI19_valley)	C++17	100 / 100	1816 ms	122260 KiB

valley

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>

vector<pll> graph[100003];
pll edges[100003];
ll pre_order[100003];
ll post_order[100003];
ll iter=0;
ll dep[100003];

vector<pll> query[100003];
ll ans[100003];

bool shop[100003];
ll down[100003];
ll oo=1e18;

void dfs1(ll v, ll p){
	pre_order[v]=iter++;
	down[v]=oo;
	dep[v]=dep[p]+1;
	if (shop[v])down[v]=0;
	for (auto [u,c] : graph[v]){
		if (u==p)continue;
		dfs1(u,v);
		down[v]=min(down[v],c+down[u]);
	}
	post_order[v]=iter++;
}

bool fat(ll v, ll u){
	return (pre_order[v]<=pre_order[u] && post_order[v]>=post_order[u]);
}

vector<pll> path;
ll sm=0;

void solve(ll v, ll par){
	for (auto [ind,i] : query[v]){
		ll u=edges[ind].second;
		if (!fat(u,v)){
			ans[i]=-1;
			continue;
		}
		if (path.empty() || path.back().first<dep[u]){
			ans[i]=oo;
			continue;
		}
		ll l=0,p=path.size()-1,md;
		while(l<p){
			md=(l+p)/2;
			if (path[md].first>=dep[u])p=md;
			else l=md+1;
		}
		ans[i]=path[l].second+sm;
	}
	stack<pll> st;
	for (auto [u,c] : graph[v]){
		if (u==par)continue;
		sm+=c;
		while(path.size() && (path.back().second+sm>=down[u])){
			st.push(path.back());
			path.pop_back();
		}
		if (down[u]!=oo){
			path.push_back({dep[u],down[u]-sm});
		}
		solve(u,v);
		if (down[u]!=oo){
			path.pop_back();
		}
		sm-=c;
		for(;st.size();st.pop())path.push_back(st.top());
	}
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	ll n,s,q,e;
	cin >> n >> s >> q >> e;
	for (ll i = 1,v,u,d; i<n; i++){
		cin >> v >> u >> d;
		edges[i]={v,u};
		graph[v].push_back({u,d});
		graph[u].push_back({v,d});
	}
	for (ll i = 1,v; i<=s; i++){
		cin >> v;
		shop[v]=true;
	}
	dfs1(e,0);
	for (ll i = 1; i<n; i++)if (fat(edges[i].second,edges[i].first))swap(edges[i].first,edges[i].second);
	for (ll i = 1,ind,v; i<=q; i++){
		cin >> ind >> v;
		query[v].push_back({ind,i});
	}
	solve(e,-1);
	for (ll i = 1; i<=q; i++){
		if (ans[i]==-1)cout << "escaped\n";
		else if (ans[i]==oo)cout << "oo\n";
		else cout << ans[i] << '\n';
	}
}

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