Submission #1126795

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126795		Pannda	Rigged Roads (NOI19_riggedroads)	C++20	10 / 100	205 ms	145800 KiB

riggedroads

#include <bits/stdc++.h>
using namespace std;

struct Tree {
    vector<int> depth, parent, siz, head, begin, end;
    Tree(int n, const vector<vector<int>> &adj) : depth(n), parent(n), siz(n), head(n), begin(n), end(n) {
        auto scout = [&](auto self, int u, int p) -> void {
            depth[u] = p == -1 ? 0 : depth[p] + 1;
            parent[u] = p;
            siz[u] = 1;
            for (int v : adj[u]) {
                if (v == p) continue;
                self(self, v, u);
                siz[u] += siz[v];
            }
        };
        scout(scout, 0, -1);
        int tim = 0;
        auto decompose = [&](auto self, int u, int h) -> void {
            head[u] = h;
            begin[u] = tim++;
            int heavy = -1;
            for (int v : adj[u]) {
                if (v == parent[u]) continue;
                if (heavy == -1 || siz[v] > siz[heavy]) heavy = v;
            }
            if (heavy != -1) {
                self(self, heavy, h);
            }
            for (int v : adj[u]) {
                if (v == parent[u] || v == heavy) continue;
                self(self, v, v);
            }
            end[u] = tim;
        };
        decompose(decompose, 0, 0);
    }
    int getDepth(int u) {
        return depth[u];
    }
    int getNode(int u) {
        return begin[u];
    }
    vector<array<int, 2>> getPath(int u, int v, bool includeLCA = true) {
        vector<array<int, 2>> res;
        while (head[u] != head[v]) {
            if (depth[head[u]] > depth[head[v]]) swap(u, v);
            res.push_back({ begin[head[v]], begin[v] + 1 });
            v = parent[head[v]];
        }
        if (depth[u] > depth[v]) swap(u, v);
        int l = begin[u] + (!includeLCA);
        int r = begin[v] + 1;
        if (l < r) res.push_back({l, r});
        return res;
    }
};

struct Paint {
    int n;
    vector<int> color;
    Paint(int n) : n(n), color(4 * n, -1) {}
    void paint(int ql, int qr, int c) {
        auto dfs = [&](auto self, int idx, int l, int r) -> void {
            if (r <= ql || qr <= l) return;
            if (ql <= l && r <= qr) {
                color[idx] = c;
                return;
            }
            int m = (l + r) >> 1;
            self(self, 2 * idx + 1, l, m);
            self(self, 2 * idx + 2, m, r);
        };
        dfs(dfs, 0, 0, n);
    }
    int getColor(int i) {
        int idx = 0, l = 0, r = n;
        while (l + 1 < r) {
            if (color[idx] != -1) return color[idx];
            int m = (l + r) >> 1;
            if (i < m) {
                idx = 2 * idx + 1;
                r = m;
            } else {
                idx = 2 * idx + 2;
                l = m;
            }
        }
        return color[idx];
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<array<int, 2>> edges(m);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        edges[i] = {u, v};
    }
    vector<bool> is_tree_edge(m, false);
    for (int i = 0; i < n - 1; i++) {
        int p;
        cin >> p;
        p--;
        is_tree_edge[p] = true;
    }

    vector<vector<int>> adj(n);
    for (int i = 0; i < m; i++) {
        if (!is_tree_edge[i]) continue;
        auto [u, v] = edges[i];
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    Tree tree(n, adj);
    Paint paint(n);

    for (int i = m - 1; i >= 0; i--) {
        if (is_tree_edge[i]) continue;
        auto [u, v] = edges[i];
        for (auto [l, r] : tree.getPath(u, v, false)) {
            paint.paint(l, r, i);
        }
    }

    vector<vector<int>> inbox(m);
    for (int i = 0; i < m; i++) {
        if (!is_tree_edge[i]) continue;
        auto [u, v] = edges[i];
        if (tree.getDepth(u) > tree.getDepth(v)) swap(u, v);
        int color = paint.getColor(tree.getNode(v));
        if (color != -1) inbox[color].push_back(i);
    }

    int val = 1;
    vector<int> w(m);
    for (int i = 0; i < m; i++) {
        if (!is_tree_edge[i]) {
            sort(inbox[i].begin(), inbox[i].end());
            for (int j : inbox[i]) {
                w[j] = val++;
            }
            w[i] = val++;
        } else {
            auto [u, v] = edges[i];
            if (tree.getDepth(u) > tree.getDepth(v)) swap(u, v);
            int color = paint.getColor(tree.getNode(v));
            if (color == -1) {
                w[i] = val++;
            }
        }
    }

    for (int i = 0; i < m; i++) {
        cout << w[i] << " \n"[i == m - 1];
    }
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 19
• Subtask 3: 0 / 9
• Subtask 4: 0 / 10
• Subtask 5: 10 / 10
• Subtask 6: 0 / 12
• Subtask 7: 0 / 32