제출 #720184

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
720184		Cyanmond	Rigged Roads (NOI19_riggedroads)	C++17	58 / 100	2053 ms	78580 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);
    }

    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];
    }
};

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);

    auto findPaint = [&](int a, int b) {
        if (hld.depth[a] < hld.depth[b]) std::swap(a, b);
        std::vector<int> path;
        while (hld.depth[a] != hld.depth[b]) {
            const int nxta = hld.parent[a];
            path.push_back(edgeId[std::minmax(nxta, a)]);
            a = nxta;
        }
        while (a != b) {
            const int nxta = hld.parent[a];
            path.push_back(edgeId[std::minmax(nxta, a)]);
            a = nxta;
            const int nxtb = hld.parent[b];
            path.push_back(edgeId[std::minmax(nxtb, b)]);
            b = nxtb;
        }
        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: 0 / 10
• Subtask 5: 10 / 10
• Subtask 6: 12 / 12
• Subtask 7: 0 / 32