Submission #702422

#	Time	Username	Problem	Language	Result	Execution time	Memory
702422		Zian_Jacobson	Valley (BOI19_valley)	C++17	100 / 100	618 ms	97852 KiB

valley

#include<bits/stdc++.h>
using namespace std;
#define cIO ios_base::sync_with_stdio(0);cin.tie(0)
#define fileIO(x) ifstream fin(string(x)+".in"); ofstream fout(string(x)+".out")
#define cont(container, object) (container.find(object)!=container.end())
#define sz(x) (int) (x).size()
#define ll long long
#define v vector
const ll INF = LLONG_MAX / 2;
const int max_log = 18;
v<v<pair<int, ll>>> adj;
v<pair<int, ll>> p;
v<v<pair<int, ll>>> c;
v<v<pair<int, ll>>> jmp;
v<v<ll>> jmp_f, jmp_d;//jump 2^k steps to parent & distance
v<ll> ds_subtree;//min dist to store in subtree
v<bool> is_store;
v<int> depth;
v<pair<int, int>> roads_list;
void dfs_p(int node)
{
	if (is_store[node]) ds_subtree[node] = 0;
	for (auto nxt : adj[node])
		if (nxt.first != p[node].first)
		{
			p[nxt.first] = { node, nxt.second };
			c[node].push_back(nxt);
			depth[nxt.first] = depth[node] + 1;
			dfs_p(nxt.first);
			ds_subtree[node] = min(ds_subtree[node], ds_subtree[nxt.first]+nxt.second);
		}
	return;
}
int main()
{
	fileIO("valley");
	//remember distances could be long long
	int N, S, Q, E; cin >> N >> S >> Q >> E;
	adj.resize(N + 1);
	is_store.resize(N + 1);
	p.resize(N + 1); c.resize(N + 1);
	p[E] = { E,0 };
	ds_subtree.resize(N + 1, INF);
	depth.resize(N + 1);
	jmp = v<v<pair<int, ll>>>(N + 1, v<pair<int, ll>>(max_log + 1));
	jmp_f = jmp_d = v<v<ll>>(N + 1, v<ll>(max_log + 1, INF));
	roads_list.resize(N + 1);
	for (int i = 1; i <= N - 1; i++)
	{
		int a, b; ll c;
		cin >> a >> b >> c;
		adj[a].push_back({ b,c });
		adj[b].push_back({ a,c });
		roads_list[i] = { a,b };
	}
	for (int i = 1; i <= S; i++)
	{
		int a; cin >> a;
		is_store[a] = true;
	}
	dfs_p(E);
	
	for (int i = 1; i <= N; i++)
	{
		jmp[i][0] = p[i];
	}
	for (int dep = 1; dep <= max_log; dep++)
		for (int i = 1; i <= N; i++)
		{
			jmp[i][dep] = { jmp[jmp[i][dep - 1].first][dep - 1].first,
			jmp[i][dep - 1].second + jmp[jmp[i][dep - 1].first][dep - 1].second };
		}
	for (int i = 1; i <= N; i++)
	{
		jmp_d[i][0] = jmp[i][0].second + ds_subtree[jmp[i][0].first];
	}
	for (int dep = 1; dep <= max_log; dep++)
		for (int i=1; i <= N; i++)
		{
			jmp_d[i][dep] = min(jmp_d[i][dep - 1],
				jmp_d[jmp[i][dep - 1].first][dep - 1] + jmp[i][dep - 1].second);
		}
	for (int z = 1; z <= Q; z++)
	{
		int I, R;
		cin >> I >> R;
		pair<int, int> rem = roads_list[I];
		if (depth[rem.first] > depth[rem.second]) swap(rem.first, rem.second);
		int top_node = rem.second;
		//first check if top_node is not a parent of R
		if (depth[R] < depth[top_node])
		{
			cout << "escaped\n";
			continue;
		}
		int stp = depth[R] - depth[top_node];
		int R1 = R;
		for (int i = 0; i <= max_log; i++)
		{
			if (stp & (1 << i))
				R1 = jmp[R1][i].first;
		}
		if (R1!=top_node)
		{
			cout << "escaped\n";
			continue;
		}
		//we know that top_node is a parent
		ll min_cost = ds_subtree[R];
		ll cum_jmp_cost = 0;
		R1 = R;
		for (int i = 0; i <= max_log; i++)
		{
			if (stp & (1 << i))
			{
				min_cost = min(min_cost, jmp_d[R1][i] + cum_jmp_cost);
				cum_jmp_cost += jmp[R1][i].second;
				R1 = jmp[R1][i].first;
			}
		}
		if (min_cost == INF) cout << "oo\n";
		else cout << min_cost << "\n";
	}
	return 0;
}

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