oj.uz

Submission #681541

# Submission time Handle Problem Language Result Execution time Memory
681541 2023-01-13T09:31:14 Z nutella Collapse (JOI18_collapse) C++17
100 / 100
 987 ms 48864 KB 
#include <bits/stdc++.h>
#include "collapse.h"

using namespace std;

struct DSU {
    vector<int> p, sz;

    DSU(int n) : p(n), sz(n, 1) {
        iota(p.begin(), p.end(), 0);
    }

    DSU() = default;

    int get(int x) {
        while (x != p[x]) x = p[x] = p[p[x]];
        return x;
    }

    bool unite(int a, int b) {
        a = get(a), b = get(b);
        if (a == b) return false;
        if (sz[a] < sz[b]) swap(a, b);
        p[b] = a;
        sz[a] += sz[b];
        return true;
    }
};

struct Fenwick {
    vector<int> t;
    int n{};

    Fenwick() = default;

    Fenwick(int n) : n(n), t(n + 1) {}

    void modify(int i, int val) {
        for (int x = i + 1; x <= n; x += x & -x) {
            t[x] += val;
        }
    }

    int sum(int i) {
        int ans = 0;
        for (int x = i + 1; x > 0; x -= x & -x) {
            ans += t[x];
        }
        return ans;
    }
};

struct Edge {
    int l, r;
    int u, v;
    int w;
    int x, y;

    bool operator<(Edge b) const {
        return w < b.w;
    }
};

constexpr int N = 100001;

vector<array<int, 2>> queries[N];

int n, answer[N];

Fenwick fn;

void solve(int lx, int rx, vector<Edge> e, int sz) {
    e.erase(stable_partition(e.begin(), e.end(), [&](Edge ed) {
        return ed.l < rx && ed.r > lx;
    }), e.end());

    vector<int> id(sz);
    for (auto &ed : e) {
        id[ed.u] = id[ed.v] = 1;
    }

    int last_id = 0;
    for (int i = 0; i < sz; ++i) {
        if (id[i]) {
            id[i] = last_id++;
        }
    }

    sz = last_id;

    for (auto &ed : e) {
        ed.u = id[ed.u], ed.v = id[ed.v];
    }

    DSU d1(sz), d2(sz);
    for (auto [l, r, u, v, w, x, y]: e) {
        if (l > lx || r < rx) {
            d1.unite(u, v);
        }
    }

    vector<int> done;
    for (auto [l, r, u, v, w, x, y]: e) {
        if (l <= lx && rx <= r && d1.unite(u, v)) {
            done.push_back(y);

            d2.unite(u, v);

            fn.modify(y, 1);
        }
    }

    if (lx + 1 == rx) {
        for (auto [i, u]: queries[lx]) {
            answer[i] += fn.sum(u);
        }
    } else {
        int cnt = 0;
        for (int i = 0; i < sz; ++i) {
            if (d2.get(i) == i) {
                id[i] = cnt++;
            }
        }

        DSU d(cnt);
        for (auto &[l, r, u, v, w, x, y]: e) {
            u = id[d2.get(u)], v = id[d2.get(v)];
            if (l <= lx && rx <= r && !d.unite(u, v)) {
                l = rx + 228, r = lx - 228;
            }
        }

        int mid = (lx + rx) / 2;
        solve(lx, mid, e, cnt), solve(mid, rx, e, cnt);
    }

    for (int r : done) {
        fn.modify(r, -1);
    }
}

std::vector<int> simulateCollapse(int N, std::vector<int> T, std::vector<int> X, std::vector<int> Y, std::vector<int> W,
                                  std::vector<int> P) {
    const int q = P.size(), c = T.size();
    ::n = N;


    map<pair<int, int>, int> last;

    vector<Edge> e;

    for (int i = 0; i < c; ++i) {
        if (X[i] > Y[i]) {
            swap(X[i], Y[i]);
        }
        if (T[i] == 0) {
            last[{X[i], Y[i]}] = i;
        } else {
            e.push_back({last[{X[i], Y[i]}], i, X[i], Y[i], 0, X[i], Y[i]});
            last.erase({X[i], Y[i]});
        }
    }

    for (auto [x, y]: last) {
        e.push_back({y, c, x.first, x.second, 0, x.first, x.second});
    }

    for (int _ = 0; _ < 2; ++_) {
        fn = Fenwick(n);

        for (auto &[s, t, a, b, w, x, y]: e) {
            w = y;
        }

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

        for (int i = 0; i < c; ++i) {
            queries[i].clear();
        }

        for (int i = 0; i < q; ++i) {
            queries[W[i]].push_back({i, P[i]});
        }

        solve(0, c, e, n);

        for (auto &[s, t, a, b, w, x, y]: e) {
            x = n - x - 1, y = n - y - 1;
            swap(x, y);
            a = x, b = y;
            w = 0;
        }

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

    vector<int> ans(q);
    for (int i = 0; i < q; ++i) {
        ans[i] = n - answer[i];
    }

    return ans;
}

Compilation message

collapse.cpp: In constructor 'Fenwick::Fenwick(int)':
collapse.cpp:32:9: warning: 'Fenwick::n' will be initialized after [-Wreorder]
   32 |     int n{};
      |         ^
collapse.cpp:31:17: warning:   'std::vector<int> Fenwick::t' [-Wreorder]
   31 |     vector<int> t;
      |                 ^
collapse.cpp:36:5: warning:   when initialized here [-Wreorder]
   36 |     Fenwick(int n) : n(n), t(n + 1) {}
      |     ^~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 3412 KB Output is correct
2 Correct 3 ms 2772 KB Output is correct
3 Correct 3 ms 2772 KB Output is correct
4 Correct 3 ms 2772 KB Output is correct
5 Correct 21 ms 3452 KB Output is correct
6 Correct 34 ms 4496 KB Output is correct
7 Correct 3 ms 2900 KB Output is correct
8 Correct 5 ms 2772 KB Output is correct
9 Correct 21 ms 3808 KB Output is correct
10 Correct 27 ms 4056 KB Output is correct
11 Correct 32 ms 5108 KB Output is correct
12 Correct 33 ms 4992 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 5744 KB Output is correct
2 Correct 27 ms 6276 KB Output is correct
3 Correct 434 ms 18376 KB Output is correct
4 Correct 33 ms 6356 KB Output is correct
5 Correct 542 ms 18428 KB Output is correct
6 Correct 60 ms 7684 KB Output is correct
7 Correct 874 ms 39180 KB Output is correct
8 Correct 474 ms 19868 KB Output is correct
9 Correct 27 ms 6088 KB Output is correct
10 Correct 29 ms 6260 KB Output is correct
11 Correct 37 ms 7244 KB Output is correct
12 Correct 495 ms 23480 KB Output is correct
13 Correct 722 ms 33924 KB Output is correct
14 Correct 794 ms 48864 KB Output is correct
15 Correct 783 ms 47920 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 5752 KB Output is correct
2 Correct 26 ms 5848 KB Output is correct
3 Correct 26 ms 6248 KB Output is correct
4 Correct 33 ms 6264 KB Output is correct
5 Correct 33 ms 6328 KB Output is correct
6 Correct 70 ms 7652 KB Output is correct
7 Correct 593 ms 30232 KB Output is correct
8 Correct 987 ms 41436 KB Output is correct
9 Correct 36 ms 6088 KB Output is correct
10 Correct 41 ms 6996 KB Output is correct
11 Correct 826 ms 46580 KB Output is correct
12 Correct 805 ms 47912 KB Output is correct
13 Correct 848 ms 46428 KB Output is correct
14 Correct 771 ms 47800 KB Output is correct
15 Correct 861 ms 46520 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 3412 KB Output is correct
2 Correct 3 ms 2772 KB Output is correct
3 Correct 3 ms 2772 KB Output is correct
4 Correct 3 ms 2772 KB Output is correct
5 Correct 21 ms 3452 KB Output is correct
6 Correct 34 ms 4496 KB Output is correct
7 Correct 3 ms 2900 KB Output is correct
8 Correct 5 ms 2772 KB Output is correct
9 Correct 21 ms 3808 KB Output is correct
10 Correct 27 ms 4056 KB Output is correct
11 Correct 32 ms 5108 KB Output is correct
12 Correct 33 ms 4992 KB Output is correct
13 Correct 26 ms 5744 KB Output is correct
14 Correct 27 ms 6276 KB Output is correct
15 Correct 434 ms 18376 KB Output is correct
16 Correct 33 ms 6356 KB Output is correct
17 Correct 542 ms 18428 KB Output is correct
18 Correct 60 ms 7684 KB Output is correct
19 Correct 874 ms 39180 KB Output is correct
20 Correct 474 ms 19868 KB Output is correct
21 Correct 27 ms 6088 KB Output is correct
22 Correct 29 ms 6260 KB Output is correct
23 Correct 37 ms 7244 KB Output is correct
24 Correct 495 ms 23480 KB Output is correct
25 Correct 722 ms 33924 KB Output is correct
26 Correct 794 ms 48864 KB Output is correct
27 Correct 783 ms 47920 KB Output is correct
28 Correct 28 ms 5752 KB Output is correct
29 Correct 26 ms 5848 KB Output is correct
30 Correct 26 ms 6248 KB Output is correct
31 Correct 33 ms 6264 KB Output is correct
32 Correct 33 ms 6328 KB Output is correct
33 Correct 70 ms 7652 KB Output is correct
34 Correct 593 ms 30232 KB Output is correct
35 Correct 987 ms 41436 KB Output is correct
36 Correct 36 ms 6088 KB Output is correct
37 Correct 41 ms 6996 KB Output is correct
38 Correct 826 ms 46580 KB Output is correct
39 Correct 805 ms 47912 KB Output is correct
40 Correct 848 ms 46428 KB Output is correct
41 Correct 771 ms 47800 KB Output is correct
42 Correct 861 ms 46520 KB Output is correct
43 Correct 429 ms 17740 KB Output is correct
44 Correct 839 ms 38160 KB Output is correct
45 Correct 461 ms 18908 KB Output is correct
46 Correct 966 ms 41360 KB Output is correct
47 Correct 29 ms 6124 KB Output is correct
48 Correct 32 ms 6356 KB Output is correct
49 Correct 44 ms 7284 KB Output is correct
50 Correct 118 ms 11288 KB Output is correct
51 Correct 487 ms 21164 KB Output is correct
52 Correct 661 ms 29644 KB Output is correct
53 Correct 617 ms 27952 KB Output is correct
54 Correct 696 ms 34176 KB Output is correct
55 Correct 740 ms 32948 KB Output is correct
56 Correct 759 ms 37688 KB Output is correct
57 Correct 806 ms 42180 KB Output is correct
58 Correct 727 ms 42828 KB Output is correct
59 Correct 832 ms 46580 KB Output is correct
60 Correct 803 ms 47784 KB Output is correct