Submission #339003

#	Time	Username	Problem	Language	Result	Execution time	Memory
339003		sinamhdv	Valley (BOI19_valley)	C++11	100 / 100	340 ms	31024 KiB

valley

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1000 * 1000 * 1000 + 7;
const int INF = 1000 * 1000 * 1000;
const ll LINF = (ll)INF * INF;

#ifdef DEBUG
#define dbg(x) cout << #x << " = " << (x) << endl << flush;
#define dbgr(s, f) { cout << #s << ": "; for (auto _ = (s); _ != (f); _++) cout << *_ << ' '; cout << endl << flush; }
#else
#define dbg(x) ;
#define dbgr(s, f) ;
#endif
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define fast_io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define msub(a, b) ((mod + ((ll)(a) - (b)) % mod) % mod)
#define mdiv(a, b) ((ll)(a) * poww((b), mod - 2) % mod)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define endl '\n'

struct QR
{
	int e, v, ind;
};

#define MAXN 100100

int n, sp, q, E;
vector<int> adj[MAXN];
bool shop[MAXN];
int efrom[MAXN], eto[MAXN], ew[MAXN];
int sttime[MAXN], fntime[MAXN], timer;
vector<QR> qr[MAXN];
ll dist[MAXN];
ll ans[MAXN];
int h[MAXN];

void fr_dfs(int v, int par = -1)
{
	sttime[v] = timer++;
	for (int e : adj[v])
	{
		int u = efrom[e] ^ eto[e] ^ v;
		if (u == par)
			continue;
		dist[timer] = dist[sttime[v]] + ew[e];
		h[u] = h[v] + 1;
		fr_dfs(u, v);
	}
	fntime[v] = timer;
}

inline bool insub(int v, int u)
{
	return (sttime[v] <= sttime[u] && sttime[u] < fntime[v]);
}

ll seg[4 * MAXN];
ll lazy[4 * MAXN];

void build(int v = 1, int l = 0, int r = n - 1)
{
	if (l == r)
	{
		seg[v] = dist[l];
		return;
	}
	int mid = (r + l) / 2;
	build(2 * v, l, mid);
	build(2 * v + 1, mid + 1, r);
	seg[v] = min(seg[2 * v], seg[2 * v + 1]);
}

void pushdown(int v)
{
	if (!lazy[v])
		return;
	lazy[2 * v] += lazy[v];
	lazy[2 * v + 1] += lazy[v];
	seg[2 * v] += lazy[v];
	seg[2 * v + 1] += lazy[v];
	lazy[v] = 0;
}

void add(int L, int R, ll x, int v = 1, int l = 0, int r = n - 1)
{
	if (l > R || r < L)
		return;
	if (l >= L && r <= R)
	{
		lazy[v] += x;
		seg[v] += x;
		return;
	}
	int mid = (r + l) / 2;
	pushdown(v);
	add(L, R, x, 2 * v, l, mid);
	add(L, R, x, 2 * v + 1, mid + 1, r);
	seg[v] = min(seg[2 * v], seg[2 * v + 1]);
}

ll rmin(int L, int R, int v = 1, int l = 0, int r = n - 1)
{
	if (l > R || r < L)
		return LINF;
	if (l >= L && r <= R)
		return seg[v];
	int mid = (r + l) / 2;
	pushdown(v);
	return min(rmin(L, R, 2 * v, l, mid), rmin(L, R, 2 * v + 1, mid + 1, r));
}

void sc_dfs(int v, int par)
{
	for (QR q : qr[v])
	{
		int u = efrom[q.e];
		if (h[u] < h[eto[q.e]])
			u = eto[q.e];

		/*
		if (q.ind == 0)
		{
			dbg(v);
			dbg(u);
			dbgr(seg, seg + n);
			dbg(efrom[q.e]);
			dbg(eto[q.e]);
			dbgr(h + 1, h + n + 1);
		}
		*/
		
		if (!(insub(u, v) ^ insub(u, E)))
		{
			ans[q.ind] = -1;	// escaped
			continue;
		}
		if (insub(u, v))
		{
			ans[q.ind] = rmin(sttime[u], fntime[u] - 1);
		}
		else
		{
			ans[q.ind] = min(rmin(0, sttime[u] - 1), rmin(fntime[u], n - 1));
		}
	}

	for (int e : adj[v])
	{
		int u = efrom[e] ^ eto[e] ^ v;
		if (u == par)
			continue;
		ll w = ew[e];
		add(0, n - 1, w);
		add(sttime[u], fntime[u] - 1, -2 * w);
		sc_dfs(u, v);
		add(sttime[u], fntime[u] - 1, 2 * w);
		add(0, n - 1, -w);
	}
}

int32_t main(void)
{
	fast_io;
	cin >> n >> sp >> q >> E;
	FOR(i, 0, n - 1)
	{
		int x, y, w;
		cin >> x >> y >> w;
		adj[x].pb(i);
		adj[y].pb(i);
		efrom[i] = x;
		eto[i] = y;
		ew[i] = w;
	}
	FOR(i, 0, sp)
	{
		int x;
		cin >> x;
		shop[x] = true;
	}
	FOR(i, 0, q)
	{
		int x, y;
		cin >> x >> y;
		x--;
		QR tmp = {x, y, i};
		qr[y].pb(tmp);
	}

	fr_dfs(1);
	FOR(i, 1, n + 1)
	{
		if (!shop[i])
		{
			dist[sttime[i]] = LINF;
		}
	}

	/*
	dbgr(dist, dist + n);
	dbgr(sttime + 1, sttime + n + 1);
	dbgr(fntime + 1, fntime + n + 1);
	dbg("=========\n\n");
	*/

	build();
	sc_dfs(1, -1);

	FOR(i, 0, q)
	{
		if (ans[i] == -1)
		{
			cout << "escaped\n";
		}
		else if (ans[i] >= LINF/10)
		{
			cout << "oo\n";
		}
		else
		{
			cout << ans[i] << endl;
		}
	}

	return 0;
}

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