Submission #684189

#	Time	Username	Problem	Language	Result	Execution time	Memory
684189		finn__	Railway (BOI17_railway)	C++17	36 / 100	153 ms	40436 KiB

railway

#include <bits/stdc++.h>
using namespace std;

vector<vector<pair<uint64_t, uint64_t>>> g;
vector<vector<uint64_t>> jmp;
vector<uint64_t> height, pre, ans;
vector<int64_t> val;

uint64_t lift(uint64_t u, uint64_t h)
{
    uint64_t z = 0;
    while (h)
    {
        if (h & 1)
            u = jmp[u][z];
        h >>= 1;
        z++;
    }
    return u;
}

uint64_t lca(uint64_t u, uint64_t v)
{
    if (height[u] < height[v])
        swap(u, v);
    u = lift(u, height[u] - height[v]);
    if (u == v)
        return u;

    for (uint64_t i = jmp[u].size() - 1; i < jmp[u].size(); i--)
        if (jmp[u][i] != jmp[v][i])
            u = jmp[u][i], v = jmp[v][i];

    return jmp[u][0];
}

uint64_t traverse(
    vector<uint64_t> &path, uint64_t u, uint64_t p, uint64_t h, uint64_t i)
{
    for (uint64_t j = 1; j <= path.size(); j <<= 1)
        jmp[u].push_back(path[path.size() - j]);
    height[u] = h;
    path.push_back(u);
    pre[u] = i++;

    for (auto const &[v, j] : g[u])
        if (v != p)
            i = traverse(path, v, u, h + 1, i);

    path.pop_back();
    return i;
}

void calc_ans(uint64_t u, uint64_t p)
{
    for (auto const &[v, j] : g[u])
    {
        if (v != p)
        {
            calc_ans(v, u);
            ans[j] = val[v];
            val[u] += val[v];
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    uint64_t n, m, k;
    cin >> n >> m >> k;

    g = vector<vector<pair<uint64_t, uint64_t>>>(n);
    jmp = vector<vector<uint64_t>>(n);
    height = vector<uint64_t>(n);
    pre = vector<uint64_t>(n);
    ans = vector<uint64_t>(n - 1);
    val = vector<int64_t>(n, 0);

    for (uint64_t i = 0; i < n - 1; i++)
    {
        uint64_t u, v;
        cin >> u >> v;
        g[u - 1].emplace_back(v - 1, i);
        g[v - 1].emplace_back(u - 1, i);
    }

    vector<uint64_t> path;
    assert(traverse(path, 0, -1, 0, 0) == n);

    for (uint64_t i = 0; i < m; i++)
    {
        uint64_t s;
        cin >> s;
        vector<pair<uint64_t, uint64_t>> y(s);
        for (auto &[j, u] : y)
        {
            cin >> u;
            u--;
            j = pre[u];
        }
        sort(y.begin(), y.end());
        y.resize(unique(y.begin(), y.end()) - y.begin());

        for (uint64_t j = 0; j < y.size(); j++)
        {
            val[y[j].second]++;
            val[y[(j + 1) % y.size()].second]++;
            val[lca(y[j].second, y[(j + 1) % y.size()].second)] -= 2;
        }
    }

    calc_ans(0, -1);

    uint64_t c = 0;
    for (uint64_t const &x : ans)
        c += (x >= (2 * k));
    cout << c << '\n';
    for (uint64_t i = 0; i < n - 1; i++)
        if (ans[i] >= 2 * k)
            cout << i + 1 << ' ';
    cout << '\n';
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 15
• Subtask 3: 7 / 7
• Subtask 4: 29 / 29
• Subtask 5: 0 / 16
• Subtask 6: 0 / 25