Submission #332843

#	Time	Username	Problem	Language	Result	Execution time	Memory
332843		sinamhdv	Valley (BOI19_valley)	C++11	36 / 100	3059 ms	53368 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 + ((a) - (b)) % mod) % mod)
#define mdiv(a, b) ((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'

#define MAXN 100100
#define LOGN 30
#define SQRT 1000
//#define SQRT 6

vector<int> adj[MAXN];
int ew[MAXN];
int efrom[MAXN], eto[MAXN];
int n, S, q, E;
int sp[MAXN];
bool in_sp[MAXN];

int h[MAXN];
int par[LOGN][MAXN];
ll dpar[LOGN][MAXN];
int sttime[MAXN], fntime[MAXN];
int timer;

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

bool stcmp(int a, int b)
{
	return sttime[a] < sttime[b];
}

ll dist[MAXN/SQRT+10][MAXN];

set<pll> ds;

void dij(int b)
{
	ds.clear();
	int l = b * SQRT;
	int r = (b + 1) * SQRT;
	fill(dist[b], dist[b] + n + 10, LINF);
	FOR(i, l, r)
	{
		dist[b][sp[i]] = 0;
		ds.insert(mp(dist[b][i], sp[i]));
	}
	while (!ds.empty())
	{
		int v = ds.begin() -> sc;
		ds.erase(ds.begin());
		for (int e : adj[v])
		{
			int u = efrom[e] ^ eto[e] ^ v;
			ll nw = dist[b][v] + ew[e];
			if (nw < dist[b][u])
			{
				ds.erase(mp(dist[b][u], u));
				dist[b][u] = nw;
				ds.insert(mp(dist[b][u], u));
			}
		}
	}
}

pll lca(int v, int u)
{
	if (h[u] > h[v])
	{
		swap(u, v);
	}
	ll res = 0;
	int dif = h[v] - h[u];
	FOR(i, 0, LOGN)
	{
		if (dif & (1 << i))
		{
			res += dpar[i][v];
			v = par[i][v];
		}
	}
	if (u == v)
	{
		return mp(u, res);
	}
	for (int i = LOGN - 1; i >= 0; i--)
	{
		if (par[i][v] != par[i][u])
		{
			res += dpar[i][v] + dpar[i][u];
			v = par[i][v];
			u = par[i][u];
		}
	}
	res += dpar[0][v] + dpar[0][u];
	return mp(par[0][u], res);
}

ll getdist(int v, int l, int r)
{
	int i;
	ll res = LINF;
	if (l > r)
	{
		return LINF;
	}
	for (i = l; i / SQRT == l/SQRT && i <= r; i++)
	{
		res = min(res, lca(v, sp[i]).sc);
	}
	for (int b = i/SQRT; b < r/SQRT; b++)
	{
		res = min(res, dist[b][v]);
	}
	if (i <= r)
	{
		for (i = (r/SQRT) * SQRT; i <= r; i++)
		{
			res = min(res, lca(v, sp[i]).sc);
		}
	}
	return res;
}

#define insub(r, v) (sttime[(r)] <= sttime[(v)] && sttime[(v)] <= fntime[(r)])

int32_t main(void)
{
	fast_io;
	cin >> n >> S >> q >> E;
	FOR(i, 1, n)
	{
		int x, y;
		cin >> x >> y >> ew[i];
		efrom[i] = x;
		eto[i] = y;
		adj[x].pb(i);
		adj[y].pb(i);
	}
	FOR(i, 0, S)
	{
		cin >> sp[i];
		in_sp[sp[i]] = true;
	}
	dfs(1);
	sort(sp, sp + S, stcmp);
	FOR(i, 1, LOGN)
	{
		FOR(j, 1, n + 1)
		{
			par[i][j] = par[i - 1][par[i - 1][j]];
			dpar[i][j] = dpar[i - 1][j] + dpar[i - 1][par[i - 1][j]];
		}
	}
	FOR(i, 0, (S-1)/SQRT + 1)
	{
		dij(i);
	}
	dbgr(sp, sp + S);
	dbgr(sttime + 1, sttime + n + 1);
	dbgr(fntime + 1, fntime + n + 1);
	while (q--)
	{
		int l, R;
		cin >> l >> R;
		int u = efrom[l], d = eto[l];
		if (h[u] > h[d])
			swap(u, d);
		if ((insub(d, R) && insub(d, E)) || (!insub(d, R) && !insub(d, E)))
		{
			cout << "escaped\n";
			continue;
		}
		if (in_sp[R])
		{
			cout << "0\n";
			continue;
		}
		int lft = lower_bound(sp, sp + S, d, stcmp) - sp;
		sttime[0] = fntime[d];
		int rgt = upper_bound(sp, sp + S, 0, stcmp) - sp;
		rgt--;

		dbg(lft);
		dbg(rgt);
		dbg(insub(d, R));
		dbg(d);

		if (insub(d, R))
		{
			ll dd = getdist(R, lft, rgt);
			if (dd >= LINF)
			{
				cout << "oo\n";
			}
			else
			{
				cout << dd << endl;
			}
		}
		else
		{
			ll dd = min(getdist(R, 0, lft - 1), getdist(R, rgt + 1, S - 1));
			if (dd >= LINF)
			{
				cout << "oo\n";
			}
			else
			{
				cout << dd << endl;
			}
		}
	}
	return 0;
}

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