제출 #898852

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
898852		vjudge1	Valley (BOI19_valley)	C++17	36 / 100	3068 ms	11280 KiB

valley

#include <bits/stdc++.h>

using namespace std;

#define ll long long int
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
#define u_map unordered_map
#define int ll
const int maxn = 1e5 + 5, mod = 1e9 + 7, inf = 1e15;

vector<pii> adj[maxn], ed;
bool sh[maxn], mark[maxn], is, si, issub;
pii ban;
int n, s, q, e, ans, dis[maxn], parl[maxn][19], h[maxn], cnt, st[maxn], fn[maxn];

void dfs(int v, int par) {
	mark[v] = 1;
	if (v == e) {
		is = true;
	}
	if (sh[v]) {
		si = true;
		ans = min(ans, par);
	}
	for (pii u: adj[v]) {
		if (!mark[u.second] and !(((ban.first == u.second and ban.second == v) or (ban.first == v and ban.second == u.second)))) {
			dfs(u.second, par + u.first);
		}
	}
}

inline void _clear() {
	memset(mark, 0, sizeof mark);
	is = false;
	si = false;
	ans = inf;
}

void dfs1(int v, int par) {
	mark[v] = 1;
	st[v] = cnt;
	h[v] = h[par] + 1;
	cnt++;
	if (par) {
		parl[v][0] = par;
		for (int i = 1; i <= 17; i++) {
			parl[v][i] = parl[parl[v][i - 1]][i - 1];
		}
	}
	for (pii x: adj[v]) {
		int u = x.second;
		if (!mark[u]) {
			dis[u] = dis[v] + x.first;
			dfs1(u, v);
		}
	}
	fn[v] = cnt;
	cnt++;
}

int lca(int x, int y) {
	if (h[y] > h[x])
		swap(x, y);
	for (int i = 17; i >= 0; i--) {
		if ((st[parl[x][i]] <= st[y] and fn[parl[x][i]] >= fn[y]) or parl[x][i] == 0) {
			continue;
		}
		x = parl[x][i];
	}
	return parl[x][0];
}

bool isin(int a, int b) {
	if (st[a] <= st[b] and fn[a] >= fn[b]) {
		return true;
	}
	return false;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n >> s >> q >> e;
    for (int i = 1; i < n; i++) {
    	int u, v, w;
    	cin >> u >> v >> w;
    	adj[u].pb({w, v});
    	adj[v].pb({w, u});
    	ed.pb({u, v});
    }
    for (int i = 1; i <= s; i++) {
    	int x;
    	cin >> x;
    	if (s == 1 and x == n) {
    		issub = 1;
    	}
    	sh[x] = 1;
    }
    if (issub) {
    	h[0] = -1;
    	dfs1(n, 0);
    }
    while (q--) {
    	_clear();
    	int l, r;
    	cin >> l >> r;
    	ban = {ed[l - 1].first, ed[l - 1].second};
    	if (issub) {
    		int x = ban.first, y = ban.second;
    		if (h[y] > h[x]) {
    			swap(x, y);
    		}
    		if (isin(x, r)) {
    			if (isin(x, e)) {
    				cout << "escaped\n";
    			} else {
    				cout << "oo\n";
    			}
    		} else {
    			if (isin(x, e)) {
    				cout << dis[r] << '\n';
    			} else {
    				cout << "escaped\n";
    			}
    		}
    		continue;
    	}
    	dfs(r, 0);
    	if (is) {
    		cout << "escaped\n";
    	} else {
    		if (!si) {
    			cout << "oo\n";
    		} else {
    			cout << ans << '\n';
    		}
    	}
    }
    return 0;
}

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