oj.uz

Submission #401792

# Submission time Handle Problem Language Result Execution time Memory
401792 2021-05-10T20:14:57 Z timmyfeng Collapse (JOI18_collapse) C++17
100 / 100
 2164 ms 26676 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 100000, B = 256;

vector<array<int, 3>> queries[N];
vector<int> adj[N];
bool visited[N];
int dsu[N];

int find(int u) {
    if (dsu[u] < 0) {
        return u;
    } else {
        dsu[u] = find(dsu[u]);
        return dsu[u];
    }
}

bool unite(int u, int v) {
    u = find(u), v = find(v);
    if (u == v) {
        return false;
    }

    if (-dsu[u] > -dsu[v]) {
        swap(u, v);
    }

    dsu[v] += dsu[u];
    dsu[u] = v;
    return true;
}

void dfs(int u) {
    visited[u] = true;
    for (auto c : adj[u]) {
        if (!visited[c]) {
            dfs(c);
        }
    }
}

vector<int> simulateCollapse(int n, vector<int> t, vector<int> x, vector<int> y, vector<int> w, vector<int> p) {
    int m = t.size(), q = w.size();
    vector<int> ans(q, n);

    for (int k = 0; k < 2; ++k) {
        map<array<int, 2>, int> in;
        vector<array<int, 4>> edges;
        for (int i = 0; i < m; ++i) {
            if (x[i] < y[i]) {
                swap(x[i], y[i]);
            }

            if (t[i] == 0) {
                in[{x[i], y[i]}] = i;
            } else {
                edges.push_back({x[i], y[i], in[{x[i], y[i]}], i});
                in.erase({x[i], y[i]});
            }
        }

        for (auto [e, i] : in) {
            edges.push_back({e[0], e[1], i, m});
        }

        sort(edges.begin(), edges.end());

        for (int i = 0; i < q; ++i) {
            queries[w[i] - w[i] % B].push_back({p[i], w[i], i});
        }

        for (int i = 0; i < m; i += B) {
            sort(queries[i].begin(), queries[i].end());

            vector<array<int, 4>> partial;
            fill(dsu, dsu + n, -1);
            int count = 0;

            int j = 0;
            for (auto [l, s, id] : queries[i]) {
                while (j < (int) edges.size() && edges[j][0] <= l) {
                    auto [u, v, a, b] = edges[j++];
                    if (a <= i && min(m, i + B) <= b) {
                        count += unite(u, v);
                    } else if (!(b <= i || min(m, i + B) <= a)) {
                        partial.push_back({u, v, a, b});
                    }
                }

                vector<int> nodes;
                for (auto [u, v, a, b] : partial) {
                    if (a <= s && s < b) {
                        u = find(u), v = find(v);
                        adj[u].push_back(v);
                        adj[v].push_back(u);
                        nodes.push_back(u);
                        nodes.push_back(v);
                    }
                }

                int res = 0;
                for (auto u : nodes) {
                    if (!visited[u]) {
                        --res;
                        ++ans[id];
                        dfs(u);
                    }
                }

                for (auto u : nodes) {
                    if (visited[u]) {
                        visited[u] = false;
                        adj[u].clear();
                        ++res;
                        --ans[id];
                    }
                }

                ans[id] -= count;
            }

            queries[i].clear();     
        }

        for (int i = 0; i < m; ++i) {
            x[i] = n - 1 - x[i];
            y[i] = n - 1 - y[i];
        }

        for (int i = 0; i < q; ++i) {
            p[i] = n - 2 - p[i];
        }
    }

    return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5452 KB Output is correct
2 Correct 8 ms 5272 KB Output is correct
3 Correct 8 ms 5268 KB Output is correct
4 Correct 9 ms 5272 KB Output is correct
5 Correct 14 ms 5452 KB Output is correct
6 Correct 29 ms 5944 KB Output is correct
7 Correct 6 ms 5264 KB Output is correct
8 Correct 7 ms 5332 KB Output is correct
9 Correct 17 ms 5612 KB Output is correct
10 Correct 35 ms 5712 KB Output is correct
11 Correct 48 ms 6092 KB Output is correct
12 Correct 41 ms 6072 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 8992 KB Output is correct
2 Correct 72 ms 9008 KB Output is correct
3 Correct 226 ms 13796 KB Output is correct
4 Correct 129 ms 9040 KB Output is correct
5 Correct 382 ms 13992 KB Output is correct
6 Correct 309 ms 10092 KB Output is correct
7 Correct 627 ms 22544 KB Output is correct
8 Correct 455 ms 14696 KB Output is correct
9 Correct 51 ms 9404 KB Output is correct
10 Correct 92 ms 9476 KB Output is correct
11 Correct 452 ms 10160 KB Output is correct
12 Correct 566 ms 16540 KB Output is correct
13 Correct 731 ms 19308 KB Output is correct
14 Correct 933 ms 24256 KB Output is correct
15 Correct 749 ms 23764 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 9028 KB Output is correct
2 Correct 82 ms 8968 KB Output is correct
3 Correct 108 ms 8960 KB Output is correct
4 Correct 134 ms 9096 KB Output is correct
5 Correct 401 ms 9000 KB Output is correct
6 Correct 382 ms 10068 KB Output is correct
7 Correct 824 ms 20508 KB Output is correct
8 Correct 1276 ms 23584 KB Output is correct
9 Correct 60 ms 9352 KB Output is correct
10 Correct 666 ms 9844 KB Output is correct
11 Correct 1640 ms 26288 KB Output is correct
12 Correct 2062 ms 26624 KB Output is correct
13 Correct 1687 ms 26256 KB Output is correct
14 Correct 2164 ms 26652 KB Output is correct
15 Correct 1624 ms 26260 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5452 KB Output is correct
2 Correct 8 ms 5272 KB Output is correct
3 Correct 8 ms 5268 KB Output is correct
4 Correct 9 ms 5272 KB Output is correct
5 Correct 14 ms 5452 KB Output is correct
6 Correct 29 ms 5944 KB Output is correct
7 Correct 6 ms 5264 KB Output is correct
8 Correct 7 ms 5332 KB Output is correct
9 Correct 17 ms 5612 KB Output is correct
10 Correct 35 ms 5712 KB Output is correct
11 Correct 48 ms 6092 KB Output is correct
12 Correct 41 ms 6072 KB Output is correct
13 Correct 50 ms 8992 KB Output is correct
14 Correct 72 ms 9008 KB Output is correct
15 Correct 226 ms 13796 KB Output is correct
16 Correct 129 ms 9040 KB Output is correct
17 Correct 382 ms 13992 KB Output is correct
18 Correct 309 ms 10092 KB Output is correct
19 Correct 627 ms 22544 KB Output is correct
20 Correct 455 ms 14696 KB Output is correct
21 Correct 51 ms 9404 KB Output is correct
22 Correct 92 ms 9476 KB Output is correct
23 Correct 452 ms 10160 KB Output is correct
24 Correct 566 ms 16540 KB Output is correct
25 Correct 731 ms 19308 KB Output is correct
26 Correct 933 ms 24256 KB Output is correct
27 Correct 749 ms 23764 KB Output is correct
28 Correct 49 ms 9028 KB Output is correct
29 Correct 82 ms 8968 KB Output is correct
30 Correct 108 ms 8960 KB Output is correct
31 Correct 134 ms 9096 KB Output is correct
32 Correct 401 ms 9000 KB Output is correct
33 Correct 382 ms 10068 KB Output is correct
34 Correct 824 ms 20508 KB Output is correct
35 Correct 1276 ms 23584 KB Output is correct
36 Correct 60 ms 9352 KB Output is correct
37 Correct 666 ms 9844 KB Output is correct
38 Correct 1640 ms 26288 KB Output is correct
39 Correct 2062 ms 26624 KB Output is correct
40 Correct 1687 ms 26256 KB Output is correct
41 Correct 2164 ms 26652 KB Output is correct
42 Correct 1624 ms 26260 KB Output is correct
43 Correct 609 ms 15084 KB Output is correct
44 Correct 1118 ms 23248 KB Output is correct
45 Correct 747 ms 15404 KB Output is correct
46 Correct 1292 ms 23528 KB Output is correct
47 Correct 61 ms 9348 KB Output is correct
48 Correct 84 ms 9444 KB Output is correct
49 Correct 580 ms 9864 KB Output is correct
50 Correct 747 ms 11964 KB Output is correct
51 Correct 846 ms 17192 KB Output is correct
52 Correct 1377 ms 19432 KB Output is correct
53 Correct 1200 ms 18848 KB Output is correct
54 Correct 1561 ms 21868 KB Output is correct
55 Correct 1426 ms 21348 KB Output is correct
56 Correct 1509 ms 22904 KB Output is correct
57 Correct 1580 ms 24564 KB Output is correct
58 Correct 1897 ms 24944 KB Output is correct
59 Correct 1638 ms 26128 KB Output is correct
60 Correct 2074 ms 26676 KB Output is correct