Submission #1262571

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262571		A_M_Namdar	Railway (BOI17_railway)	C++20	100 / 100	76 ms	24900 KiB

railway

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

const int N = 1e5 + 10, LG = 20;
int n, m, k, par[N][LG], h[N], cnt[N], st[N];
vector<int> adj[N], tr, ans;
pair<int, int> edge[N];

void dfs(int u) {
    st[u] = tr.size();
    tr.push_back(u);
    for (int v: adj[u]) 
        if (v != par[u][0]) {
            h[v] = h[u] + 1, par[v][0] = u;
            dfs(v);
        }
}

void pre() {
    par[0][0] = n;
    dfs(0);
    for (int j = 1; j < LG; j++) 
        for (int i = 0; i < n; i++) 
            if (h[i] >= (1 << j)) 
                par[i][j] = par[par[i][j - 1]][j - 1];
}

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

void add_path(int u, int v) {
//    cout << u << ' ' << v << " : " << lca(u, v) << '\n';
    cnt[u]++;
    cnt[v]++;
    cnt[lca(u, v)] -= 2;
}

void dfs_relax(int u) {
    for (int v: adj[u]) 
        if (v != par[u][0]) {
            dfs_relax(v);
            cnt[u] += cnt[v];
        }
//    cout << u + 1 << ' ' << cnt[u] << '\n';
}

void input() {
    cin >> n >> m >> k;
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
        edge[i] = {u, v};
    }
}

void solve() {
    pre();
    for (int i = 0; i < m; i++) {
        int sz;
        cin >> sz;
        vector<int> vec(sz);
        for (int j = 0; j < sz; j++) {
            cin >> vec[j];
            vec[j]--;
        }
        sort(vec.begin(), vec.end(), [](int p1, int p2) {
                return st[p1] < st[p2];
        });
        for (int j = 1; j < sz; j++) 
            add_path(vec[j], vec[j - 1]);
        add_path(vec[0], vec[sz - 1]);
    }
    dfs_relax(0);
    for (int i = 0; i < n - 1; i++) {
        if (h[edge[i].first] > h[edge[i].second]) 
            swap(edge[i].first, edge[i].second);
        if (cnt[edge[i].second] >= 2 * k) 
            ans.push_back(i + 1);
    }
}

void output() {
    cout << ans.size() << '\n';
    for (int u: ans) 
        cout << u << ' ';
}

int main() {
    ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
    input();
    solve();
    output();
}

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