Submission #200560

#	Time	Username	Problem	Language	Result	Execution time	Memory
200560		johutha	Valley (BOI19_valley)	C++17	59 / 100	3021 ms	29928 KiB

valley

#include <vector>
#include <iostream>

#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;
    int n;
    int logn;
    int rt;
    vector<bool> shop;

    void builddfs(int curr, int par, int l)
    {
        lvl[curr] = l;
        lcatable[0][curr] = par;

        for (auto p : adjlist[curr])
        {
            auto next = p.first;
            if (next == par) continue;
            builddfs(next, curr, l + 1);
        }
    }

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

        builddfs(rt, -1, 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 ldiff = lvl[a] - lvl[b];

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

        if (a == b) return a;

        for (int i = 0; i < logn; i++)
        {
            if (lcatable[i][a] != lcatable[i][b])
            {
                a = lcatable[i][a];
                b = lcatable[i][b];
            }
        }

        return lcatable[0][a];
    }

    int ddfs(int curr, int par, pair<int,int> fb)
    {
        // cerr << curr << " " << shop[curr] << "\n";
        if (shop[curr] == true) return 0;
        int mmin = 1e15;

        for (auto p : adjlist[curr])
        {
            int next = p.first;
            if (next == par) continue;
            if (min(fb.first, fb.second) == min(curr, next) && max(fb.first, fb.second) == max(curr, next)) continue;
            mmin = min(mmin, p.second + ddfs(next, curr, fb));
        }
        return mmin;
    }
};

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

    graph g;
    g.rt = r - 1;
    g.n = n;
    g.adjlist.resize(n);
    g.shop.resize(n, false);
    
    vector<pair<int,int>> edges;

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

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

    g.build();

    for (int i = 0; i < q; i++)
    {
        int r, v;
        cin >> r >> v;
        r--;
        v--;
        auto p = edges[r];
        if (g.lvl[p.first] > g.lvl[p.second]) swap(p.first, p.second);

        if (g.lca(p.second, v) != p.second)
        {
            cout << "escaped\n";
            continue;
        }

        int d = g.ddfs(v, -1, p);
        if (d >= 1e15)
        {
            cout << "oo\n";
        }
        else
        {
            cout << d << "\n";
        }
    }
}

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