Submission #1328531

#TimeUsernameProblemLanguageResultExecution timeMemory
1328531tkm_algorithmsValley (BOI19_valley)C++20
0 / 100
46 ms8076 KiB
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
//#define int ll
using P = pair<int, int>;
#define all(x) x.begin(), x.end()
#define rep(i, l, n) for (int i = l; i < (n); ++i)
#define sz(x) (int)x.size()
const char nl = '\n';
const int mod = 998244353;
const int NMAX = 1e5+10;
struct edge{
	int v, w, id;
};

P E[NMAX];
vector<edge> g[NMAX];
int tin[NMAX], tout[NMAX];
int t = 0;

void dfs(int nd = 1, int p = -1) {
	tin[nd] = t++;
	for (auto ch: g[nd]) {
		if (ch.v == p)continue;
		E[ch.id] = {nd, ch.v};
		dfs(ch.v, nd);
	}
	
	tout[nd] = t;
}

bool f(int l, int r, int x) {
	if (l <= x && r <= x)return 1;
	return 0;
}

void solve() {
	int n, s, q, e;
	cin >> n >> s >> q >> e;
	rep(i, 1, n) {
		int u, v, w; cin >> u >> v >> w;
		g[u].push_back({v, w, i});
		g[v].push_back({u, w, i});
	}
	
	rep(i, 0, s) {
		int c; cin >> c;
	}
	
	while (q--) {
		int I, R; cin >> I >> R;
		int v = E[I].second;
		int a = f(tin[v], tout[v], tin[e]);
		int b = f(tin[v], tout[v], tin[R]);
		if (a^b)cout << 0 << nl;
		else cout << "escaped\n";
	}	
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...