Submission #996929

#	Time	Username	Problem	Language	Result	Execution time	Memory
996929		aykhn	Valley (BOI19_valley)	C++17	100 / 100	291 ms	52820 KiB

valley

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define inf 0x3F3F3F3F3F3F3F3F

const int MXN = 3e5 + 5;

int N, S, Q, E;
vector<array<int, 2>> adj[MXN];
vector<array<int, 2>> q[MXN];
int in[MXN], out[MXN], tim, d[MXN];
int ans[MXN], sh[MXN];
int st[MXN << 2], lz[MXN << 2];
array<int, 2> e[MXN];
int esc[MXN];

void relax(int l, int r, int x)
{
	if (!lz[x]) return;
	st[x] += lz[x];
	if (l != r)
	{
		lz[2*x] += lz[x], lz[2*x + 1] += lz[x];
	}
	lz[x] = 0;
}
void add(int l, int r, int x, int lx, int rx, int val)
{
	if (lx > rx) return;
	relax(l, r, x);
	if (l > rx || r < lx) return;
	if (l >= lx && r <= rx) 
	{
		lz[x] += val;
		relax(l, r, x);
		return;
	}
	int mid = (l + r) >> 1;
	add(l, mid, 2*x, lx, rx, val);
	add(mid + 1, r, 2*x + 1, lx, rx, val);
	st[x] = min(st[2*x], st[2*x + 1]);
}
int get(int l, int r, int x, int lx, int rx)
{
	if (lx > rx) return inf;
	if (l > rx || r < lx) return inf;
	relax(l, r, x);
	if (l >= lx && r <= rx) return st[x];
	int mid = (l + r) >> 1;
	return min(get(l, mid, 2*x, lx, rx), get(mid + 1, r, 2*x + 1, lx, rx));
}

void _init(int a, int p)
{
	in[a] = ++tim;
	for (array<int, 2> &v : adj[a])
	{
		if (v[0] == p) continue;
		d[v[0]] = d[a] + v[1];
		_init(v[0], a);
	}
	out[a] = tim;
}

int anc(int u, int v)
{
	return in[u] <= in[v] && out[v] <= out[u];
}

void dfs(int a, int p)
{
	for (array<int, 2> &x : q[a])
	{
		int r = e[x[0]][0];
		if (anc(r, E) == anc(r, a))
		{
			esc[x[1]] = 1;
			continue;
		}
		if (anc(r, a)) ans[x[1]] = get(1, N, 1, in[r], out[r]);
		else ans[x[1]] = min(get(1, N, 1, 1, in[r] - 1), get(1, N, 1, out[r] + 1, N));
	}
	for (array<int, 2> &v : adj[a])
	{
		if (v[0] == p) continue;
		add(1, N, 1, in[v[0]], out[v[0]], -v[1]);
		add(1, N, 1, 1, in[v[0]] - 1, v[1]);
		add(1, N, 1, out[v[0]] + 1, N, v[1]);
		dfs(v[0], a);
		add(1, N, 1, in[v[0]], out[v[0]], v[1]);
		add(1, N, 1, 1, in[v[0]] - 1, -v[1]);
		add(1, N, 1, out[v[0]] + 1, N, -v[1]);
	}
}

signed main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> S >> Q >> E;
	for (int i = 1; i < N; i++)
	{
		int u, v, w;
		cin >> u >> v >> w;
		e[i] = {u, v};
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
	}
	_init(1, 1);
	for (int i = 1; i < N; i++) if (anc(e[i][0], e[i][1])) swap(e[i][0], e[i][1]);
	for (int i = 1; i <= S; i++)
	{
		int x;
		cin >> x;
		sh[x] = 1;
	}
	for (int i = 1; i <= N; i++) if (!sh[i]) add(1, N, 1, in[i], in[i], inf); else add(1, N, 1, in[i], in[i], d[i]);
	for (int i = 0; i < Q; i++)
	{
		int j, r;
		cin >> j >> r;
		q[r].push_back({j, i});
	}
	dfs(1, 1);
	for (int i = 0; i < Q; i++)
	{
		if (esc[i]) cout << "escaped\n";
		else if (ans[i] >= (int)1e15) cout << "oo\n";
		else cout << ans[i] << '\n';
	}
}

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