Submission #1023162

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023162		avighna	Rigged Roads (NOI19_riggedroads)	C++17	100 / 100	378 ms	88756 KiB

riggedroads

#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 / 8
• Subtask 2: 19 / 19
• Subtask 3: 9 / 9
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 12 / 12
• Subtask 7: 32 / 32