Submission #898796

#	Time	Username	Problem	Language	Result	Execution time	Memory
898796		vjudge1	Valley (BOI19_valley)	C++17	23 / 100	244 ms	20052 KiB

valley

#include <bits/stdc++.h>
#define pb push_back
#define f first
#define s second
#define dbg(x) cout << "reached here " << x << endl;
#define int long long 

using namespace std;
typedef pair<int, int> pii;

struct edge {int o, d, w, id;};

const int maxn = 1e5+5, inf = (int)100000*100000*100000;
int dis[maxn], E, st[maxn], ft[maxn], t = 1;
vector<edge> adj[maxn];
edge yal[maxn];

void dfs(int v, int par)
{
    st[v] = t;
    t++;
    for (auto e: adj[v])
    {
        int u = e.o^e.d^v;
        if(u != par)
        {
            dis[u] = dis[v] + 1;
            dfs(u, v);
        }
    }
    ft[v] = t;
    t++;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, s, q;
    cin >> n >> s >> q >> E;

    for (int i = 1; i <= n-1; ++i)
    {
        cin >> yal[i].o >> yal[i].d >> yal[i].w;
        yal[i].id = i;

        adj[yal[i].o].pb(yal[i]);
        adj[yal[i].d].pb(yal[i]);
    }

    for (int i = 1; i <= s; ++i)
    {
        int a;
        cin >> a;
    }

    dfs(E, 0);

    while(q--)
    {
        int l, r;
        cin >> l >> r;

        int v = yal[l].o;
        if(dis[yal[l].o] < dis[yal[l].d])
            v = yal[l].d;

        if(st[r] >= st[v] and ft[r] <= ft[v])
            cout << 0 << endl;
        else
            cout << "escaped" << endl;            
    }


    return 0;
}

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