Submission #898865

#	Time	Username	Problem	Language	Result	Execution time	Memory
898865		vjudge1	Valley (BOI19_valley)	C++17	59 / 100	3067 ms	16664 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;
pii ban;
int n, s, q, e, ans, st[maxn], fn[maxn], cnt, h[maxn];

void dfs1(int v, int par) {
	mark[v] = 1;
	h[v] = h[par] + 1;
	st[v] = cnt;
	cnt++;
	for (pii x: adj[v]) {
		int u = x.second;
		if (!mark[u]) {
			dfs1(u, v);
		}
	}
	fn[v] = cnt;
	cnt++;
}

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

bool isin(int x, int y) {
	if (st[x] <= st[y] and fn[x] >= fn[y]) {
		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;
    	sh[x] = 1;
    }
    if (s == n) {
    	h[0] = -1;
    	dfs1(e, 0);
    }
    while (q--) {
    	_clear();
    	int l, r;
    	cin >> l >> r;
    	ban = {ed[l - 1].first, ed[l - 1].second};
    	if (s == n) {
    		int x = ban.first, y = ban.second;
    		if (h[y] > h[x]) {
    			swap(x, y);
    		}
			if (isin(x, r)) {
				cout << "0\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: 23 / 23
• Subtask 4: 0 / 41