Submission #822994

#	Time	Username	Problem	Language	Result	Execution time	Memory
822994		aryan12	Valley (BOI19_valley)	C++17	32 / 100	113 ms	61172 KiB

valley

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

const int N = 1e5 + 5, LG = 17, INF = 1e18;
vector<pair<int, int> > g[N];
bool shop[N];
int lift[LG][N], tin[N], tout[N], tim = 0;
int dist_in_subtree[N];
int bestup[LG][N], tot_dist[LG][N];

void dfs(int node, int par)
{
	if(shop[node])
	{
		dist_in_subtree[node] = 0;
	}
	else
	{
		dist_in_subtree[node] = INF;
	}
	tin[node] = ++tim;
	lift[0][node] = par;
	for(auto [to, wt]: g[node])
	{
		if(to == par) continue;
		dfs(to, node);
		tot_dist[0][to] = wt;
		dist_in_subtree[node] = min(dist_in_subtree[node], dist_in_subtree[to] + wt);
		bestup[0][to] = min(dist_in_subtree[to], dist_in_subtree[node] + wt);
	}
	tout[node] = tim;
}

int32_t main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, s, q, e;
	cin >> n >> s >> q >> e;
	vector<array<int, 3> > edges;
	for(int i = 1; i < n; i++)
	{
		int u, v, w;
		cin >> u >> v >> w;
		g[u].push_back({v, w});
		g[v].push_back({u, w});
		edges.push_back({u, v, w});
	}
	for(int i = 1; i <= s; i++)
	{
		int x;
		cin >> x;
		shop[x] = true;
	}
	dist_in_subtree[0] = INF;
	dfs(e, 0);
	for(int i = 1; i < LG; i++)
	{
		for(int j = 1; j <= n; j++)
		{
			lift[i][j] = lift[i - 1][lift[i - 1][j]];
			tot_dist[i][j] = tot_dist[i - 1][lift[i - 1][j]] + tot_dist[i - 1][j];
			bestup[i][j] = min(bestup[i - 1][j], bestup[i - 1][lift[i - 1][j]] + tot_dist[i - 1][j]);
		}
	}
	for(int i = 1; i <= q; i++)
	{
		int idx, node;
		cin >> idx >> node;
		idx -= 1;
		if(tin[edges[idx][0]] <= tin[edges[idx][1]])
		{
			swap(edges[idx][0], edges[idx][1]);
		}
		if(tin[edges[idx][0]] <= tin[node] && tout[node] <= tout[edges[idx][0]])
		{
			if(dist_in_subtree[edges[idx][0]] >= INF)
			{
				cout << "oo\n";
			}
			else
			{
				if(shop[node])
				{
					cout << "0\n";
					continue;
				}
				int cur_dist = 0, tot_ans = dist_in_subtree[node];
				for(int j = LG - 1; j >= 0; j--)
				{
					// cout << "j = " << j << ", node = " << node << "\n";
					// cout << lift[j][node] << "\n";
					if(lift[j][node] == 0)
					{
						continue;
					}
					if(tin[lift[j][node]] <= tin[edges[idx][1]] && tout[edges[idx][1]] <= tout[lift[j][node]])
					{
						continue;
					}
					else
					{
						tot_ans = min(tot_ans, cur_dist + bestup[j][node]);
						cur_dist += tot_dist[j][node];
						node = lift[j][node];
					}
				}
				// cout << "node = " << node << "\n";
				// assert(tot_ans < INF);
				cout << tot_ans << "\n";
			}
		}
		else
		{
			cout << "escaped\n";
		}
	}
}

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