제출 #878208

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
878208		vjudge1	Railway (BOI17_railway)	C++17	100 / 100	97 ms	26572 KiB

railway

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

const int N = 1e5 + 10;
const int LG = 20;

int n, m, k;
int n1[N], n2[N], par[N][LG], h[N], st[N], ps[N], t;
vector<int> edj[N], ans;

void dfs_pre(int v = 1, int p = 0) {
    st[v] = t++, h[v] = h[p] + 1;
    par[v][0] = p;
    for (int lg = 1; lg < LG; lg++)
        par[v][lg] = par[par[v][lg - 1]][lg - 1];
    for (auto e : edj[v]) {
        int u = n1[e] ^ n2[e] ^ v;
        if (u ^ p) dfs_pre(u, v);
    }
}

int lca(int u, int v) {
    if (h[u] > h[v]) swap(u, v);
    int dist = h[v] - h[u];
    for (int lg = 0; lg < LG; lg++)
        if (dist & (1 << lg)) v = par[v][lg];
    if (u == v) return v;
    for (int lg = LG - 1; lg >= 0; lg--)
        if (par[v][lg] ^ par[u][lg])
            v = par[v][lg], u = par[u][lg];
    return par[v][0];
}

void dfs(int v = 1, int p = -1) {
    for (auto e : edj[v])
        if (e ^ p) {
            int u = n1[e] ^ n2[e] ^ v;
            dfs(u, e);
            ps[v] += ps[u];
        }
    if (ps[v] >= k) ans.pb(p);
}

int main() {
	ios:: sync_with_stdio(0), cin.tie(0);
    cin >> n >> m >> k;
    for (int i = 0; i < n - 1; i++) {
        cin >> n1[i] >> n2[i];
        edj[n1[i]].pb(i);
        edj[n2[i]].pb(i);
    }
    dfs_pre();
    while (m--) {
        int x;
        cin >> x;
        vector<int> vec(x);
        for (int i = 0; i < x; i++) cin >> vec[i];
        sort(vec.begin(), vec.end(), [](int p, int q) {return st[p] < st[q];});
        vec.pb(vec[0]);
        for (int i = 0; i < x; i++)
            ps[vec[i]]++, ps[lca(vec[i], vec[i + 1])] -= 1;
    }
    dfs();
    cout << ans.size() << '\n';
    sort(ans.begin(), ans.end());
    for (auto e : ans) cout << e + 1 << ' ';
    cout << '\n';
	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