제출 #1264258

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1264258		MinhKien	Railway (BOI17_railway)	C++20	0 / 100	50 ms	27068 KiB

railway

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

#define ii pair <int, int>
#define fi first
#define se second

const int N = 2e5 + 10;

int n, m, k, x, y;
int par[N], dp[N];
int num, a[N], tim, in[N], out[N];
int depth[N], up[N][20], Log2[N];
vector <ii> v[N];
vector <int> ans;
bool ck[N];

void DFS(int s = 1, int p = -1) {
    in[s] = out[s] = ++tim;

    for (ii z: v[s]) {
        if (z.se == p) continue;

        par[z.se] = s;
        depth[z.se] = depth[s] + 1;

        up[z.se][0] = s;
        for (int i = 1; i <= Log2[depth[z.se]]; ++i) {
            up[z.se][i] = up[up[z.se][i - 1]][i - 1];
        }

        DFS(z.se, s);
        out[s] = out[z.se];
    }
}

int LCA(int A, int B) {
    if (depth[A] < depth[B]) swap(A, B);

    int step = depth[A] - depth[B];

    for (int i = 0; i <= Log2[step]; ++i) {
        if (step >> i & 1) A = up[A][i];
    }

    if (A == B) return A;

    for (int i = Log2[depth[A]]; i >= 0; --i) {
        if (up[A][i] != up[B][i]) {
            A = up[A][i];
            B = up[B][i];
        }
    }

    return up[A][0];
}

void Path(int A, int B) {
    ++dp[A]; ++dp[B];
    dp[LCA(A, B)] -= 2;
}

bool cmp(const int &A, const int &B) {
    return in[A] < in[B];
}

void dodp(int s = 1, int la = -1) {
    for (ii z: v[s]) {
        if (z.fi == la) continue;
        dodp(z.se, z.fi);
        dp[s] += dp[z.se];
    }

    if (dp[s] / 2 >= k) ans.push_back(la);
}

int main() {
    cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(false);

    cin >> n >> m >> k;
    for (int i = 1; i < n; ++i) {
        cin >> x >> y;
        v[x].push_back(ii(i, y));
        v[y].push_back(ii(i, x));

        if (i >= 2) Log2[i] = Log2[i >> 1] + 1;
    }

    DFS();

    while (m--) {
        cin >> num;
        for (int i = 1; i <= num; ++i) cin >> a[i];
        sort(a + 1, a + num + 1, cmp);

        Path(a[1], a[num]);
        for (int i = 1; i < num; ++i) {
            Path(a[i], a[i + 1]);
        }
    }

    dodp();

    cout << ans.size() << "\n";
    for (int z: ans) cout << z << " ";

    return 0;
}

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