Submission #907516

#	Time	Username	Problem	Language	Result	Execution time	Memory
907516		I_FloPPed21	Valley (BOI19_valley)	C++14	23 / 100	83 ms	20284 KiB

valley

#include <iostream>
#include <vector>
using namespace std;

int n, s, q, e ;
vector<pair<int,int>> edge [200005];
long long tin[200005], tout [200005];

vector<int> v;
void dfs ( int nod,int p )
{
    v.push_back(nod);
    if (tin[nod] == 0 )
    {
        tin [nod] = v.size() ;
    }
    for ( auto u : edge[nod] )
    {
        if ( u.first != p)
        {
            dfs (u.first, nod );
            v.push_back(nod);
        }
    }

    tout[nod] = v.size();
}

vector<pair<int,int>> qr;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> s >> q >> e;

    for ( int i =1; i < n ; i ++ )
    {
        int a, b,c;
        cin >> a >> b>>c;
        edge[a].push_back({b,c});
        edge[b].push_back({a,c});
        qr.push_back({a,b});
    }

    dfs(e,0);


    for( int i = 1; i <= s; i ++ )
    {
        int val;
        cin >> val ;
    }
    for ( int i = 1; i <= q; i ++ )
    {
        int l, r;
        cin >> l >> r ;
        l -- ;
        int  a = qr[l].first;
        int b = qr[l].second;

        int tg ;

        if ( tin[a] < tin[b] && tout[a] > tout[b])
            tg =b ;
        else
            tg = a;

        if ( tin[tg] <= tin[r] && tout[tg] >= tout[r])
        {
            cout << 0 << '\n';
        }
        else
            cout << "escaped" << '\n';
    }
    return 0;
}

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