Submission #646260

#	Time	Username	Problem	Language	Result	Execution time	Memory
646260		ymm	Valley (BOI19_valley)	C++17	100 / 100	867 ms	23892 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_m_height_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_m_height_st[i] = near_m_height_st[i] < x?
		                      near_m_height_st[i]: x;
	}
}

void up_near(int v, int p)
{
	near_child[v] = has_shop[v]? 0: 1e100;
	for (auto [u, e] : A[v]) {
		if (u == p)
			continue;
		near_child[v] = min(near_child[v], near_child[u] + w[e]);
	}
	update(st[v], ft[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_m_height_st[st[u]] > 1e20)
			ans[i] = -1;
		else
			ans[i] = near_m_height_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});
	}
	fill(near_m_height_st, near_m_height_st+N, 1e100);
	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: 27 / 27
• Subtask 3: 23 / 23
• Subtask 4: 41 / 41