Submission #1264254

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264254		MinhKien	Railway (BOI17_railway)	C++20	0 / 100	53 ms	27580 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];
}

struct BIT {
    int val[N];

    void update(int u, int V) {
        while (u <= n) {
            val[u] += V;
            u += u & -u;
        }
    }

    int get(int u) {
        int res = 0;
        while (u > 0) {
            res += val[u];
            u -= u & -u;
        }
        return res;
    }

    int range(int l, int r) {
        return get(r) - get(l - 1);
    }
} bit;

void Path(int &A, int B) {
    int l = LCA(A, B);

    if (l != A) {
        ++dp[A]; ++dp[B];
        dp[l] -= 2;
        A = l;
    } else {
        if (bit.range(in[B], out[B]) == 0) {
            --dp[A]; ++dp[B];
        }
    }
}

bool cmp(const int &A, const int &B) {
    return depth[A] > depth[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] >= 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);

        int cur = a[1];
        bit.update(in[a[1]], 1);
        for (int i = 2; i <= num; ++i) {
            Path(cur, a[i]);
            bit.update(in[a[i]], 1);
        }

        for (int i = 1; i <= num; ++i) {
            bit.update(in[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