Submission #559461

#	Time	Username	Problem	Language	Result	Execution time	Memory
559461		four_specks	Railway (BOI17_railway)	C++17	100 / 100	201 ms	42692 KiB

railway

#include <bits/stdc++.h>

using namespace std;

inline namespace
{
    template <typename Fun>
    struct YCombinator
    {
        template <typename T>
        YCombinator(T &&_fun) : fun(forward<T>(_fun)) {}

        template <typename... Args>
        decltype(auto) operator()(Args &&...args) { return fun(ref(*this), forward<Args>(args)...); }

    private:
        Fun fun;
    };

    template <typename T>
    YCombinator(T &&) -> YCombinator<decay_t<T>>;

    template <typename T, typename Op>
    struct SparseTable
    {
        SparseTable(const vector<T> &vec, Op _op = Op())
            : op(_op), sz((int)vec.size())
        {
            table.push_back(vec);
            for (int k = 1; k <= __lg(sz); k++)
            {
                table.emplace_back(sz - (1 << k) + 1);
                for (int i = 0; i + (1 << k) <= sz; i++)
                    table[k][i] = op(table[k - 1][i], table[k - 1][i + (1 << (k - 1))]);
            }
        }

        T query(int l, int r) const
        {
            int k = __lg(r - l);
            return op(table[k][l], table[k][r - (1 << k)]);
        }

        T get(int l) const { return table[0][l]; }

        int size() const { return sz; }

    private:
        Op op;

        int sz;
        vector<vector<T>> table;
    };

    struct LCA
    {
        LCA(vector<vector<int>> &_adj, int _root = 0)
            : n((int)_adj.size()), root(_root), st(n), level(n), rmq(dfs(_adj), min)
        {
        }

        int query(int a, int b) const
        {
            if (a == b)
                return a;

            if (st[a] > st[b])
                swap(a, b);

            return path[rmq.query(st[a], st[b])];
        }

        int depth(int a) const { return level[a]; }

        int dist(int a, int b) const { return depth(a) + depth(b) - 2 * depth(query(a, b)); }

    private:
        int n;
        int root;

        vector<int> st, path, level;
        SparseTable<int, const int &(*)(const int &, const int &)> rmq;

        vector<int> dfs(vector<vector<int>> &adj)
        {
            vector<int> ret;
            path.reserve(n), ret.reserve(n);

            int timer = 0;

            auto yc = [&](auto self, int u, int p, int d) -> void
            {
                st[u] = timer++;
                level[u] = d;

                for (int v : adj[u])
                {
                    if (v != p)
                    {
                        path.push_back(u), ret.push_back(st[u]);
                        self(self, v, u, d + 1);
                    }
                }
            };

            yc(yc, root, -1, 0);

            return ret;
        };
    };

} // namespace

void solve()
{
    int n;
    int m, k;
    cin >> n >> m >> k;

    vector<vector<int>> adj(n);
    vector<vector<array<int, 2>>> gr(n);
    for (int i = 0; i < n - 1; i++)
    {
        int a, b;
        cin >> a >> b, --a, --b;

        adj[a].push_back(b),
        adj[b].push_back(a);
        gr[a].push_back({b, i}),
        gr[b].push_back({a, i});
    }

    LCA lca(adj);

    vector<vector<int>> change(n);
    for (int w = 0; w < m; w++)
    {
        int s;
        cin >> s;

        vector<int> c(s);
        for (int &a : c)
            cin >> a, --a;

        int l = lca.query(c[0], c[1]);
        for (int i = 2; i < s; i++)
            l = lca.query(l, c[i]);

        for (int a : c)
            change[a].push_back(w);
        change[l].push_back(~w);
    }

    vector<int> cnt(n - 1);

    YCombinator(
    [&](auto self, int u, int p) -> set<int>
    {
        set<int> st;
        for (auto [v, i] : gr[u])
        {
            if (v != p)
            {
                set<int> st1 = self(v, u);
                cnt[i] = (int)st1.size();
                if ((int)st.size() < (int)st1.size())
                    swap(st, st1);
                while (!st1.empty())
                {
                    auto it = st1.begin();
                    st.insert(*it);
                    st1.erase(it);
                }
            }
        }
        for (int w : change[u])
        {
            if (w >= 0)
                st.insert(w);
        }
        for (int w : change[u])
        {
            if (w < 0)
                st.erase(~w);
        }

        return st;
    })(0, -1);

    vector<int> tracks;
    for (int i = 0; i < n - 1; i++)
    {
        if (cnt[i] >= k)
            tracks.push_back(i);
    }

    cout << (int)tracks.size() << '\n';
    for (int track : tracks)
        cout << track + 1 << ' ';
    cout << '\n';
}

int main()
{
    ios_base::sync_with_stdio(false), cin.tie(NULL);

    solve();

    return 0;
}

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