Submission #1327321

#TimeUsernameProblemLanguageResultExecution timeMemory
1327321dianaValley (BOI19_valley)C++20
0 / 100
51 ms8860 KiB
#include <bits/stdc++.h>
#define pii pair<int, int>
#define fi first
#define se second
#define ll long long
using namespace std;
int n, s, q, e, bc;
const int N = 1e5+5;
const ll M = 1e17;
bool sh[N];
pii cel[N];
vector<pii> graf[N];

int tme = 0, tin[N], tout[N];
void et(int v, int p)
{
    tin[v] = ++tme;
    for(auto x: graf[v])
        if(x.fi != p)
            et(x.fi, v);
    tout[v] = ++tme;
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin >> n >> s >> q >> e;
    for(int i=1; i<n; i++)
    {
        int u, v, w; cin >> u >> v >> w;
        cel[i] = {u, v};
        graf[u].push_back({v, w});
        graf[v].push_back({u, w});
    }
    for(int i=0; i<s; i++)
    {
        int c; cin >> c;
        sh[c] = 1;
    }
    et(e, 0);
    while(q--)
    {
        int r; cin >> bc >> r;
        int u = cel[bc].fi, v = cel[bc].se;
        if(r == u || r == v)
        {
            if(tin[u] < tin[v] && tout[v] < tout[u])
            {
                if(tin[u] < tin[r] && tout[r] < tout[u]) cout << 0 << '\n';
                else cout << "escaped\n";
            }
            else
            {
                if(tin[v] < tin[r] && tout[r] < tout[v]) cout << 0 << '\n';
                else cout << "escaped\n";
            }
        }
        else
        {
            if(tin[u] < tin[r] && tout[r] < tout[u]) cout << 0 << '\n';
            else cout << "escaped\n";
        }
    }

    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...