Submission #435852

#	Time	Username	Problem	Language	Result	Execution time	Memory
435852		jerzyk	Valley (BOI19_valley)	C++14	100 / 100	483 ms	59844 KiB

valley

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 100 * 1000 + 7;
const ll I = 1000000LL * 1000000LL * 1000000LL; 
int lca[20][N], poz[N], czy[N], od[N];
ll dol[3][N], gor[N], nws[20][N], rnws[20][N], odl[N];
vector<pair<int, ll>> kr[N];
pair<int, int> ed[N];

void DFS(int v)
{
	od[v] = 1;
	int i;
	ll aw;
	dol[0][v] = I;
	dol[1][v] = I;
	dol[2][v] = I;
	if(czy[v] == 1)
		dol[0][v] = 0;
	gor[v] = I;
	for(i = 0; i < (int)kr[v].size(); ++i)
	{
		if(od[kr[v][i].first] == 1)
			continue;
		if(dol[0][v] == dol[0][kr[v][i].first] + kr[v][i].second)
			rnws[0][kr[v][i].first] = dol[1][v];
		else
			rnws[0][kr[v][i].first] = dol[0][v];
		poz[kr[v][i].first] = poz[v] + 1;
		odl[kr[v][i].first] = odl[v] + kr[v][i].second;
		lca[0][kr[v][i].first] = v;
		DFS(kr[v][i].first);
		aw = dol[0][kr[v][i].first] + kr[v][i].second;
		if(aw < dol[0][v])
			swap(aw, dol[0][v]);
		if(aw < dol[1][v])
			swap(aw, dol[1][v]);
		if(aw < dol[2][v])
			swap(aw, dol[2][v]);
	}
}

void DFS2(int v, int o)
{
	od[v] = 1;
	int i;
	if(czy[v] == 1)
		gor[v] = 0LL;
	nws[0][v] = dol[0][v];
	for(i = 0; i < (int)kr[v].size(); ++i)
	{
		if(od[kr[v][i].first] == 1)
			continue;
		gor[kr[v][i].first] = gor[v];
		if(dol[0][kr[v][i].first] + kr[v][i].second == dol[0][v])
			gor[kr[v][i].first] = min(gor[kr[v][i].first], dol[1][v] + kr[v][i].second);
		else
			gor[kr[v][i].first] = min(gor[kr[v][i].first], dol[0][v] + kr[v][i].second);
		DFS2(kr[v][i].first, o);
	}
}

void WyLCA(int n)
{
	int i, j;
	for(j = 1; j <= 18; ++j)
	{
		for(i = 1; i <= n; ++i)
		{
			lca[j][i] = lca[j - 1][lca[j - 1][i]];
			nws[j][i] = min(nws[j - 1][i], nws[j - 1][lca[j - 1][i]] + odl[i] - odl[lca[j - 1][i]]);
			rnws[j][i] = min(rnws[j - 1][lca[j - 1][i]], rnws[j - 1][i] + odl[lca[j - 1][i]] - lca[j][i]);
		}
	}
}

pair<int, ll> LCA(int a, int b)
{
	int i, pa, pb;
	if(a == b)
		return make_pair(a, dol[0][a]);
	pa = a;
	pb = b;
	ll w1, w2;
	w1 = I;
	w2 = I;
	if(poz[a] > poz[b])
	{
		for(i = 18; i >= 0; --i)
		{
			if(poz[lca[i][a]] > poz[b])
			{
				w1 = min(w1, nws[i][a] + odl[pa] - odl[a]);
				a = lca[i][a];
			}
		}
		if(lca[0][a] == b)
		{
			w1 = min(w1, odl[pa] - odl[b] + dol[0][b]);
		}
		w1 = min(w1, nws[0][a] + odl[pa] - odl[a]);
		a = lca[0][a];
		//cout << a << " " << b << "\n";
	}
	if(poz[b] > poz[a])
	{
		for(i = 18; i >= 0; --i)
		{
			if(poz[lca[i][b]] > poz[a])
			{
				w2 = min(w2 + odl[b] - odl[lca[i][b]], rnws[i][b]);
				b = lca[i][b];
			}
		}
		w2 = min(w2 + odl[b] - odl[lca[0][b]], rnws[0][b]);
		b = lca[0][b];
	}
	if(b == pa)
	{
		return make_pair(b, min(min(w1, w2), gor[a]));
	}
	if(a == pb)
	{
		return make_pair(a, min(w1, w2));
	}
	for(i = 18; i >= 0; --i)
	{
		if(lca[i][a] != lca[i][b])
		{
			w2 = min(w2 + odl[b] - odl[lca[i][b]], rnws[i][b]);
			b = lca[i][b];
			w1 = min(w1, nws[i][a] + odl[pa] - odl[a]);
			a = lca[i][a];
		}
	}
	w2 = min(w2 + odl[b] - odl[lca[0][b]], rnws[0][b]);
	b = lca[0][b];
	w1 = min(w1, nws[0][a] + odl[pa] - odl[a]);
	a = lca[0][a];
	w2 += (odl[pa] - odl[a]);
	w1 = min(w1, gor[a]);
	return make_pair(a, min(w1, w2));
}

void Wyw(int s, int n)
{
	int i, j;
	for(i = 1; i <= n; ++i)
	{
		for(j = 0; j <= 18; ++j)
		{
			nws[j][i] = I;
			rnws[j][i] = I;
		}
	}
	poz[s] = 0;
	odl[s] = 0LL;
	lca[0][s] = s;
	DFS(s);
	for(i = 1; i <= n; ++i)
		od[i] = 0;
	DFS2(s, s);
}

void Odp(int q)
{
	int i, v, x, a, b;
	pair<int, ll> w;
	for(i = 1; i <= q; ++i)
	{
		cin >> x >> v;
		a = ed[x].first;
		b = ed[x].second;
		if(poz[a] < poz[b])
			w = LCA(v, b);
		else
			w = LCA(v, a);
		//cout << w.first << " " << LCA(v, b).first << "\n";
		if(poz[w.first] <= min(poz[a], poz[b]))
		{
			cout << "escaped\n";
		}
		else
		{
			if(w.second >= I)
				cout << "oo\n";
			else
				cout << w.second << "\n";
		}
	}
}

void Wczytaj(int &n, int &s, int &q)
{
	int i, k, a;
	ll d;
	cin >> n >> k >> q >> s;
	for(i = 1; i < n; ++i)
	{
		cin >> ed[i].first >> ed[i].second >> d;
		kr[ed[i].first].push_back(make_pair(ed[i].second, d));
		kr[ed[i].second].push_back(make_pair(ed[i].first, d));
	}
	for(i = 1; i <= k; ++i)
	{
		cin >> a;
		czy[a] = 1;
	}
}

void Valley()
{
	int n, s, q;
	Wczytaj(n, s, q);
	Wyw(s, n);
	WyLCA(n);
	Odp(q);
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	Valley();

	return 0;
}

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