oj.uz

Submission #720184

# Submission time Handle Problem Language Result Execution time Memory
720184 2023-04-07T15:08:46 Z Cyanmond Rigged Roads (NOI19_riggedroads) C++17
58 / 100
 2000 ms 78580 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 212 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 2 ms 452 KB Output is correct
5 Correct 3 ms 452 KB Output is correct
6 Correct 7 ms 456 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 468 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 24260 KB Output is correct
2 Correct 258 ms 36888 KB Output is correct
3 Correct 454 ms 28376 KB Output is correct
4 Correct 304 ms 65980 KB Output is correct
5 Correct 333 ms 69436 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2053 ms 33656 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 287 ms 63444 KB Output is correct
2 Correct 313 ms 70556 KB Output is correct
3 Correct 80 ms 20140 KB Output is correct
4 Correct 112 ms 30228 KB Output is correct
5 Correct 367 ms 78580 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 287 ms 42296 KB Output is correct
2 Correct 146 ms 29140 KB Output is correct
3 Correct 475 ms 68620 KB Output is correct
4 Correct 486 ms 63896 KB Output is correct
5 Correct 26 ms 6504 KB Output is correct

Subtask #7
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 2 ms 452 KB Output is correct
5 Correct 3 ms 452 KB Output is correct
6 Correct 7 ms 456 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 107 ms 24260 KB Output is correct
10 Correct 258 ms 36888 KB Output is correct
11 Correct 454 ms 28376 KB Output is correct
12 Correct 304 ms 65980 KB Output is correct
13 Correct 333 ms 69436 KB Output is correct
14 Execution timed out 2053 ms 33656 KB Time limit exceeded
15 Halted 0 ms 0 KB -