Submission #720186

#	Time	Username	Problem	Language	Result	Execution time	Memory
720186		Cyanmond	Rigged Roads (NOI19_riggedroads)	C++17	100 / 100	859 ms	88148 KiB

riggedroads

#include <bits/stdc++.h>

struct HLD {
    int n;
    std::vector<std::vector<int>> tree;
    std::vector<int> parent, subtreeSize, head, in, depth;

    HLD(const std::vector<std::vector<int>> &tree_) : tree(tree_) {
        n = (int)tree.size();
        parent.assign(n, -1);
        subtreeSize.assign(n, -1);
        head.assign(n, -1);
        in.assign(n, -1);
        depth.assign(n, -1);
        dfs1(0, -1, 0);
        head[0] = 0;
        dfs2(0, -1, 0);
    }

    int dfs1(int v, int p, int d) {
        subtreeSize[v] = 1;
        parent[v] = p;
        depth[v] = d;
        for (const int t : tree[v]) {
            if (t != p) {
                subtreeSize[v] += dfs1(t, v, d + 1);
            }
        }
        for (auto &t : tree[v]) {
            if (t == p) std::swap(t, tree[v].back());
        }
        for (auto &t : tree[v]) {
            if (t != p and subtreeSize[t] >= subtreeSize[tree[v][0]]) std::swap(t, tree[v][0]);
        }
        return subtreeSize[v];
    }

    int dfs2(int v, int p, int k) {
        in[v] = k++;
        for (const int t : tree[v]) {
            if (t == p) continue;
            if (t == tree[v][0]) {
                head[t] = head[v];
            } else {
                head[t] = t;
            }
            k = dfs2(t, v, k);
        }
        return k;
    }

    template <class F>
    void queryEdge(int u, int v, F &&f) {
        while (true) {
            if (in[u] > in[v]) std::swap(u, v);
            if (head[u] == head[v]) break;
            f(in[head[v]], in[v] + 1);
            v = parent[head[v]];
        }
        f(in[u] + 1, in[v] + 1);
    }
};

void solve() {
    int N, M;
    std::cin >> N >> M;
    std::vector<int> A(M), B(M);
    std::map<std::pair<int, int>, int> edgeId;
    for (int i = 0; i < M; ++i) {
        std::cin >> A[i] >> B[i];
        --A[i], --B[i];
        edgeId[std::minmax(A[i], B[i])] = i;
    }
    std::vector<int> R(N - 1);
    std::vector<bool> isSp(M);
    for (auto &e : R) {
        std::cin >> e;
        --e;
        isSp[e] = true;
    }
    std::vector<int> parent(N);
    std::vector<std::vector<int>> Tree(N);
    for (const auto e : R) {
        Tree[A[e]].push_back(B[e]);
        Tree[B[e]].push_back(A[e]);
    }

    HLD hld(Tree);
    std::vector<int> answer(M, -1);
    std::set<int> s;
    std::vector<int> pEdgeId(N);
    for (int i = 1; i < N; ++i) {
        const int a = i, b = hld.parent[i];
        const auto j = edgeId[std::minmax(a, b)];
        pEdgeId[hld.in[a]] = j;
        s.insert(i);
    }

    auto findPaint = [&](int a, int b) {
        if (hld.depth[a] < hld.depth[b]) std::swap(a, b);
        std::vector<int> path;
        auto f = [&](int l, int r) {
            auto itr = s.lower_bound(l);
            while (itr != s.end() and *itr < r) {
                path.push_back(pEdgeId[*itr]);
                itr = s.erase(itr);
            }
        };
        hld.queryEdge(a, b, f);
        return path;
    };

    int nowValue = 0;
    for (int i = 0; i < M; ++i) {
        if (answer[i] != -1) continue;
        if (isSp[i]) {
            answer[i] = ++nowValue;
            continue;
        }
        auto path = findPaint(A[i], B[i]);
        std::sort(path.begin(), path.end());
        for (const auto e : path) {
            if (answer[e] == -1) {
                answer[e] = ++nowValue;
            }
        }
        answer[i] = ++nowValue;
    }
    for (const auto e : answer) std::cout << e << ' ';
    std::cout << std::endl;
}

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

• 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