Submission #1139211

#TimeUsernameProblemLanguageResultExecution timeMemory
1139211rayan_bdValley (BOI19_valley)C++20
59 / 100
3095 ms24680 KiB
#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int mxN = 1e5 + 100;
const ll INF = 1e18;

bool shop[mxN];
int st[mxN], en[mxN], seg[mxN * 12], edg[mxN], tim = 0;
vector<vector<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[0] ^ par)
        {
            edg[it[2]] = it[0];
            dfs(it[0], u);
        }
    }
    en[u] = tim++;
}


ll dfs_qry(int u, int block, int par)
{
    if (shop[u])
        return 0;
    ll answer = INF;
    for (auto it : adj[u])
    {
        if (it[0] ^ par && block != it[2])
        {
            answer = min(answer, dfs_qry(it[0], block, u) + it[1]);
        }
    }
    return answer;
}

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, w, i});
        adj[v].push_back({u, w, i});
    }
    dfs(e);
    while (s--)
    {
        cin >> u;
        shop[u] = 1;
    }
    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
        {
            ll answer = dfs_qry(u, e, -1);
            if (answer >= INF)
                cout << "oo\n";
            else
                cout << answer << '\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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...