oj.uz

Submission #681522

# Submission time Handle Problem Language Result Execution time Memory
681522 2023-01-13T09:01:04 Z nutella Collapse (JOI18_collapse) C++17
5 / 100
 15000 ms 79256 KB 
#include <bits/stdc++.h>
#include "collapse.h"

using namespace std;
using ll = long long;

constexpr int inf = 1e9 + 7;

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) {
    e.erase(stable_partition(e.begin(), e.end(), [&](Edge ed) {
        return ed.l < rx && ed.r > lx;
    }), e.end());

    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);
        }
    }

    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;
        }
    }

    if (lx + 1 < rx) {
        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) {
            assert(w == 0);
            assert(x < y);
            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:34:9: warning: 'Fenwick::n' will be initialized after [-Wreorder]
   34 |     int n{};
      |         ^
collapse.cpp:33:17: warning:   'std::vector<int> Fenwick::t' [-Wreorder]
   33 |     vector<int> t;
      |                 ^
collapse.cpp:37:5: warning:   when initialized here [-Wreorder]
   37 |     Fenwick(int n) : n(n), t(n + 1) {}
      |     ^~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 3532 KB Output is correct
2 Correct 3 ms 2796 KB Output is correct
3 Correct 3 ms 2796 KB Output is correct
4 Correct 3 ms 2844 KB Output is correct
5 Correct 21 ms 3500 KB Output is correct
6 Correct 38 ms 4504 KB Output is correct
7 Correct 3 ms 2928 KB Output is correct
8 Correct 8 ms 3568 KB Output is correct
9 Correct 912 ms 5560 KB Output is correct
10 Correct 814 ms 5568 KB Output is correct
11 Correct 321 ms 5976 KB Output is correct
12 Correct 359 ms 6056 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 6088 KB Output is correct
2 Correct 25 ms 6672 KB Output is correct
3 Correct 434 ms 19788 KB Output is correct
4 Correct 24 ms 6868 KB Output is correct
5 Correct 628 ms 20124 KB Output is correct
6 Correct 58 ms 8480 KB Output is correct
7 Correct 803 ms 41160 KB Output is correct
8 Execution timed out 15079 ms 25728 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 6060 KB Output is correct
2 Correct 25 ms 6244 KB Output is correct
3 Correct 28 ms 6580 KB Output is correct
4 Correct 28 ms 6732 KB Output is correct
5 Correct 31 ms 6892 KB Output is correct
6 Correct 62 ms 8324 KB Output is correct
7 Correct 630 ms 32016 KB Output is correct
8 Correct 2331 ms 43828 KB Output is correct
9 Correct 35 ms 9288 KB Output is correct
10 Correct 5370 ms 37760 KB Output is correct
11 Execution timed out 15088 ms 79256 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 3532 KB Output is correct
2 Correct 3 ms 2796 KB Output is correct
3 Correct 3 ms 2796 KB Output is correct
4 Correct 3 ms 2844 KB Output is correct
5 Correct 21 ms 3500 KB Output is correct
6 Correct 38 ms 4504 KB Output is correct
7 Correct 3 ms 2928 KB Output is correct
8 Correct 8 ms 3568 KB Output is correct
9 Correct 912 ms 5560 KB Output is correct
10 Correct 814 ms 5568 KB Output is correct
11 Correct 321 ms 5976 KB Output is correct
12 Correct 359 ms 6056 KB Output is correct
13 Correct 25 ms 6088 KB Output is correct
14 Correct 25 ms 6672 KB Output is correct
15 Correct 434 ms 19788 KB Output is correct
16 Correct 24 ms 6868 KB Output is correct
17 Correct 628 ms 20124 KB Output is correct
18 Correct 58 ms 8480 KB Output is correct
19 Correct 803 ms 41160 KB Output is correct
20 Execution timed out 15079 ms 25728 KB Time limit exceeded
21 Halted 0 ms 0 KB -