oj.uz

Submission #677064

# Submission time Handle Problem Language Result Execution time Memory
677064 2023-01-02T08:18:27 Z Cyanmond Railway (BOI17_railway) C++17
100 / 100
 334 ms 65736 KB 
#include <bits/stdc++.h>

struct LCA {
    int n;
    int logn;
    std::vector<std::vector<int>> tree;
    std::vector<int> depth;
    std::vector<int> parent;
    std::vector<std::vector<int>> ancestors;

    LCA(const std::vector<std::vector<int>> &treee) {
        tree = treee;
        n = (int)tree.size();
        logn = 0;
        while ((1 << logn) < n) {
            ++logn;
        }
        parent.resize(n);
        depth.resize(n);
        dfs(0, -1, 0);
        make_table();
    }

    void make_table() {
        ancestors.resize(logn + 1);
        ancestors[0] = parent;
        for (int d = 0; d < logn; ++d) {
            ancestors[d + 1].resize(n);
            for (int i = 0; i < n; ++i) {
                const int t = ancestors[d][i];
                if (t == -1) {
                    ancestors[d + 1][i] = -1;
                } else {
                    ancestors[d + 1][i] = ancestors[d][t];
                }
            }
        }
    }

    void dfs(int v, int p, int d) {
        parent[v] = p;
        depth[v] = d;
        for (const int t : tree[v]) {
            if (t == p) {
                continue;
            }
            dfs(t, v, d + 1);
        }
    }

    int lca(int a, int b) {
        int da = depth[a], db = depth[b];
        if (da > db) {
            std::swap(a, b);
            std::swap(da, db);
        }
        for (int d = logn; d >= 0; --d) {
            if (db - (1 << d) >= da) {
                b = ancestors[d][b];
                db -= (1 << d);
            }
        }
        assert(da == db);
        if (a == b) {
            return a;
        }
        for (int d = logn; d >= 0; --d) {
            int na = ancestors[d][a];
            int nb = ancestors[d][b];
            if (na != nb) {
                a = na;
                b = nb;
            }
        }
        return parent[a];
    }
};

void merge(std::set<int> &a, std::set<int> &b) {
    if (a.size() < b.size()) {
        std::swap(a, b);
    }
    for (const int e : b) {
        a.insert(e);
    }
}

int main() {
    int N, M, K;
    std::cin >> N >> M >> K;

    std::vector<int> A(N - 1), B(N - 1);
    std::vector<std::vector<int>> tree(N);
    std::map<std::pair<int, int>, int> edge_id;
    for (int i = 0; i < N - 1; ++i) {
        std::cin >> A[i] >> B[i];
        tree[--A[i]].push_back(--B[i]);
        tree[B[i]].push_back(A[i]);
        edge_id[{A[i], B[i]}] = edge_id[{B[i], A[i]}] = i;
    }

    std::vector<int> S(M);
    std::vector<std::vector<int>> L(M);
    for (int i = 0; i < M; ++i) {
        std::cin >> S[i];
        L[i].resize(S[i]);
        for (auto &e : L[i]) {
            std::cin >> e;
            --e;
        }
    }

    LCA tree_d(tree);
    std::vector<std::vector<int>> add_list(N), erase_list(N);
    for (int i = 0; i < M; ++i) {
        for (const int e : L[i]) {
            add_list[e].push_back(i);
        }

        int lca = L[i][0];
        for (int j = 1; j < S[i]; ++j) {
            lca = tree_d.lca(lca, L[i][j]);
        }
        erase_list[lca].push_back(i);
    }

    std::vector<int> answer;
    auto dfs = [&](auto &&self, const int v, const int p) -> std::set<int> {
        std::set<int> ls;
        for (const int t : tree[v]) {
            if (p == t) {
                continue;
            }
            auto res = self(self, t, v);
            if ((int)res.size() >= K) {
                answer.push_back(edge_id[{t, v}]);
            }
            merge(ls, res);
        }

        for (const int e : add_list[v]) {
            ls.insert(e);
        }

        for (const int e : erase_list[v]) {
            ls.erase(e);
        }

        return ls;
    };
    dfs(dfs, 0, -1);

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 14 ms 4020 KB Output is correct
3 Correct 14 ms 3968 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 15 ms 5060 KB Output is correct
7 Correct 14 ms 4148 KB Output is correct
8 Correct 12 ms 4216 KB Output is correct
9 Correct 13 ms 4220 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 300 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 14 ms 4020 KB Output is correct
3 Correct 14 ms 3968 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 15 ms 5060 KB Output is correct
7 Correct 14 ms 4148 KB Output is correct
8 Correct 12 ms 4216 KB Output is correct
9 Correct 13 ms 4220 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 300 KB Output is correct
15 Correct 46 ms 5428 KB Output is correct
16 Correct 47 ms 5344 KB Output is correct
17 Correct 50 ms 5504 KB Output is correct
18 Correct 15 ms 5196 KB Output is correct
19 Correct 15 ms 4280 KB Output is correct
20 Correct 51 ms 5792 KB Output is correct
21 Correct 49 ms 5892 KB Output is correct
22 Correct 1 ms 300 KB Output is correct
23 Correct 14 ms 3984 KB Output is correct
24 Correct 14 ms 4036 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 1 ms 304 KB Output is correct
27 Correct 14 ms 5048 KB Output is correct
28 Correct 14 ms 4256 KB Output is correct
29 Correct 13 ms 4180 KB Output is correct
30 Correct 13 ms 4180 KB Output is correct
31 Correct 1 ms 212 KB Output is correct
32 Correct 0 ms 212 KB Output is correct
33 Correct 1 ms 212 KB Output is correct
34 Correct 1 ms 212 KB Output is correct
35 Correct 1 ms 212 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 65732 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 230 ms 65352 KB Output is correct
4 Correct 222 ms 64976 KB Output is correct
5 Correct 201 ms 61464 KB Output is correct
6 Correct 202 ms 61576 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 54492 KB Output is correct
2 Correct 263 ms 46080 KB Output is correct
3 Correct 278 ms 47172 KB Output is correct
4 Correct 277 ms 47464 KB Output is correct
5 Correct 282 ms 46900 KB Output is correct
6 Correct 227 ms 54584 KB Output is correct
7 Correct 225 ms 54476 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 54492 KB Output is correct
2 Correct 263 ms 46080 KB Output is correct
3 Correct 278 ms 47172 KB Output is correct
4 Correct 277 ms 47464 KB Output is correct
5 Correct 282 ms 46900 KB Output is correct
6 Correct 227 ms 54584 KB Output is correct
7 Correct 225 ms 54476 KB Output is correct
8 Correct 223 ms 52948 KB Output is correct
9 Correct 219 ms 53104 KB Output is correct
10 Correct 192 ms 60992 KB Output is correct
11 Correct 191 ms 60896 KB Output is correct
12 Correct 173 ms 41648 KB Output is correct
13 Correct 179 ms 41672 KB Output is correct
14 Correct 248 ms 41148 KB Output is correct
15 Correct 249 ms 41092 KB Output is correct
16 Correct 280 ms 47552 KB Output is correct
17 Correct 286 ms 47408 KB Output is correct
18 Correct 290 ms 47508 KB Output is correct
19 Correct 263 ms 45948 KB Output is correct
20 Correct 221 ms 54840 KB Output is correct
21 Correct 240 ms 54948 KB Output is correct
22 Correct 227 ms 54852 KB Output is correct

Subtask #6
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 14 ms 4020 KB Output is correct
3 Correct 14 ms 3968 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 15 ms 5060 KB Output is correct
7 Correct 14 ms 4148 KB Output is correct
8 Correct 12 ms 4216 KB Output is correct
9 Correct 13 ms 4220 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 300 KB Output is correct
15 Correct 46 ms 5428 KB Output is correct
16 Correct 47 ms 5344 KB Output is correct
17 Correct 50 ms 5504 KB Output is correct
18 Correct 15 ms 5196 KB Output is correct
19 Correct 15 ms 4280 KB Output is correct
20 Correct 51 ms 5792 KB Output is correct
21 Correct 49 ms 5892 KB Output is correct
22 Correct 1 ms 300 KB Output is correct
23 Correct 14 ms 3984 KB Output is correct
24 Correct 14 ms 4036 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 1 ms 304 KB Output is correct
27 Correct 14 ms 5048 KB Output is correct
28 Correct 14 ms 4256 KB Output is correct
29 Correct 13 ms 4180 KB Output is correct
30 Correct 13 ms 4180 KB Output is correct
31 Correct 1 ms 212 KB Output is correct
32 Correct 0 ms 212 KB Output is correct
33 Correct 1 ms 212 KB Output is correct
34 Correct 1 ms 212 KB Output is correct
35 Correct 1 ms 212 KB Output is correct
36 Correct 238 ms 65732 KB Output is correct
37 Correct 0 ms 212 KB Output is correct
38 Correct 230 ms 65352 KB Output is correct
39 Correct 222 ms 64976 KB Output is correct
40 Correct 201 ms 61464 KB Output is correct
41 Correct 202 ms 61576 KB Output is correct
42 Correct 228 ms 54492 KB Output is correct
43 Correct 263 ms 46080 KB Output is correct
44 Correct 278 ms 47172 KB Output is correct
45 Correct 277 ms 47464 KB Output is correct
46 Correct 282 ms 46900 KB Output is correct
47 Correct 227 ms 54584 KB Output is correct
48 Correct 225 ms 54476 KB Output is correct
49 Correct 223 ms 52948 KB Output is correct
50 Correct 219 ms 53104 KB Output is correct
51 Correct 192 ms 60992 KB Output is correct
52 Correct 191 ms 60896 KB Output is correct
53 Correct 173 ms 41648 KB Output is correct
54 Correct 179 ms 41672 KB Output is correct
55 Correct 248 ms 41148 KB Output is correct
56 Correct 249 ms 41092 KB Output is correct
57 Correct 280 ms 47552 KB Output is correct
58 Correct 286 ms 47408 KB Output is correct
59 Correct 290 ms 47508 KB Output is correct
60 Correct 263 ms 45948 KB Output is correct
61 Correct 221 ms 54840 KB Output is correct
62 Correct 240 ms 54948 KB Output is correct
63 Correct 227 ms 54852 KB Output is correct
64 Correct 239 ms 54808 KB Output is correct
65 Correct 334 ms 46672 KB Output is correct
66 Correct 266 ms 42416 KB Output is correct
67 Correct 282 ms 42172 KB Output is correct
68 Correct 180 ms 41000 KB Output is correct
69 Correct 181 ms 40900 KB Output is correct
70 Correct 243 ms 55624 KB Output is correct
71 Correct 214 ms 52884 KB Output is correct
72 Correct 1 ms 296 KB Output is correct
73 Correct 13 ms 4052 KB Output is correct
74 Correct 13 ms 4032 KB Output is correct
75 Correct 1 ms 212 KB Output is correct
76 Correct 0 ms 300 KB Output is correct
77 Correct 14 ms 5076 KB Output is correct
78 Correct 15 ms 4180 KB Output is correct
79 Correct 11 ms 4180 KB Output is correct
80 Correct 13 ms 4136 KB Output is correct
81 Correct 1 ms 296 KB Output is correct
82 Correct 1 ms 212 KB Output is correct
83 Correct 1 ms 212 KB Output is correct
84 Correct 1 ms 212 KB Output is correct
85 Correct 0 ms 212 KB Output is correct
86 Correct 45 ms 5432 KB Output is correct
87 Correct 48 ms 5452 KB Output is correct
88 Correct 46 ms 5424 KB Output is correct
89 Correct 15 ms 5076 KB Output is correct
90 Correct 14 ms 4308 KB Output is correct
91 Correct 48 ms 5788 KB Output is correct
92 Correct 50 ms 5672 KB Output is correct
93 Correct 1 ms 212 KB Output is correct
94 Correct 241 ms 65736 KB Output is correct
95 Correct 229 ms 65352 KB Output is correct
96 Correct 226 ms 64852 KB Output is correct
97 Correct 198 ms 61580 KB Output is correct
98 Correct 201 ms 61544 KB Output is correct
99 Correct 286 ms 47704 KB Output is correct
100 Correct 273 ms 47724 KB Output is correct
101 Correct 277 ms 47476 KB Output is correct
102 Correct 260 ms 46312 KB Output is correct
103 Correct 214 ms 54552 KB Output is correct
104 Correct 223 ms 54916 KB Output is correct
105 Correct 230 ms 54496 KB Output is correct
106 Correct 224 ms 53160 KB Output is correct
107 Correct 210 ms 52952 KB Output is correct
108 Correct 198 ms 60912 KB Output is correct
109 Correct 190 ms 60936 KB Output is correct
110 Correct 172 ms 41648 KB Output is correct
111 Correct 172 ms 41676 KB Output is correct
112 Correct 247 ms 40912 KB Output is correct
113 Correct 242 ms 41260 KB Output is correct