제출 #694692

#제출 시각아이디문제언어결과실행 시간메모리
694692daoquanglinh2007Valley (BOI19_valley)C++17
0 / 100
3092 ms262144 KiB
#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, SZ = 320, INF = 1e18+7;

struct edge{
	int par, son;
};

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

void DFS(int u){
	if (is_shop[u]) shopNum[u] = 1;
	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;
			DFS(v);
			shopNum[u] += shopNum[v];
		}
	}
}

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(){
	parent[1] = -1, h[1] = 0, dist[1] = 0;
	for (int i = 2; i <= N; i++)
		h[i] = -1;
	DFS(1);
	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];
}

int Find(int u){
	if (is_shop[u]) return 0;
	int 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;
}

int 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, 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;
			}
			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, 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;
}

컴파일 시 표준 에러 (stderr) 메시지

valley.cpp: In function 'void DFS(long long int)':
valley.cpp:26: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]
   26 |  for (int i = 0; i < adj[u].size(); i++){
      |                  ~~^~~~~~~~~~~~~~~
valley.cpp: In function 'long long int Find(long long int)':
valley.cpp:81: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]
   81 |  for (int i = 0; i < adj[u].size(); i++){
      |                  ~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...