oj.uz

답안 #589316

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
589316 2022-07-04T12:47:58 Z danikoynov Valley (BOI19_valley) C++14
23 / 100
 339 ms 15560 KB 
/**
 ____ ____ ____ ____ ____ ____
||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 << 0 << endl;
        else
        cout << "escaped" << endl;

    }

}

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

Subtask #1
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 17 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 17 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 315 ms 9164 KB Output is correct
2 Correct 314 ms 12748 KB Output is correct
3 Correct 328 ms 12672 KB Output is correct
4 Correct 339 ms 14136 KB Output is correct
5 Correct 330 ms 14156 KB Output is correct
6 Correct 306 ms 15560 KB Output is correct

Subtask #4
0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 17 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -