Submission #694714

#	Time	Username	Problem	Language	Result	Execution time	Memory
694714		daoquanglinh2007	Valley (BOI19_valley)	C++17	59 / 100	3066 ms	20724 KiB

valley

#pragma GCC optimize("Ofast")
#pragma GCC target("sse4")

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

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

const int NM = 1e5, SZ = 50000;
const ll INF = 1e18+7;

struct edge{
	int par, son;
};

int N, S, Q, E;
vector <pil> adj[NM+5];
edge e[NM+5];
int A[NM+5], is_shop[NM+5];
stack <int> st;
int parent[NM+5], h[NM+5], shopNum[NM+5], lg2[NM+5];
ll dist[NM+5];
int P[NM+5][20];
pii banned_edge;

void DFS(){
	parent[1] = -1, h[1] = 0, dist[1] = 0;
	for (int i = 2; i <= N; i++)
		h[i] = -1;
	for (int i = 1; i <= N; i++)
		shopNum[i] = -1;
	st.push(1);
	while (!st.empty()){
		int u = st.top();
		if (shopNum[u] == -1){
			shopNum[u] = is_shop[u];
			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; dist[v] = dist[u]+adj[u][i].se;
					st.push(v);
				}
			}
		}
		else{
			for (int i = 0; i < adj[u].size(); i++){
				int v = adj[u][i].fi;
				if (v != parent[u]) shopNum[u] += shopNum[v];
			}
			st.pop();
		}
	}
}

void build(){
	for (int i = 1; i <= N; i++)
		P[i][0] = parent[i];
	for (int j = 1; j <= lg2[N]; j++)
		for (int i = 1; i <= N; i++)
			if (P[i][j-1] != -1) P[i][j] = P[P[i][j-1]][j-1];
			else P[i][j] = -1;
}

void preprocess(){
	DFS();
	for (int i = 1; i < N; i++)
		if (parent[e[i].par] == e[i].son) swap(e[i].par, e[i].son);
	lg2[1] = 0;
	for (int i = 2; i <= N; i++)
		lg2[i] = lg2[i>>1]+1;
	build();
}

int binlift(int u, int k){
	for (int i = lg2[k]; i >= 0; i--)
		if ((k&(1<<i)) != 0) u = P[u][i];
	return u;
}

int LCA(int u, int v){
	if (h[u] < h[v]) swap(u, v);
	u = binlift(u, h[u]-h[v]);
	if (u == v) return u;
	for (int i = lg2[h[u]]; i >= 0; i--)
		if (P[u][i] != -1 && P[u][i] != P[v][i]){
			u = P[u][i];
			v = P[v][i];
		}
	return parent[u];
}

ll Find(int u){
	if (is_shop[u]) return 0;
	ll res = +INF;
	for (int i = 0; i < adj[u].size(); i++){
		int v = adj[u][i].fi;
		if (mp(u, v) == banned_edge || mp(v, u) == banned_edge) continue;
		res = min(res, Find(v)+adj[u][i].se);
	}
	return res;
}

bool is_ancestor(int a, int u){
	if (h[a] > h[u]) return 0;
	return binlift(u, h[u]-h[a]) == a;
}

ll D(int u, int v){
	int a = LCA(u, v);
	return dist[u]+dist[v]-2*dist[a];
}

void solve(){
	while (Q--){
		int I, R;
		cin >> I >> R;
		int v = e[I].son;
		ll ans = +INF;
		if (is_ancestor(v, R)){
			if (is_ancestor(v, E)){
				cout << "escaped\n"; continue;
			}
			if (shopNum[v] == 0){
				cout << "oo\n"; continue;
			}
			if (S <= SZ){
				for (int i = 1; i <= S; i++)
					if (is_ancestor(v, A[i])) ans = min(ans, D(R, A[i]));
			}
			else{
				banned_edge = mp(e[I].par, e[I].son);
				ans = Find(R);
			}
		}
		else{
			if (!is_ancestor(v, E)){
				cout << "escaped\n"; continue;
			}
			if (shopNum[v] == S){
				cout << "oo\n"; continue;
			}
			if (S <= SZ){
				for (int i = 1; i <= S; i++)
					if (!is_ancestor(v, A[i])) ans = min(ans, D(R, A[i]));
			}
			else{
				banned_edge = mp(e[I].par, e[I].son);
				ans = Find(R);
			}
		}
		cout << ans << "\n";
	}
}

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 A, B; ll W;
		cin >> A >> B >> W;
		adj[A].push_back(mp(B, W));
		adj[B].push_back(mp(A, W));
		e[i].par = A, e[i].son = B;
	}
	for (int i = 1; i <= S; i++){
		cin >> A[i];
		is_shop[A[i]] = 1;
	}
	preprocess();
	solve();
	return 0;
}

Compilation message (stderr)

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

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