Submission #898824

#	Time	Username	Problem	Language	Result	Execution time	Memory
898824		vjudge1	Valley (BOI19_valley)	C++17	36 / 100	3042 ms	11972 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;

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

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;
    }
    while (q--) {
    	_clear();
    	int l, r;
    	cin >> l >> r;
    	ban = {ed[l - 1].first, ed[l - 1].second};
    	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