제출 #1282936

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1282936		Jawad_Akbar_JJ	Valley (BOI19_valley)	C++20	100 / 100	330 ms	49664 KiB

valley

#include <iostream>
#include <vector>

using namespace std;
#define int long long
const int N = 1<<17;
vector<pair<int,int>> nei[N];
int hei[N], st[N], en[N], Mn[N][20], dist[N], Par[N][20], a[N], b[N], cur, inf = 1e17;

void dfs(int u, int p){
	hei[u] = hei[p] + 1;
	st[u] = cur++;

	for (auto [i, w] : nei[u]){
		if (i == p)
			continue;
		dist[i] = dist[u] + w;
		dfs(i, u);
		Mn[u][0] = min(Mn[u][0], Mn[i][0] + w);
	}
	en[u] = cur;
}

void dfs2(int u, int p){
	Par[u][0] = p, Mn[u][0] -= dist[u];
	
	for (int i=1;i<=17;i++){
		Mn[u][i] = min(Mn[u][i-1], Mn[Par[u][i-1]][i-1]);
		Par[u][i] = Par[Par[u][i-1]][i-1];
	}

	for (auto [i, w] : nei[u]){
		if (i == p)
			continue;
		dfs2(i, u);
	}
}

int moveUp(int v, int k, int ans = inf){
	for (int i=0;i<=17;i++)
		if ((1<<i) & k)
			ans = min(ans, Mn[v][i]), v = Par[v][i];
	return ans;
}

signed main(){
	int n, s, q, e;
	cin>>n>>s>>q>>e;

	for (int i=1;i<=n;i++)
		Mn[i][0] = inf;

	for (int i=1, c;i<n;i++){
		cin>>a[i]>>b[i]>>c;

		nei[a[i]].push_back({b[i], c});
		nei[b[i]].push_back({a[i], c});
	}

	for (int i=1, v;i<=s;i++)
		cin>>v, Mn[v][0] = 0;

	dfs(e, 0);
	dfs2(e, 0);

	for (int i=1;i<=q;i++){
		int I, r;
		cin>>I>>r;

		I = (Par[a[I]][0] == b[I] ? a[I] : b[I]);

		if (st[I] <= st[r] and en[r] <= en[I]){
			int d = moveUp(r, hei[r] - hei[I] + 1) + dist[r];
			if (d >= inf / 10)
				cout<<"oo\n";
			else
				cout<<d<<'\n';
		}
		else
			cout<<"escaped\n";
	}
}

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