Submission #725914

#	Time	Username	Problem	Language	Result	Execution time	Memory
725914		finn__	Railway (BOI17_railway)	C++17	0 / 100	4 ms	596 KiB

railway

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

template <typename T, int64_t... Ns>
struct FenwickTree
{
    T t = 0;
    void increment(T x) { t += x; }
    T range_sum() { return t; }
};

template <typename T, int64_t N, int64_t... Ns>
struct FenwickTree<T, N, Ns...>
{
    FenwickTree<T, Ns...> t[N];

    template <typename... Args>
    void increment(int64_t i, Args... a)
    {
        ++i;
        while (i <= N)
            t[i - 1].increment(a...), i += i & -i;
    }

    template <typename... Args>
    T range_sum(int64_t i, int64_t j, Args... a)
    {
        T x = 0;
        ++j;
        while (j)
            x += t[j - 1].range_sum(a...), j -= j & -j;
        while (i)
            x -= t[i - 1].range_sum(a...), i -= i & -i;
        return x;
    }
};

constexpr size_t N = 102;

size_t n, m, k;
vector<pair<int, int>> g[N];
vector<int> anc[N];
int h[N], r[N / 2], subtree_begin[N], subtree_end[N], ind[N];
FenwickTree<int, N> tree;

int trav(int u, int p, vector<int> &path, int j = 0)
{
    subtree_begin[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, i] : g[u])
        if (v != p)
        {
            j = trav(v, u, path, j);
            ind[v] = i;
        }
    path.pop_back();
    return (subtree_end[u] = j - 1) + 1;
}

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])
        swap(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];
}

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 subtree_begin[u] < subtree_begin[v]; });
        r[s] = r[0];
        for (size_t j = 0; j < s; ++j)
        {
            tree.increment(subtree_begin[r[j]], 1);
            tree.increment(subtree_begin[r[j + 1]], 1);
            tree.increment(subtree_begin[lca(r[j], r[j + 1])], -2);
        }
    }
    vector<int> ans;
    for (size_t i = 1; i < n; ++i)
        if (tree.range_sum(subtree_begin[i], subtree_end[i]) >= 2 * k)
            ans.push_back(ind[i]);
    cout << ans.size() << '\n';
    sort(ans.begin(), ans.end());
    for (int const &x : ans)
        cout << x + 1 << ' ';
}

Compilation message (stderr)

railway.cpp: In function 'int main()':
railway.cpp:109:30: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  109 |         for (size_t j = 0; j < s; ++j)
      |                            ~~^~~
railway.cpp:114:30: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  114 |         for (size_t j = 0; j < s; ++j)
      |                            ~~^~~
railway.cpp:123:62: warning: comparison of integer expressions of different signedness: 'int' and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
  123 |         if (tree.range_sum(subtree_begin[i], subtree_end[i]) >= 2 * k)
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~

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