Submission #916794

#	Time	Username	Problem	Language	Result	Execution time	Memory
916794		uped	Railway (BOI17_railway)	C++14	100 / 100	252 ms	40652 KiB

railway

#include <bits/stdc++.h>
#define DEBUG(x) cout << #x << ": " << x << '\n';
using namespace std;

const int MAXN = 1e5 + 1;
const int LOGN = 20;
int depth[MAXN];
int euler[MAXN];
int jmp[LOGN][MAXN];
int starting[MAXN];
int ending[MAXN];
vector<int> adj[MAXN];

int timer = 0;
void init_lca(int n, int p = 0) {
    depth[n] =depth[p] + 1;
    jmp[0][n] = p;
    euler[n] = timer++;
    for (int x : adj[n]) {
        if (x == p) continue;
        init_lca(x, n);
    }
}

void init_lca() {
    init_lca(1);
    for (int i = 1; i < LOGN; ++i) {
        for (int j = 1; j < MAXN; ++j) {
            jmp[i][j] = jmp[i - 1][jmp[i - 1][j]];
        }
    }
}

int lca(int a, int b) {
    if (depth[a] < depth[b]) swap(a, b);
    for (int i = 0; i < LOGN; ++i) {
        if ((depth[a] - depth[b]) & (1 << i)) a = jmp[i][a];
    }
    if (a == b) return a;
    for (int i = LOGN - 1; i >= 0; --i) {
        int la = jmp[i][a];
        int lb = jmp[i][b];
        if (la != lb) {
            a = la;
            b = lb;
        }
    }
    return jmp[0][a];
}
map<pair<int, int>, int> edge_to_idx;
int ans[MAXN];

int solve(int n, int p = -1) {
    int k = starting[n];
    for (int x : adj[n]) {
        if (x == p) continue;
        k += solve(x, n);
    }
    k -= ending[n];
    ans[edge_to_idx[{n, p}]] = k;
    return k;
}

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 1; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
        edge_to_idx[{a, b}] = i;
        edge_to_idx[{b, a}] = i;
    }
    init_lca();
    for (int i = 0; i < m; ++i) {
        int s;
        cin >> s;
        vector<int> v(s);
        for (int i = 0; i < s; ++i) {
            cin >> v[i];
        }
        sort(v.begin(), v.end(), [&](int a, int b) {
            return euler[a] < euler[b];
        });

        int root = v[0];
        for (int i = 1; i < s; ++i) {
            root = lca(root, v[i]);
        }
        int last = root;
        for (int i = 0; i < s; ++i) {
            ending[lca(last, v[i])]++;
            starting[v[i]]++;
            last = v[i];
        }
    }
    solve(1);
    vector<int> v;
    for (int i = 1; i < n; ++i) {
        if (ans[i] >= k) v.push_back(i);
    }
    cout << v.size() << '\n';
    for (int x : v) {
        cout << x << ' ';
    }
}

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