Submission #1099592

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099592		andrei_iorgulescu	Valley (BOI19_valley)	C++14	100 / 100	139 ms	57428 KiB

valley

#include <bits/stdc++.h>

using namespace std;

#define int long long

int inf = 1e18;

int n, s, q, e;
vector<pair<int, int>> g[100005], f[100005];
pair<int, int> t[100005];
int h[100005], d[100005], v[100005], h_real[100005];
int x[100005], y[100005], w[100005];
bool yup[100005], viz[100005];

int lg[100005];
int bl[20][100005], vl[20][100005];

void dfs(int nod)
{
    viz[nod] = true;
    d[nod] = inf;
    if (yup[nod])
        d[nod] = 0;
    for (auto vecin : g[nod])
    {
        if (!viz[vecin.first])
        {
            h[vecin.first] = h[nod] + vecin.second;
            h_real[vecin.first] = 1 + h_real[nod];
            t[vecin.first] = {nod, vecin.second};
            f[nod].push_back(vecin);
            dfs(vecin.first);
            d[nod] = min(d[nod], d[vecin.first] + vecin.second);
        }
    }
    v[nod] = d[nod] - h[nod];
}

int anc(int nod, int dh)
{
    for (int pas = lg[n]; pas >= 0; pas--)
    {
        if (dh - (1 << pas) >= 0)
        {
            dh -= (1 << pas);
            nod = bl[pas][nod];
        }
    }
    return nod;
}

int vv(int nod, int dh)
{
    int nod1 = nod;
    dh++;
    int mnm = inf;
    for (int pas = lg[n]; pas >= 0; pas--)
    {
        if (dh - (1 << pas) >= 0)
        {
            mnm = min(mnm, vl[pas][nod]);
            nod = bl[pas][nod];
            dh -= (1 << pas);
        }
    }
    return mnm + h[nod1];
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> s >> q >> e;
    for (int i = 1; i < n; i++)
    {
        cin >> x[i] >> y[i] >> w[i];
        g[x[i]].push_back({y[i], w[i]});
        g[y[i]].push_back({x[i], w[i]});
    }
    for (int i = 1; i <= s; i++)
    {
        int oras;
        cin >> oras;
        yup[oras] = true;
    }
    dfs(e);
    for (int i = 1; i < n; i++)
    {
        if (h[x[i]] > h[y[i]])
            swap(x[i], y[i]);
    }
    for (int i = 2; i <= n; i++)
        lg[i] = 1 + lg[i / 2];
    for (int i = 1; i <= n; i++)
        bl[0][i] = t[i].first;
    for (int j = 1; j <= lg[n]; j++)
        for (int i = 1; i <= n; i++)
            bl[j][i] = bl[j - 1][bl[j - 1][i]];
    for (int i = 1; i <= n; i++)
        vl[0][i] = v[i];
    //for (int i = 1; i <= n; i++)
      //  cout << v[i] << '\n';
    for (int j = 1; j <= lg[n]; j++)
        for (int i = 1; i <= n; i++)
            vl[j][i] = min(vl[j - 1][i], vl[j - 1][bl[j - 1][i]]);
    for (int i = 1; i <= q; i++)
    {
        int idx, r;
        cin >> idx >> r;
        if (h_real[r] < h_real[y[idx]] or anc(r, h_real[r] - h_real[y[idx]]) != y[idx])
            cout << "escaped\n";
        else
        {
            int dh = h_real[r] - h_real[y[idx]];
            int ans = vv(r, dh);
            if (ans >= inf / 10)
                cout << "oo\n";
            else
                cout << ans << '\n';
        }
    }
    return 0;
}

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