Submission #1103626

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103626		ortsac	Railway (BOI17_railway)	C++17	100 / 100	161 ms	35008 KiB

railway

#include <bits/stdc++.h>

using namespace std;

#define pii pair<int, int>
#define fr first
#define se second

const int MAXN = 1e5 + 10;
const int MAXLOG = 18;

vector<int> adj[MAXN];
map<pii, int> edgeId;

int h[MAXN], in[MAXN], out[MAXN], p[MAXN];
int t = 0;

void dfs(int node, int dad) {
    p[node] = dad;
    h[node] = (h[dad] + 1);
    in[node] = ++t;
    for (auto u : adj[node]) {
        if (u != dad) dfs(u, node);
    }
    out[node] = t;
}

int binl[MAXLOG][MAXN];

int lca(int a, int b) {
    if (h[a] > h[b]) swap(a, b);
    int k = (h[b] - h[a]);
    for (int i = 0; i < MAXLOG; i++) {
        if ((1 << i) & k) b = binl[i][b];
    }
    if (a == b) {
        return a;
    }
    for (int i = MAXLOG - 1; i >= 0; i--) {
        if (binl[i][a] != binl[i][b]) {
            a = binl[i][a];
            b = binl[i][b];
        }
    }
    return p[a];
}

bool upper(int a, int b) {
    // check if a is ancestor of b
    return ((in[a] <= in[b]) && (out[b] <= out[a]));
}

int pf[MAXN];
vector<int> ans;
int n, m, k;

void calc(int node, int dad) {
    for (auto u : adj[node]) {
        if (u == dad) continue;
        calc(u, node);
        pf[node] += pf[u];
    }
    if (pf[node] >= k) {
        int a = node, b = p[node];
        if (a > b) swap(a, b);
        ans.push_back(edgeId[{a, b}]);
    }
}

int32_t main() {
    cin >> n >> m >> k;
    for (int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        if (a > b) swap(a, b);
        adj[a].push_back(b);
        adj[b].push_back(a);
        edgeId[{a, b}] = i;
    }
    dfs(1, 0);
    for (int i = 1; i <= n; i++) binl[0][i] = p[i];
    for (int j = 1; j < MAXLOG; j++) {
        for (int i = 1; i <= n; i++) binl[j][i] = binl[j - 1][binl[j - 1][i]];
    }
    while (m--) {
        int t;
        cin >> t;
        vector<pii> v;
        for (int i = 0; i < t; i++) {
            int x;
            cin >> x;
            v.push_back({in[x], x});
        }
        sort(v.begin(), v.end());
        for (int i = 0; i < (t - 1); i++) {
            int x = lca(v[i].se, v[i + 1].se);
            v.push_back({in[x], x});
        }
        sort(v.begin(), v.end());
        v.erase(unique(v.begin(), v.end()), v.end());
        stack<int> s;
        for (auto u : v) {
            if (!s.empty()) {
                while (!upper(s.top(), u.se)) {
                    int b = s.top();
                    s.pop();
                    int a = s.top();
                    pf[b]++;
                    pf[a]--;
                }
            }
            s.push(u.se);
        }
        while (((int) s.size()) >= 2) {
            int b = s.top();
            s.pop();
            int a = s.top();
            pf[b]++;
            pf[a]--;
        }
    }
    calc(1, 0);
    sort(ans.begin(), ans.end());
    cout << ans.size() << "\n";
    for (auto u : ans) cout << u << " ";
    cout << "\n";
}

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