Submission #851015

#	Time	Username	Problem	Language	Result	Execution time	Memory
851015		anhphant	Railway (BOI17_railway)	C++14	36 / 100	88 ms	29384 KiB

railway

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

constexpr size_t N = 100000;

size_t n, m, k, ans[N], l;
vector<pair<int, int>> g[N];
vector<int> anc[N];
int x[N], h[N], r[N], preorder[N];

int trav(int u, int p, vector<int> &path, int j = 0)
{
    preorder[u] = j++;
    h[u] = path.size();
    for (size_t i = 1; i <= path.size(); i <<= 1)
        anc[u].push_back(path[path.size() - i]);
    path.push_back(u);
    for (auto const &[v, _] : g[u])
        if (v != p)
            j = trav(v, u, path, j);
    path.pop_back();
    return j;
}

int lift(int u, int y)
{
    int z = 0;
    while (y)
    {
        if (y & 1)
            u = anc[u][z];
        y >>= 1;
        ++z;
    }
    return u;
}

int lca(int u, int v)
{
    if (h[u] < h[v])
        u ^= v, v ^= u, u ^= v;
    u = lift(u, h[u] - h[v]);
    if (u == v)
        return u;
    for (size_t i = anc[u].size() - 1; i < anc[u].size(); --i)
        if (anc[u][i] != anc[v][i])
            u = anc[u][i], v = anc[v][i];
    return anc[u][0];
}

void sum(int u, int p)
{
    for (auto const &[v, i] : g[u])
        if (v != p)
            sum(v, u), x[u] += x[v], ans[i] = x[v], l += x[v] >= 2 * k;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> k;

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

    for (size_t i = 0; i < m; ++i)
    {
        int s;
        cin >> s;
        for (size_t j = 0; j < s; ++j)
            cin >> r[j], --r[j];
        sort(r, r + s, [](int const &u, int const &v)
             { return preorder[u] < preorder[v]; });
        r[s] = r[0];
        for (size_t j = 0; j < s; ++j)
            ++x[r[j]], ++x[r[j + 1]], x[lca(r[j], r[j + 1])] -= 2;
    }
    sum(0, -1);
    cout << l << '\n';
    for (size_t i = 0; i < n - 1; ++i)
        if (ans[i] >= 2 * k)
            cout << i + 1 << ' ';
    cout << '\n';
}

Compilation message (stderr)

railway.cpp: In function 'int trav(int, int, std::vector<int>&, int)':
railway.cpp:18:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   18 |     for (auto const &[v, _] : g[u])
      |                      ^
railway.cpp: In function 'void sum(int, int)':
railway.cpp:53:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   53 |     for (auto const &[v, i] : g[u])
      |                      ^
railway.cpp:55:63: warning: comparison of integer expressions of different signedness: 'int' and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
   55 |             sum(v, u), x[u] += x[v], ans[i] = x[v], l += x[v] >= 2 * k;
      |                                                          ~~~~~^~~~~~~~
railway.cpp: In function 'int main()':
railway.cpp:78:30: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   78 |         for (size_t j = 0; j < s; ++j)
      |                            ~~^~~
railway.cpp:83:30: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   83 |         for (size_t j = 0; j < s; ++j)
      |                            ~~^~~

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