Submission #1278984

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278984		domi	Railway (BOI17_railway)	C++20	7 / 100	81 ms	84396 KiB

railway

#include <bits/stdc++.h>

#define int long long
#define fi first
#define se second

#define sz(a) (int)((a).size())
#define all(a) (a).begin(), (a).end()

#define lsb(x) (x & (-x))
#define vi vector<int>
#define YES { cout << "YES" << endl; return; }
#define NO { cout << "NO" << endl; return; }

using ll = long long;
using pii = std::pair<int, int>;

const int NMAX = 1e5;

using namespace std;

template<class T>
struct RMQ {
    vector<vector<T>> rmq;
    T kInf = numeric_limits<T>::max();

    void build(const vector<T>& V) {
        int n = (int) V.size(), on = 1, dep = 1;
        while (on < n) on *= 2, ++dep;
        rmq.assign(dep, V);

        for (int i = 0; i < dep - 1; i++) {
            for (int j = 0; j < n; j++) {
                int nj = min(n - 1, j + (1 << i));
                rmq[i + 1][j] = min(rmq[i][j], rmq[i][nj]);
            }
        }
    }

    T query(int a, int b) {
        if (b <= a) return kInf;
        int dep = 31 - __builtin_clz(b - a);
        return min(rmq[dep][a], rmq[dep][b - (1 << dep)]);
    }
};

struct LCA {
    vector<int> enter, depth, ex;
    vector<vector<int>> G;
    vector<pair<int, int>> linear;
    RMQ<pair<int, int>> rmq;
    int timer = 0;

    LCA() {}

    LCA(int n) : enter(n, -1), depth(n), ex(n), G(n), linear(2 * n) {}

    void dfs(int v, int d) {
        linear[timer] = { d, v };
        enter[v] = timer++;
        depth[v] = d;

        for (int to : G[v]) {
            if (enter[to] == -1) {
                dfs(to, d + 1);
                linear[timer++] = { d, v };
            }
        }
        ex[v] = timer;
    }

    void add_edge(int a, int b) {
        G[a].push_back(b);
        G[b].push_back(a);
    }

    void build(int root) {
        fill(enter.begin(), enter.end(), -1);
        timer = 0;
        dfs(root, 0);
        rmq.build(linear);
    }

    int query(int a, int b) {
        a = enter[a];
        b = enter[b];
        return rmq.query(min(a, b), max(a, b) + 1).second;
    }

    int dist(int a, int b) {
        int c = query(a, b);
        return depth[a] + depth[b] - 2 * depth[c];
    }
};

LCA lca;
vector<int>T[NMAX + 5];
int a[NMAX + 5], in[NMAX + 5], mars[NMAX + 5], n, m, k, timer = 0;

void dfs_ord(int nod, int p = -1) {
    in[nod] = timer++;
    for (auto &son : T[nod]) {
        if (son == p)continue;
        dfs_ord(son, nod);
    }
}

void dfs_mars(int nod, int p = -1) {
    for (auto &son : T[nod]) {
        if (son == p)continue;

        dfs_mars(son, nod);
        mars[nod] += mars[son];
    }
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> m >> k;

    lca = LCA(n + 5);
    for (int i = 1, u, v; i <= n - 1; ++i) {
        cin >> u >> v;
        T[u].push_back(v);
        T[v].push_back(u);
        lca.add_edge(u, v);
    }
    lca.build(1);

    dfs_ord(1);
    for (int i = 1, k; i <= m; ++i) {
        cin >> k;

        for (int j = 1; j <= k; ++j)
            cin >> a[j];

        sort(a + 1, a + k + 1, [](auto& a, auto& b) {
            return in[a] < in[b];
        });
        a[k + 1] = a[1];

        for (int j = 1; j <= k; ++j) {
            ++mars[a[j]];
            ++mars[a[j + 1]];
            mars[lca.query(a[j], a[j + 1])] -= 2;
        }
    }

    dfs_mars(1);
    vector<int>ans;
    for (int i = 1; i <= n; ++i) {
        if (mars[i] >= 2 * k)
            ans.push_back(in[i]);
    }

    sort(all(ans));
    cout << sz(ans) << '\n';
    for (auto &it : ans)
        cout << it << " \n"[it == ans.back()];
    return 0;
}

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