제출 #589314

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
589314		danikoynov	Valley (BOI19_valley)	C++14	0 / 100	315 ms	13136 KiB

valley

/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 1e5 + 10;

int n, s, q, e;
bool shop[maxn];

vector < pair < int, int > > g[maxn];
int in[maxn], out[maxn], timer, lvl[maxn];
void dfs(int v, int p)
{
    in[v] = ++ timer;
    for (pair < int, int > nb : g[v])
    {
        int u = nb.first;
        if (u == p)
            continue;
        lvl[u] = lvl[v] + 1;
            dfs(u, v);
    }
    out[v] = timer;
}

bool in_subtree(int v, int u)
{
    if (in[v] <= in[u] && out[v] >= out[u])
        return true;
    return false;
}


pair < int, int > edge[maxn];

void solve()
{
    cin >> n >> s >> q >> e;
    for (int i = 1; i < n; i ++)
    {
        int v, u, w;
        cin >> v >> u >> w;
        g[v].push_back({u, w});
        g[u].push_back({v, w});
        edge[i] = {v, u};
    }

    for (int i = 1; i <= s; i ++)
    {
        int v;
        cin >> v;
        shop[v] = true;
    }

    dfs(e, -1);

    for (int i = 1; i < n; i ++)
        if (lvl[edge[i].first] > lvl[edge[i].second])
        swap(edge[i].first, edge[i].second);

    for (int i = 1; i <= q; i ++)
    {
        int id, v;
        cin >> id >> v;
        if (in_subtree(edge[id].second, v))
            cout << "oo" << endl;
        else
        cout << "escaped" << endl;

    }

}

int main()
{
    solve();
    return 0;
}

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