Submission #1138977

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138977		rayan_bd	Valley (BOI19_valley)	C++20	23 / 100	120 ms	11496 KiB

valley

#include <bits/stdc++.h>
using namespace std;

const int mxN = 1e5 + 100;

int st[mxN], en[mxN], seg[mxN * 12], edg[mxN], tim = 0;
vector<pair<int, int>> adj[mxN];

void update(int node, int start, int end, int idx, int val)
{
    if (start == end)
    {
        seg[node] = val;
        return;
    }
    int mid = start + (end - start) / 2;
    if (idx <= mid)
        update(node * 2 + 1, start, mid, idx, val);
    else
        update(node * 2 + 2, mid + 1, end, idx, val);
    seg[node] = seg[node * 2 + 1] + seg[node * 2 + 2];
}

int qry(int node, int start, int end, int l, int r)
{
    if (start > r || end < l)
        return 0;
    if (start >= l && end <= r)
        return seg[node];
    int mid = start + (end - start) / 2;
    return qry(node * 2 + 1, start, mid, l, r) + qry(node * 2 + 2, mid + 1, end, l, r);
}

void dfs(int u, int par = -1)
{
    st[u] = tim++;
    for (auto it : adj[u])
    {
        if (it.first ^ par)
        {
            edg[it.second] = it.first;
            dfs(it.first, u);
        }
    }
    en[u] = tim++;
}

void solve()
{
    int n, s, q, e, u, v, w;
    cin >> n >> s >> q >> e;
    for (int i = 0; i < n - 1; ++i)
    {
        cin >> u >> v >> w;
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
    }
    dfs(e);
    while (s--)
        cin >> u;
    while (q--)
    {
        cin >> e >> u;
        --e;
        update(0, 0, tim, st[edg[e]], 1);
        update(0, 0, tim, en[edg[e]], -1);
        if (qry(0, 0, tim, 0, st[u]) == 0)
            cout << "escaped\n";
        else
            cout << "0\n";
        update(0, 0, tim, st[edg[e]], 0);
        update(0, 0, tim, en[edg[e]], 0);
    }
}

signed main()
{

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    solve();
    return 0;
}

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