Submission #200557

#	Time	Username	Problem	Language	Result	Execution time	Memory
200557		johutha	Valley (BOI19_valley)	C++14	0 / 100	630 ms	55364 KiB

valley

#include <iostream>
#include <memory>
#include <vector>

#define int int64_t

using namespace std;

int log2(int n)
{
    int res = 0;
    for (; n; n >>= 1) res++;
    return res;
}

struct graph
{
    vector<vector<pair<int,int>>> adjlist;
    vector<vector<int>> lcatable;
    vector<int> lvl;
    vector<int> submxdist;
    vector<int> premx;
    vector<int> premxdist;
    vector<bool> shop;
    int n;
    int logn;
    int rt;

    int dfs(int curr, int par, int pm, int pmd, int lv)
    {
        lvl[curr] = lv;
        lcatable[0][curr] = par;
        premx[curr] = pm;
        premxdist[curr] = pmd;
        if (shop[curr])
        {
            premxdist[curr] = 0;
            premx[curr] = curr;
        }

        int md = 1e15;

        for (auto p : adjlist[curr])
        {
            int next = p.first;
            if (next == par) continue;
            md = min(md, p.second + dfs(next, curr, premx[curr], premxdist[curr] + p.second, lv + 1));
        }
        submxdist[curr] = md;

        return (shop[curr] ? 0 : md);
    }

    void build()
    {
        logn = log2(n);
        lcatable.resize(logn, vector<int>(n - 1));
        premx.resize(n, -1);
        submxdist.resize(n, 1e14);
        premxdist.resize(n, 1e14);
        lvl.resize(n);

        dfs(rt, -1, rt, 0, 0);

        for (int l = 1; l < logn; l++)
        {
            for (int i = 0; i < n; i++)
            {
                lcatable[l][i] = (lcatable[l - 1][i] == -1 ? -1 : lcatable[l - 1][lcatable[l - 1][i]]);
            }
        }
    }

    int lca(int a, int b)
    {
        if (lvl[a] < lvl[b]) swap(a, b);
        int ld = lvl[a] - lvl[b];

        int e = 1;
        for (int i = 0; i < logn; i++)
        {
            if (ld & e) a = lcatable[i][a];
            e *= 2;
        }

        if (a == b) return a;

        for (int i = logn - 1; i >= 0; i--)
        {
            if (lcatable[i][a] != lcatable[i][b])
            {
                a = lcatable[i][a];
                b = lcatable[i][b];
            }
        }
        return lcatable[0][a];
    }

    void print()
    {
        for (auto i : lvl) cout << i << " ";
        cout << "\n";
        for (auto i : submxdist) cout << i << " ";
        cout << "\n";
        for (auto i : premx) cout << i << " ";
        cout << "\n";
        for (auto i : premxdist) cout << i << " ";
        cout << "\n";
    }
};

signed main()
{
    int n, s, q, e;
    cin >> n >> s >> q >> e;

    graph g;
    g.n = n;
    g.adjlist.resize(n);
    g.shop.resize(n, false);
    g.rt = e - 1;

    vector<pair<int,int>> edges;

    for (int i = 0; i < n - 1; i++)
    {
        int a, b, w;
        cin >> a >> b >> w;
        a--; b--;
        g.adjlist[a].emplace_back(b, w);
        g.adjlist[b].emplace_back(a, w);
        edges.emplace_back(a, b);
    }

    for (int i = 0; i < s; i++)
    {
        int p;
        cin >> p;
        p--;
        g.shop[p] = true;
    }

    g.build();
    // g.print();

    for (int i = 0; i < q; i++)
    {
        //cerr << "Ok\n";
        int ed, ps;
        cin >> ed >> ps;
        ed--; ps--;
        // cerr << "Ok\n";
        pair<int,int> e = edges[ed];
        // cerr << "Ok\n";
        if (g.lvl[e.first] > g.lvl[e.second]) swap(e.first, e.second);
        if (g.lca(e.second, ps) != e.second)
        {
            cout << "escaped\n";
            continue;
        }
        int mmin = g.submxdist[ps];
        if (g.lvl[e.first] < g.lvl[ps]) mmin = min(mmin, g.premxdist[ps]);
        if (mmin >= 1e15) cout << "oo\n";
        else cout << mmin << "\n";
    }
}

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