oj.uz

Submission #1023162

# Submission time Handle Problem Language Result Execution time Memory
1023162 2024-07-14T11:25:24 Z avighna Rigged Roads (NOI19_riggedroads) C++17
100 / 100
 378 ms 88756 KB 
#include <vector>
#include <iostream>
#include <numeric>
#include <algorithm>
#include <functional>

class UFDS {
public:
    std::vector<int> par;
    UFDS(int n) : par(n + 1) {
        std::iota(par.begin(), par.end(), 0);
    }

    int root(int x) {
        if (x == par[x]) {
            return x;
        }
        return par[x] = root(par[x]);
    }

    void merge(int x, int y) {
        x = root(x);
        y = root(y);
        if (x == y) {
            return;
        }
        par[y] = x;
    }
};

const int N = 3e5 + 1;
std::vector<int> adj[N];
std::vector<std::pair<int, int>> tree[N];
bool r[N], assigned[N];
int lift[N][20];
int depth[N], edge_to_num[N];

int main() {
    int n, e;
    std::cin >> n >> e;
    std::vector<std::pair<int, int>> edges;
    for (int i = 0, u, v; i < e; ++i) {
        std::cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        edges.push_back({u, v});
    }
    for (int i = 0, v; i < n - 1; ++i) {
        std::cin >> v;
        --v;
        r[v] = true;
        tree[edges[v].first].push_back({edges[v].second, v});
        tree[edges[v].second].push_back({edges[v].first, v});
    }

    std::function<void(int, int)> dfs;
    dfs = [&](int node, int par) {
        for (auto &[i, v] : tree[node]) {
            if (i == par) {
                continue;
            }
            depth[i] = depth[node] + 1;
            lift[i][0] = node;
            edge_to_num[i] = v;
            dfs(i, node);
        }
    };
    dfs(1, 0);
    for (int bt = 1; bt < 20; ++bt) {
        for (int i = 1; i <= n; ++i) {
            lift[i][bt] = lift[lift[i][bt - 1]][bt - 1];
        }
    }
    auto lca = [&](int a, int b) {
        if (depth[a] < depth[b]) {
            std::swap(a, b);
        }
        int k = depth[a] - depth[b];
        for (int bt = 0; bt < 20; ++bt) {
            if (k & (1 << bt)) {
                a = lift[a][bt];
            }
        }
        if (a == b) {
            return a;
        }
        for (int bt = 19; bt >= 0; --bt) {
            if (lift[a][bt] != lift[b][bt]) {
                a = lift[a][bt];
                b = lift[b][bt];
            }
        }
        return lift[a][0];
    };

    int cur = 1;
    std::vector<int> p(e);
    UFDS dsu(n);
    for (int i = 0; i < e; ++i) {
        if (assigned[i]) {
            continue;
        }
        assigned[i] = true;
        auto [u, v] = edges[i];
        int anc = lca(u, v);
        if (r[i]) {
            p[i] = cur++;
            if (depth[u] < depth[v]) {
                std::swap(u, v);
            }
            dsu.merge(v, u);
            continue;
        }
        std::vector<int> target_edges;
        for (auto &x : std::array<int, 2>({u, v})) {
            while (x != anc && depth[dsu.root(x)] >= depth[anc]) {
                x = dsu.root(x);
                if (x == anc) {
                    break;
                }
                target_edges.push_back(edge_to_num[x]);
                dsu.merge(lift[x][0], x);
                x = lift[x][0];
            }
        }
        std::sort(target_edges.begin(), target_edges.end());
        for (auto &e : target_edges) {
            if (assigned[e]) {
                continue;
            }
            assigned[e] = true;
            p[e] = cur++;
        }
        p[i] = cur++;
    }
    for (auto &i : p) {
        std::cout << i << " ";
    }
    std::cout << "\n";
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14680 KB Output is correct
2 Correct 6 ms 14424 KB Output is correct
3 Correct 6 ms 14428 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14680 KB Output is correct
2 Correct 6 ms 14424 KB Output is correct
3 Correct 6 ms 14428 KB Output is correct
4 Correct 7 ms 14684 KB Output is correct
5 Correct 7 ms 14684 KB Output is correct
6 Correct 6 ms 14684 KB Output is correct
7 Correct 6 ms 14424 KB Output is correct
8 Correct 8 ms 14684 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 33932 KB Output is correct
2 Correct 153 ms 41920 KB Output is correct
3 Correct 158 ms 28856 KB Output is correct
4 Correct 238 ms 69304 KB Output is correct
5 Correct 257 ms 71564 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 46016 KB Output is correct
2 Correct 98 ms 28136 KB Output is correct
3 Correct 50 ms 21448 KB Output is correct
4 Correct 106 ms 37692 KB Output is correct
5 Correct 41 ms 23756 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 73996 KB Output is correct
2 Correct 295 ms 83604 KB Output is correct
3 Correct 73 ms 34248 KB Output is correct
4 Correct 116 ms 43764 KB Output is correct
5 Correct 328 ms 88756 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 56768 KB Output is correct
2 Correct 122 ms 43576 KB Output is correct
3 Correct 347 ms 78516 KB Output is correct
4 Correct 333 ms 73916 KB Output is correct
5 Correct 31 ms 19792 KB Output is correct

Subtask #7
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14680 KB Output is correct
2 Correct 6 ms 14424 KB Output is correct
3 Correct 6 ms 14428 KB Output is correct
4 Correct 7 ms 14684 KB Output is correct
5 Correct 7 ms 14684 KB Output is correct
6 Correct 6 ms 14684 KB Output is correct
7 Correct 6 ms 14424 KB Output is correct
8 Correct 8 ms 14684 KB Output is correct
9 Correct 83 ms 33932 KB Output is correct
10 Correct 153 ms 41920 KB Output is correct
11 Correct 158 ms 28856 KB Output is correct
12 Correct 238 ms 69304 KB Output is correct
13 Correct 257 ms 71564 KB Output is correct
14 Correct 140 ms 46016 KB Output is correct
15 Correct 98 ms 28136 KB Output is correct
16 Correct 50 ms 21448 KB Output is correct
17 Correct 106 ms 37692 KB Output is correct
18 Correct 41 ms 23756 KB Output is correct
19 Correct 270 ms 73996 KB Output is correct
20 Correct 295 ms 83604 KB Output is correct
21 Correct 73 ms 34248 KB Output is correct
22 Correct 116 ms 43764 KB Output is correct
23 Correct 328 ms 88756 KB Output is correct
24 Correct 195 ms 56768 KB Output is correct
25 Correct 122 ms 43576 KB Output is correct
26 Correct 347 ms 78516 KB Output is correct
27 Correct 333 ms 73916 KB Output is correct
28 Correct 31 ms 19792 KB Output is correct
29 Correct 375 ms 72068 KB Output is correct
30 Correct 378 ms 74148 KB Output is correct
31 Correct 377 ms 71200 KB Output is correct
32 Correct 165 ms 28944 KB Output is correct
33 Correct 360 ms 72120 KB Output is correct