Submission #694949

#	Time	Username	Problem	Language	Result	Execution time	Memory
694949		daoquanglinh2007	Valley (BOI19_valley)	C++17	100 / 100	307 ms	44824 KiB

valley

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

#define int long long
#define pii pair <int, int>
#define fi first
#define se second
#define mp make_pair

const int NM = 1e5, LOG = 16, INF = 1e18;

int N, S, Q, E;
vector <pii> adj[NM+5];
pii A[NM+5];
bool is_shop[NM+5];
int parent[NM+5], h[NM+5], distE[NM+5], mindistE[NM+5], magic[NM+5];
int Pvertex[NM+5][LOG+1], Pmagic[NM+5][LOG+1];

void DFS(int u){
	if (is_shop[u]) mindistE[u] = distE[u]; else mindistE[u] = +INF;
	for (int i = 0; i < adj[u].size(); i++){
		int v = adj[u][i].fi;
		if (h[v] == -1){
			parent[v] = u;
			h[v] = h[u]+1;
			distE[v] = distE[u]+adj[u][i].se;
			DFS(v);
			mindistE[u] = min(mindistE[u], mindistE[v]);
		}
	}
	magic[u] = -2*distE[u]+mindistE[u];
}

void build(){
	for (int i = 1; i <= N; i++){
		Pvertex[i][0] = parent[i];
		if (parent[i] == -1) Pmagic[i][0] = +INF; else Pmagic[i][0] = magic[parent[i]];
	}
	for (int j = 1; j <= LOG; j++)
		for (int i = 1; i <= N; i++){
			if (Pvertex[i][j-1] != -1) Pvertex[i][j] = Pvertex[Pvertex[i][j-1]][j-1]; else Pvertex[i][j] = -1;
			if (Pvertex[i][j] == -1) Pmagic[i][j] = +INF; else Pmagic[i][j] = min(Pmagic[i][j-1], Pmagic[Pvertex[i][j-1]][j-1]);
		}
}

void preprocess(){
	parent[E] = -1;
	for (int i = 1; i <= N; i++) h[i] = -1;
	h[E] = 0;
	DFS(E);
	for (int i = 1; i < N; i++)
		if (parent[A[i].fi] == A[i].se) swap(A[i].fi, A[i].se);
	build();
}

bool is_ancestor(int a, int u){
	// check if a is an ancestor of u
	if (h[a] > h[u]) return 0;
	for (int i = LOG; i >= 0; i--)
		if (h[u]-(1<<i) >= h[a]) u = Pvertex[u][i];
	return u == a;
}

int binlift_magic(int u, int k){
	// calculate the min magic of u and of k nearest ancestors of u
	int res = magic[u];
	for (int i = LOG; i >= 0; i--)
		if ((k&(1<<i)) != 0){
			res = min(res, Pmagic[u][i]);
			u = Pvertex[u][i];
		}
	return res;
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> N >> S >> Q >> E;
	for (int i = 1; i < N; i++){
		int u, v, c;
		cin >> u >> v >> c;
		adj[u].push_back(mp(v, c));
		adj[v].push_back(mp(u, c));
		A[i] = mp(u, v);
	}
	for (int i = 1; i <= S; i++){
		int v; cin >> v;
		is_shop[v] = 1;
	}
	preprocess();
	while (Q--){
		int I, R; cin >> I >> R;
		int u = A[I].se;
		if (!is_ancestor(u, R)){
			cout << "escaped" << endl;
			continue;
		}
		int ans = distE[R]+binlift_magic(R, h[R]-h[u]);
		if (ans > (int)1e14) cout << "oo";
		else cout << ans;
		cout << endl;
	}
	return 0;
}

Compilation message (stderr)

valley.cpp: In function 'void DFS(long long int)':
valley.cpp:21:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |  for (int i = 0; i < adj[u].size(); i++){
      |                  ~~^~~~~~~~~~~~~~~

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