oj.uz

Submission #681524

# Submission time Handle Problem Language Result Execution time Memory
681524 2023-01-13T09:05:03 Z nutella Collapse (JOI18_collapse) C++17
5 / 100
 15000 ms 76764 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) {
    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) {
            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:34:5: warning:   when initialized here [-Wreorder]
   34 |     Fenwick(int n) : n(n), t(n + 1) {}
      |     ^~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 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 22 ms 3412 KB Output is correct
6 Correct 32 ms 4512 KB Output is correct
7 Correct 3 ms 2900 KB Output is correct
8 Correct 6 ms 3560 KB Output is correct
9 Correct 883 ms 5452 KB Output is correct
10 Correct 760 ms 5536 KB Output is correct
11 Correct 333 ms 5864 KB Output is correct
12 Correct 357 ms 6000 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 5776 KB Output is correct
2 Correct 24 ms 6228 KB Output is correct
3 Correct 440 ms 18504 KB Output is correct
4 Correct 24 ms 6388 KB Output is correct
5 Correct 657 ms 18444 KB Output is correct
6 Correct 57 ms 7688 KB Output is correct
7 Correct 821 ms 39500 KB Output is correct
8 Execution timed out 15011 ms 23648 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 5704 KB Output is correct
2 Correct 25 ms 5884 KB Output is correct
3 Correct 25 ms 6220 KB Output is correct
4 Correct 28 ms 6356 KB Output is correct
5 Correct 33 ms 6340 KB Output is correct
6 Correct 57 ms 7596 KB Output is correct
7 Correct 620 ms 30412 KB Output is correct
8 Correct 2151 ms 41772 KB Output is correct
9 Correct 31 ms 8520 KB Output is correct
10 Correct 5446 ms 37020 KB Output is correct
11 Execution timed out 15077 ms 76764 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 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 22 ms 3412 KB Output is correct
6 Correct 32 ms 4512 KB Output is correct
7 Correct 3 ms 2900 KB Output is correct
8 Correct 6 ms 3560 KB Output is correct
9 Correct 883 ms 5452 KB Output is correct
10 Correct 760 ms 5536 KB Output is correct
11 Correct 333 ms 5864 KB Output is correct
12 Correct 357 ms 6000 KB Output is correct
13 Correct 26 ms 5776 KB Output is correct
14 Correct 24 ms 6228 KB Output is correct
15 Correct 440 ms 18504 KB Output is correct
16 Correct 24 ms 6388 KB Output is correct
17 Correct 657 ms 18444 KB Output is correct
18 Correct 57 ms 7688 KB Output is correct
19 Correct 821 ms 39500 KB Output is correct
20 Execution timed out 15011 ms 23648 KB Time limit exceeded
21 Halted 0 ms 0 KB -