oj.uz

Submission #934495

# Submission time Handle Problem Language Result Execution time Memory
934495 2024-02-27T13:05:25 Z MisterReaper Railway (BOI17_railway) C++17
36 / 100
 88 ms 27336 KB 
#include <bits/stdc++.h>
using i64 = long long;

void solve() {
    int n, m, k;
    std::cin >> n >> m >> k;

    std::vector adj(n, std::vector<std::pair<int, int>> ());
    for(int i = 0; i < n - 1; i++) {
        int u, v;
        std::cin >> u >> v;
        adj[--u].emplace_back(--v, i);
        adj[v].emplace_back(u, i);
    }

    const int L = std::__lg(n) + 2;

    int timer = 0;
    std::vector par(n, std::vector<int> (L));
    std::vector<int> tin(n), tout(n), dep(n), val(n), pedge(n);
    auto dfs = [&](auto&& self, int node, int p) -> void {
        tin[node] = timer++;
        par[node][0] = p;
        for(auto [child, idx] : adj[node]) {
            if(child == p) {
                continue;
            }
            pedge[child] = idx;
            dep[child] = dep[node] + 1;
            self(self, child, node);
        }
        tout[node] = timer++;
    };

    dfs(dfs, 0, 0);

    for(int lg = 1; lg < L; lg++) {
        for(int i = 0; i < n; i++) {
            par[i][lg] = par[par[i][lg - 1]][lg - 1];
        }
    }

    std::vector s(m, std::vector<int> ());
    for(int i = 0; i < m; i++) {
        int x;
        std::cin >> x;
        s[i].resize(x);
        for(int j = 0; j < x; j++) {
            std::cin >> s[i][j];
            s[i][j]--;
        }
        std::sort(s[i].begin(), s[i].end(), [&](int lhs, int rhs) -> bool {
            return tin[lhs] < tin[rhs];
        });
        s[i].emplace_back(s[i].front());
    }

    auto get = [&](int node, int l) -> int {
        for(int lg = L - 1; lg >= 0; lg--) {
            if(l >> lg & 1) {
                node = par[node][lg];
            }
        }

        return node;
    };

    auto lca = [&](int a, int b) -> int {
        if(dep[b] > dep[a]) {
            std::swap(a, b);
        }

        a = get(a, dep[a] - dep[b]);
        for(int lg = L - 1; lg >= 0; lg--) {
            if(par[a][lg] != par[b][lg]) {
                a = par[a][lg];
                b = par[b][lg];
            }
        }

        return (a == b ? a : par[a][0]);
    };

    for(int i = 0; i < m; i++) {
        int x = int(s[i].size());
        for(int j = 0; j + 1 < x; j++) {
            int u = s[i][j], v = s[i][j + 1];
            int g = lca(u, v);
            //std::cerr << u << " " << v << " :: " << g << "\n";
            val[u]++;
            val[v]++;
            val[g] -= 2;
        }
    }

    /*
    for(int i = 0; i < n; i++) {
        std::cerr << val[i] << " \n"[i == n - 1];
    }
    */

    auto dfs2 = [&](auto&& self, int node, int p) -> void {
        for(auto [child, idx] : adj[node]) {
            if(child == p) {
                continue;
            }
            self(self, child, node);
            val[node] += val[child];
        }
    };

    dfs2(dfs2, 0, 0);

    std::vector<int> ans;
    for(int i = 0; i < n; i++) {
        //std::cerr << val[i] << " \n"[i == n - 1];
        if(val[i] >= 2 * k) {
            ans.emplace_back(pedge[i]);
        }
    }

    std::cout << int(ans.size()) << "\n";
    for(int i = 0; i < int(ans.size()); i++) {
        std::cout << ans[i] + 1 << " ";
    }
    
    return;
}

signed main() {
    #ifdef LOCAL
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    #endif

    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL); std::cout.tie(NULL);

    int t = 1; //std::cin >> t;
    for(int i = 1; i <= t; i++) {
        solve();
    }

    return 0;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 27336 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 79 ms 27192 KB Output is correct
4 Correct 75 ms 26448 KB Output is correct
5 Correct 88 ms 25676 KB Output is correct
6 Correct 79 ms 26188 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 25000 KB Output is correct
2 Correct 72 ms 23380 KB Output is correct
3 Correct 72 ms 23084 KB Output is correct
4 Correct 79 ms 23376 KB Output is correct
5 Correct 75 ms 23196 KB Output is correct
6 Correct 67 ms 25276 KB Output is correct
7 Correct 66 ms 24916 KB Output is correct

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 25000 KB Output is correct
2 Correct 72 ms 23380 KB Output is correct
3 Correct 72 ms 23084 KB Output is correct
4 Correct 79 ms 23376 KB Output is correct
5 Correct 75 ms 23196 KB Output is correct
6 Correct 67 ms 25276 KB Output is correct
7 Correct 66 ms 24916 KB Output is correct
8 Correct 72 ms 24144 KB Output is correct
9 Correct 77 ms 24144 KB Output is correct
10 Correct 69 ms 25548 KB Output is correct
11 Correct 67 ms 25484 KB Output is correct
12 Incorrect 58 ms 20820 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -