Submission #646256

#	Time	Username	Problem	Language	Result	Execution time	Memory
646256		ymm	Valley (BOI19_valley)	C++17	32 / 100	817 ms	22484 KiB

valley

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 100'010;
vector<pii> query[N];
int lower_v[N];
vector<pii> A[N];
ll w[N];
double near_st[N];
double near_child[N];
double height[N];
int st[N], ft[N];
bool has_shop[N];
ll ans[N];
int n, q, cnt_shops, rt;

void dfs1(int v, int p, int &t, double h)
{
	st[v] = t++;
	height[v] = h;
	for (auto [u, e] : A[v]) {
		if (u == p)
			continue;
		lower_v[e] = u;
		dfs1(u, v, t, h + w[e]);
	}
	ft[v] = t;
}

__attribute__((optimize("O3,unroll-loops"),target("avx")))
void update(int l, int r, double x)
{
	Loop (i,l,r)
		near_st[i] = near_st[i] < x? near_st[i]: x;
}

void up_near(int v, int p)
{
	near_child[v] = has_shop[v]? 0: 1e100;
	vector<int> vec;
	vector<double> vec_min_suf;
	for (auto [u, e] : A[v]) {
		if (u == p)
			continue;
		near_child[u] += w[e];
		near_child[v] = min(near_child[v], near_child[u]);
		vec.push_back(u);
	}
	vec_min_suf.resize(vec.size(), 1e100);
	Loop (i,1,vec.size())
		vec_min_suf[i-1] = min(vec_min_suf[i], near_child[vec[i]]);
	double cur_min = has_shop[v]? 0: 1e100;
	Loop (i,0,vec.size()) {
		int u = vec[i];
		double mn = min(cur_min, vec_min_suf[i]);
		update(st[u], ft[u], mn - height[v]);
		cur_min = min(cur_min, near_child[u]);
	}
	near_st[st[v]] = near_child[v] - height[v];
}

void ans_queries(int v)
{
	for (auto [i, u] : query[v]) {
		if (st[u] < st[v] || ft[v] <= st[u])
			ans[i] = -2;
		else if (near_st[st[u]] > 1e20)
			ans[i] = -1;
		else
			ans[i] = near_st[st[u]] + height[u];
	}
}

void dfs2(int v, int p)
{
	for (auto [u, e] : A[v]) {
		if (u != p)
			dfs2(u, v);
	}
	up_near(v, p);
	ans_queries(v);
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n >> cnt_shops >> q >> rt; --rt;
	Loop (i,0,n-1) {
		int v, u;
		cin >> v >> u >> w[i];
		--v; --u;
		A[v].push_back({u, i});
		A[u].push_back({v, i});
	}
	dfs1(rt, -1, *new int(0), 0);
	Loop (i,0,cnt_shops) {
		int v;
		cin >> v;
		has_shop[v-1] = 1;
	}
	Loop (i,0,q) {
		int e, v;
		cin >> e >> v;
		--e; --v;
		query[lower_v[e]].push_back({i, v});
	}
	dfs2(rt, -1);
	Loop (i,0,q) {
		switch (ans[i]) {
		case -2: cout << "escaped\n"; break;
		case -1: cout << "oo\n"; break;
		default: cout << ans[i] << '\n'; break;
		}
	}
}

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