Submission #819578

#	Time	Username	Problem	Language	Result	Execution time	Memory
819578		aryan12	Valley (BOI19_valley)	C++17	23 / 100	118 ms	34568 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];

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);
		dist_in_subtree[node] = min(dist_in_subtree[node], dist_in_subtree[to] + 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;
	}
	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]];
		}
	}
	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
			{
				cout << "0\n";
			}
		}
		else
		{
			cout << "escaped\n";
		}
	}
}

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