제출 #1324125

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1324125		sh_qaxxorov_571	Railway (BOI17_railway)	C++20	100 / 100	68 ms	22528 KiB

railway

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

using namespace std;

/**
 * Bergen Light Railway - Tree Difference Array + LCA
 */

const int MAXN = 100005;
const int LOGN = 18;

vector<pair<int, int>> adj[MAXN];
int up[MAXN][LOGN], tin[MAXN], tout[MAXN], timer;
int depth[MAXN], edge_id[MAXN];
long long diff[MAXN];
int n, m, k;

void dfs_lca(int u, int p, int d, int id) {
    tin[u] = ++timer;
    up[u][0] = p;
    depth[u] = d;
    edge_id[u] = id;
    for (int i = 1; i < LOGN; i++)
        up[u][i] = up[up[u][i - 1]][i - 1];
    for (auto& edge : adj[u]) {
        if (edge.first != p) dfs_lca(edge.first, u, d + 1, edge.second);
    }
    tout[u] = timer;
}

bool is_ancestor(int u, int v) {
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}

int get_lca(int u, int v) {
    if (is_ancestor(u, v)) return u;
    if (is_ancestor(v, u)) return v;
    for (int i = LOGN - 1; i >= 0; i--) {
        if (!is_ancestor(up[u][i], v)) u = up[u][i];
    }
    return up[u][0];
}

void dfs_result(int u, int p) {
    for (auto& edge : adj[u]) {
        if (edge.first != p) {
            dfs_result(edge.first, u);
            diff[u] += diff[edge.first];
        }
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m >> k;
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
    }

    dfs_lca(1, 1, 0, 0);

    for (int i = 0; i < m; i++) {
        int s; cin >> s;
        vector<int> nodes(s);
        for (int j = 0; j < s; j++) cin >> nodes[j];
        
        // Tugunlarni DFS tartibida saralash
        sort(nodes.begin(), nodes.end(), [](int a, int b) {
            return tin[a] < tin[b];
        });

        // Steiner Tree qirralarini belgilash
        for (int j = 0; j < s; j++) {
            int u = nodes[j];
            int v = nodes[(j + 1) % s];
            int lca = get_lca(u, v);
            diff[u]++;
            diff[v]++;
            diff[lca] -= 2;
        }
    }

    dfs_result(1, 1);

    vector<int> result;
    for (int i = 2; i <= n; i++) {
        // Har bir yo'l 2 marta sanalgan bo'ladi (aylana bo'ylab o'tish hisobiga)
        if (diff[i] / 2 >= k) {
            result.push_back(edge_id[i]);
        }
    }

    sort(result.begin(), result.end());
    cout << result.size() << "\n";
    for (int i = 0; i < result.size(); i++) {
        cout << result[i] << (i == result.size() - 1 ? "" : " ");
    }
    cout << endl;

    return 0;
}

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