Submission #871961

#	Time	Username	Problem	Language	Result	Execution time	Memory
871961		sleepntsheep	Railway (BOI17_railway)	C++17	100 / 100	76 ms	17112 KiB

railway

#include <iostream>
#include <cassert>
#include <stack>
#include <cstring>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#include <utility>
#include <array>

using i64 = long long;
using u64 = unsigned long long;
using f64 = double;
using f80 = long double;

using namespace std;
#define ALL(x) x.begin(), x.end()
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false);
#define N 100000

int n, m, k, h[N], alloc, tin[N], tout[N], timer, P[N], J[N], L[N], CH[N], CI[N], HC[N], htimer, t[N+2], EID[N], RV[N];
struct {int v, l; } g[2*N-1];

inline void add_edge(int u, int v) { g[++alloc] = {v, h[u]}; h[u] = alloc; }

int dfs(int u, int p)
{
    int hvsz{-1}, sz{1};
    tin[u] = ++timer; HC[u] = -1;
    for (auto j = h[u]; j; j = g[j].l) if (g[j].v != p)
    {
        P[g[j].v] = u; L[g[j].v] = L[u] + 1;
        if (L[u] - L[J[u]] == L[J[u]] - L[J[J[u]]]) J[g[j].v] = J[J[u]];
        else J[g[j].v] = u;
        int sub {dfs(g[j].v, u)};
        EID[g[j].v] = j;
        if (sub > hvsz) HC[u] = g[j].v, hvsz = sub;
        sz += sub;
    }
    tout[u] = timer;
    return sz;
}

void hld(int u, int hh)
{
    RV[CI[u] = ++htimer] = u; CH[u] = hh;
    if (HC[u] != -1) hld(HC[u], hh);
    for (auto j = h[u]; j; j = g[j].l)
        if (g[j].v != P[u] && g[j].v != HC[u]) hld(g[j].v, g[j].v);
}

inline int kth(int u, int k)
{
    int dep { L[u] - k };
    for (; L[u] > dep;)
    {
        if (L[J[u]] >= dep) u = J[u];
        else u = P[u];
    }
    return u;
}

inline int lca(int u, int v)
{
    if (L[u] < L[v]) swap(u, v);
    for (; L[u] > L[v];)
    {
        if (L[J[u]] >= L[v]) u = J[u];
        else u = P[u];
    }
    for (; u != v;)
    {
        if (J[u] == J[v]) u = P[u], v = P[v];
        else u = J[u], v = J[v];
    }
    return u;
}

inline void updup(int u, int a)
{
    assert(L[u] >= L[a] && tin[a] <= tin[u] && tout[u] <= tout[a]);
    for (; CH[u] != CH[a]; u = P[CH[u]])
    {
        ++t[CI[CH[u]]];
        --t[CI[u]+1];
    }
    ++t[CI[a]];
    --t[CI[u]+1];
}

int main()
{
    ShinLena;
    cin >> n >> m >> k;
    for (int i = 1, u, v; i < n; ++i) cin >> u >> v, --u, --v, add_edge(u, v), add_edge(v, u);

    dfs(0, 0);
    hld(0, 0);

    for (int s, i = 0; i < m; ++i)
    {
        cin >> s;
        vector<pair<int, int>> a(s);
        for (auto &[x, y] : a) cin >> y, --y, x = tin[y];
        sort(ALL(a));
        for (u64 y = a.size(), i = 1; i < y; ++i)
        {
            int lc = lca(a[i].second, a[i-1].second);
            a.emplace_back(tin[lc], lc);
        }
        sort(ALL(a));
        a.erase(unique(ALL(a)), a.end());
        stack<int> st;
        for (auto [_, x] : a)
        {
            while (st.size() && !(tin[st.top()] <= tin[x] && tout[x] <= tout[st.top()])) st.pop();
            if (st.size()) updup(x, kth(x, L[x] - L[st.top()] - 1));
            st.push(x);
        }
    }

    vector<int> ans;
    for (auto i = 1; i <= n; ++i)
    {
        t[i] += i ? t[i-1] : 0;
        if (t[i] >= k) ans.push_back((1+EID[RV[i]])/2);
    }
    sort(ALL(ans));
    cout << ans.size() << '\n';
    for (auto x : ans) cout << x << ' ';

    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