oj.uz

Submission #681525

# Submission time Handle Problem Language Result Execution time Memory
681525 2023-01-13T09:06:08 Z nutella Collapse (JOI18_collapse) C++17
5 / 100
 15000 ms 76816 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 3420 KB Output is correct
6 Correct 32 ms 4456 KB Output is correct
7 Correct 3 ms 2900 KB Output is correct
8 Correct 6 ms 3512 KB Output is correct
9 Correct 868 ms 5416 KB Output is correct
10 Correct 739 ms 5664 KB Output is correct
11 Correct 320 ms 5860 KB Output is correct
12 Correct 354 ms 6252 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 5744 KB Output is correct
2 Correct 24 ms 6260 KB Output is correct
3 Correct 418 ms 18424 KB Output is correct
4 Correct 27 ms 6400 KB Output is correct
5 Correct 598 ms 18476 KB Output is correct
6 Correct 58 ms 7696 KB Output is correct
7 Correct 787 ms 39272 KB Output is correct
8 Execution timed out 15094 ms 23684 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 26 ms 5872 KB Output is correct
3 Correct 26 ms 6228 KB Output is correct
4 Correct 26 ms 6248 KB Output is correct
5 Correct 30 ms 6220 KB Output is correct
6 Correct 59 ms 7600 KB Output is correct
7 Correct 601 ms 30508 KB Output is correct
8 Correct 2082 ms 41732 KB Output is correct
9 Correct 32 ms 8504 KB Output is correct
10 Correct 5134 ms 36956 KB Output is correct
11 Execution timed out 15093 ms 76816 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 3420 KB Output is correct
6 Correct 32 ms 4456 KB Output is correct
7 Correct 3 ms 2900 KB Output is correct
8 Correct 6 ms 3512 KB Output is correct
9 Correct 868 ms 5416 KB Output is correct
10 Correct 739 ms 5664 KB Output is correct
11 Correct 320 ms 5860 KB Output is correct
12 Correct 354 ms 6252 KB Output is correct
13 Correct 26 ms 5744 KB Output is correct
14 Correct 24 ms 6260 KB Output is correct
15 Correct 418 ms 18424 KB Output is correct
16 Correct 27 ms 6400 KB Output is correct
17 Correct 598 ms 18476 KB Output is correct
18 Correct 58 ms 7696 KB Output is correct
19 Correct 787 ms 39272 KB Output is correct
20 Execution timed out 15094 ms 23684 KB Time limit exceeded
21 Halted 0 ms 0 KB -