Submission #555758

#	Time	Username	Problem	Language	Result	Execution time	Memory
555758		status_coding	Valley (BOI19_valley)	C++14	100 / 100	325 ms	27004 KiB

valley

#include <bits/stdc++.h>

using namespace std;

long long n, nr, q, t, e;

vector<pair<int, int>> edges;

bool isShop[100005];

long long d[100005];
long long dp[100005];

int in[100005], out[100005];

vector<pair<long long, long long>> v[100005];

vector<pair<int, int>> qv[100005];

long long ans[100005];


vector<long long> seg;

void upd(int stt, int drt, int st, int dr, int p, long long val)
{
    if(stt == st && drt == dr)
    {
        seg[p] = min(seg[p], val);
        return;
    }

    int mij = (st + dr)/2;

    if(drt <= mij)
        upd(stt, drt, st, mij, 2*p, val);
    else if(stt > mij)
        upd(stt, drt, mij+1, dr, 2*p+1, val);
    else
    {
        upd(stt, mij, st, mij, 2*p, val);
        upd(mij+1, drt, mij+1, dr, 2*p+1, val);
    }

}

long long query(int i, int st, int dr, int p)
{
    if(st == dr)
        return seg[p];

    int mij = (st+dr)/2;

    if(i <= mij)
        return min(seg[p], query(i, st, mij, 2*p));
    else
        return min(seg[p], query(i, mij+1, dr, 2*p+1));
}

void dfs(int p, int par)
{
    t++;
    in[p] = t;

    if(isShop[p])
        dp[p] = 0;
    else
        dp[p] = 1e18;

    for(auto it : v[p])
    {
        if(it.first == par)
            continue;

        d[it.first] = d[p] + it.second;
        dfs(it.first, p);

        dp[p] = min(dp[p], dp[it.first] + it.second);
    }

    out[p] = t;
}

void calc(int p, int par)
{
    for(auto it : v[p])
    {
        if(it.first == par)
            continue;

        calc(it.first, p);
    }

    upd(in[p], out[p], 1, n, 1, dp[p] - d[p]);

    for(auto it : qv[p])
    {
        int pozQ = it.first;
        int idQ = it.second;

        if(in[p] <= in[pozQ] && in[pozQ] <= out[p])
            ans[idQ] = query(in[pozQ], 1, n, 1) + d[pozQ];

        else
            ans[idQ] = -1;
    }
}

int main()
{
    cin>>n>>nr>>q>>e;

    seg.resize(4*n+4);
    fill(seg.begin(), seg.end(), 1e18);

    edges.push_back({0, 0});
    for(int i=1;i<n;i++)
    {
        long long x, y, w;
        cin>>x>>y>>w;

        v[x].push_back({y, w});
        v[y].push_back({x, w});

        edges.push_back({x, y});
    }

    for(int i=1;i<=nr;i++)
    {
        int x;
        cin>>x;

        isShop[x] = true;
    }

    dfs(e, 0);

    for(int i=1; i<=n; i++)
        upd(in[i], in[i], 1, n, 1, dp[i] - d[i]);

    for(int i=1;i<=q;i++)
    {
        int id, p;
        cin>>id>>p;

        int x = edges[id].first;
        int y = edges[id].second;

        if(d[x] > d[y])
            swap(x, y);

        qv[y].push_back({p, i});
    }

    calc(e, 0);

    for(int i=1;i<=q;i++)
    {
        if(ans[i] == -1)
            cout<<"escaped\n";
        else
        {
            if(ans[i] == 1e18)
                cout<<"oo\n";
            else
                cout<<ans[i]<<'\n';
        }

    }
    return 0;
}

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