oj.uz

Submission #681528

# Submission time Handle Problem Language Result Execution time Memory
681528 2023-01-13T09:10:22 Z nutella Collapse (JOI18_collapse) C++17
5 / 100
 15000 ms 81204 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) {
        return p[x] == x ? x : p[x] = get(p[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) {
    vector<Edge> nxt;
    for (auto &ed: e) {
        if (ed.l >= rx || ed.r <= lx) {
        } else {
            nxt.push_back(ed);
        }
    }
    swap(e, nxt);

    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<pair<int, int>> done;
    for (auto [l, r, u, v, w, x, y]: e) {
        if (l <= lx && rx <= r && d1.unite(u, v)) {
            done.emplace_back(x, 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 {
        vector<int> id(sz);
        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 (auto [l, 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:31:9: warning: 'Fenwick::n' will be initialized after [-Wreorder]
   31 |     int n{};
      |         ^
collapse.cpp:30:17: warning:   'std::vector<int> Fenwick::t' [-Wreorder]
   30 |     vector<int> t;
      |                 ^
collapse.cpp:35:5: warning:   when initialized here [-Wreorder]
   35 |     Fenwick(int n) : n(n), t(n + 1) {}
      |     ^~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 3540 KB Output is correct
2 Correct 3 ms 2772 KB Output is correct
3 Correct 3 ms 2824 KB Output is correct
4 Correct 3 ms 2772 KB Output is correct
5 Correct 20 ms 3608 KB Output is correct
6 Correct 38 ms 4972 KB Output is correct
7 Correct 3 ms 2900 KB Output is correct
8 Correct 5 ms 3468 KB Output is correct
9 Correct 563 ms 5544 KB Output is correct
10 Correct 480 ms 5580 KB Output is correct
11 Correct 226 ms 6200 KB Output is correct
12 Correct 252 ms 6216 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 5736 KB Output is correct
2 Correct 27 ms 6228 KB Output is correct
3 Correct 443 ms 20600 KB Output is correct
4 Correct 25 ms 6356 KB Output is correct
5 Correct 584 ms 20552 KB Output is correct
6 Correct 61 ms 8024 KB Output is correct
7 Correct 872 ms 44712 KB Output is correct
8 Correct 13673 ms 26204 KB Output is correct
9 Correct 34 ms 8120 KB Output is correct
10 Correct 80 ms 19384 KB Output is correct
11 Correct 5292 ms 39784 KB Output is correct
12 Execution timed out 15037 ms 70408 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 5744 KB Output is correct
2 Correct 36 ms 5972 KB Output is correct
3 Correct 32 ms 6248 KB Output is correct
4 Correct 26 ms 6356 KB Output is correct
5 Correct 32 ms 6348 KB Output is correct
6 Correct 60 ms 7956 KB Output is correct
7 Correct 622 ms 36448 KB Output is correct
8 Correct 1713 ms 47808 KB Output is correct
9 Correct 31 ms 7272 KB Output is correct
10 Correct 4250 ms 35528 KB Output is correct
11 Execution timed out 15080 ms 81204 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 3540 KB Output is correct
2 Correct 3 ms 2772 KB Output is correct
3 Correct 3 ms 2824 KB Output is correct
4 Correct 3 ms 2772 KB Output is correct
5 Correct 20 ms 3608 KB Output is correct
6 Correct 38 ms 4972 KB Output is correct
7 Correct 3 ms 2900 KB Output is correct
8 Correct 5 ms 3468 KB Output is correct
9 Correct 563 ms 5544 KB Output is correct
10 Correct 480 ms 5580 KB Output is correct
11 Correct 226 ms 6200 KB Output is correct
12 Correct 252 ms 6216 KB Output is correct
13 Correct 26 ms 5736 KB Output is correct
14 Correct 27 ms 6228 KB Output is correct
15 Correct 443 ms 20600 KB Output is correct
16 Correct 25 ms 6356 KB Output is correct
17 Correct 584 ms 20552 KB Output is correct
18 Correct 61 ms 8024 KB Output is correct
19 Correct 872 ms 44712 KB Output is correct
20 Correct 13673 ms 26204 KB Output is correct
21 Correct 34 ms 8120 KB Output is correct
22 Correct 80 ms 19384 KB Output is correct
23 Correct 5292 ms 39784 KB Output is correct
24 Execution timed out 15037 ms 70408 KB Time limit exceeded
25 Halted 0 ms 0 KB -