Submission #684170

#	Time	Username	Problem	Language	Result	Execution time	Memory
684170		finn__	Railway (BOI17_railway)	C++17	36 / 100	123 ms	30404 KiB

railway

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

vector<vector<pair<unsigned, unsigned>>> g;
vector<vector<unsigned>> jmp;
vector<unsigned> height, pre, ans;
vector<int> val;

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

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

    for (size_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];
}

unsigned traverse(
    vector<unsigned> &path, unsigned u, unsigned p, unsigned h, unsigned i)
{
    for (unsigned i = 1; i <= path.size(); i <<= 1)
        jmp[u].push_back(path[path.size() - i]);
    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(unsigned u, unsigned 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);

    size_t n, m, k;
    cin >> n >> m >> k;

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

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

    vector<unsigned> path;
    traverse(path, 0, -1, 0, 0);

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

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

    calc_ans(0, -1);

    unsigned c = 0;
    for (unsigned const &x : ans)
        c += (x >= 2 * k);
    cout << c << '\n';
    for (size_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