Submission #646116

#	Time	Username	Problem	Language	Result	Execution time	Memory
646116		dozer	Valley (BOI19_valley)	C++14	100 / 100	194 ms	52796 KiB

valley

#include <bits/stdc++.h>
using namespace std;
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define sp " "
#define endl "\n"
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define N 100005
#define LOGN 20
#define int long long

int dist[N], dep[N], mini[LOGN][N], par[LOGN][N], shop[N], val[N];
vector<pii> adj[N];
pii edge[N];
const int INF = 2e18 + 8, INF2 = 1e18 + 4;


int dfs(int node, int root, int d, int dd)
{
	par[0][node] = root;
	dist[node] = dd;
	dep[node] = d;
	int ans = INF;
	if (shop[node]) ans = 0;
	for (auto i : adj[node])
	{
		int curr = i.st, w = i.nd;
		if (curr != root) ans = min(ans, dfs(curr, node, d + 1, dd + w) + w);
	}
	val[node] = ans - dist[node];
	return ans;
}

pii lca(int a, int b)
{
	int ans = val[a];
	for (int i = LOGN - 1; i >= 0; i--)
		if ((1<<i) <= dep[a] - dep[b]) ans = min(ans, mini[i][a]), a = par[i][a];
	if (a == b) return {a, ans};
	return {-1, -1};
}

int32_t main()
{
	fastio();

	int n, s, q, e;
	cin>>n>>s>>q>>e;
	for (int i = 1; i < n; i++)
	{
		int u , v, w;
		cin>>u>>v>>w;
		adj[u].pb({v, w});
		adj[v].pb({u, w});
		edge[i] = {u, v};
	}

	for (int i = 1; i <= s; i++)
	{
		int num;
		cin>>num;
		shop[num] = 1;
	}

	int tmp = dfs(e, 0, 1, 0);
	for (int i = 1; i <= n; i++)
		mini[0][i] = val[par[0][i]];

	for (int i = 1; i < LOGN; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			mini[i][j] = min(mini[i - 1][j], mini[i - 1][par[i - 1][j]]);
			par[i][j] = par[i - 1][par[i - 1][j]];
		}
	}

	for (int i = 1; i < n; i++)
	{
		int u = edge[i].st, v = edge[i].nd;
		if (dep[u] < dep[v]) swap(edge[i].st, edge[i].nd);
		//cout<<edge[i].st<<sp<<edge[i].nd<<endl;
	}

	while(q--)
	{
		int i, r;
		cin>>i>>r;
		int top = edge[i].st;
		pii res = lca(r, top);
		if (res.st == -1)
		{
			cout<<"escaped"<<endl;
			continue;
		}
		int ans = res.nd + dist[r];
		if (ans >= INF2) cout<<"oo\n";
		else cout<<ans<<endl;
	}
 
	cerr<<"time taken : "<<(float)clock() / CLOCKS_PER_SEC<<"seconds\n";
}

Compilation message (stderr)

valley.cpp: In function 'int32_t main()':
valley.cpp:68:6: warning: unused variable 'tmp' [-Wunused-variable]
   68 |  int tmp = dfs(e, 0, 1, 0);
      |      ^~~

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