oj.uz

Submission #720186

# Submission time Handle Problem Language Result Execution time Memory
720186 2023-04-07T15:21:34 Z Cyanmond Rigged Roads (NOI19_riggedroads) C++17
100 / 100
 859 ms 88148 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);
        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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 316 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 316 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 464 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 28116 KB Output is correct
2 Correct 307 ms 41028 KB Output is correct
3 Correct 287 ms 26712 KB Output is correct
4 Correct 407 ms 75952 KB Output is correct
5 Correct 515 ms 79732 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 36616 KB Output is correct
2 Correct 122 ms 20156 KB Output is correct
3 Correct 56 ms 10500 KB Output is correct
4 Correct 132 ms 28780 KB Output is correct
5 Correct 57 ms 11284 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 373 ms 71268 KB Output is correct
2 Correct 397 ms 78748 KB Output is correct
3 Correct 92 ms 22724 KB Output is correct
4 Correct 146 ms 34044 KB Output is correct
5 Correct 463 ms 88148 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 355 ms 47308 KB Output is correct
2 Correct 244 ms 32804 KB Output is correct
3 Correct 705 ms 77304 KB Output is correct
4 Correct 668 ms 71876 KB Output is correct
5 Correct 38 ms 7628 KB Output is correct

Subtask #7
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 464 KB Output is correct
9 Correct 138 ms 28116 KB Output is correct
10 Correct 307 ms 41028 KB Output is correct
11 Correct 287 ms 26712 KB Output is correct
12 Correct 407 ms 75952 KB Output is correct
13 Correct 515 ms 79732 KB Output is correct
14 Correct 204 ms 36616 KB Output is correct
15 Correct 122 ms 20156 KB Output is correct
16 Correct 56 ms 10500 KB Output is correct
17 Correct 132 ms 28780 KB Output is correct
18 Correct 57 ms 11284 KB Output is correct
19 Correct 373 ms 71268 KB Output is correct
20 Correct 397 ms 78748 KB Output is correct
21 Correct 92 ms 22724 KB Output is correct
22 Correct 146 ms 34044 KB Output is correct
23 Correct 463 ms 88148 KB Output is correct
24 Correct 355 ms 47308 KB Output is correct
25 Correct 244 ms 32804 KB Output is correct
26 Correct 705 ms 77304 KB Output is correct
27 Correct 668 ms 71876 KB Output is correct
28 Correct 38 ms 7628 KB Output is correct
29 Correct 737 ms 76368 KB Output is correct
30 Correct 859 ms 79852 KB Output is correct
31 Correct 839 ms 80100 KB Output is correct
32 Correct 235 ms 27680 KB Output is correct
33 Correct 653 ms 79820 KB Output is correct