oj.uz

Submission #681526

# Submission time Handle Problem Language Result Execution time Memory
681526 2023-01-13T09:07:25 Z nutella Collapse (JOI18_collapse) C++17
5 / 100
 15000 ms 82136 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);
        }
    }

    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 3584 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 2 ms 2772 KB Output is correct
4 Correct 3 ms 2772 KB Output is correct
5 Correct 20 ms 3544 KB Output is correct
6 Correct 34 ms 4736 KB Output is correct
7 Correct 3 ms 2900 KB Output is correct
8 Correct 6 ms 3532 KB Output is correct
9 Correct 844 ms 5544 KB Output is correct
10 Correct 689 ms 5964 KB Output is correct
11 Correct 313 ms 6260 KB Output is correct
12 Correct 346 ms 6328 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 5740 KB Output is correct
2 Correct 25 ms 6200 KB Output is correct
3 Correct 443 ms 20584 KB Output is correct
4 Correct 23 ms 6356 KB Output is correct
5 Correct 631 ms 20732 KB Output is correct
6 Correct 58 ms 8104 KB Output is correct
7 Correct 844 ms 44796 KB Output is correct
8 Execution timed out 15005 ms 25500 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 5704 KB Output is correct
2 Correct 24 ms 5884 KB Output is correct
3 Correct 25 ms 6240 KB Output is correct
4 Correct 25 ms 6320 KB Output is correct
5 Correct 29 ms 6352 KB Output is correct
6 Correct 60 ms 7872 KB Output is correct
7 Correct 626 ms 35396 KB Output is correct
8 Correct 2175 ms 48260 KB Output is correct
9 Correct 30 ms 8524 KB Output is correct
10 Correct 5368 ms 36952 KB Output is correct
11 Execution timed out 15052 ms 82136 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 3584 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 2 ms 2772 KB Output is correct
4 Correct 3 ms 2772 KB Output is correct
5 Correct 20 ms 3544 KB Output is correct
6 Correct 34 ms 4736 KB Output is correct
7 Correct 3 ms 2900 KB Output is correct
8 Correct 6 ms 3532 KB Output is correct
9 Correct 844 ms 5544 KB Output is correct
10 Correct 689 ms 5964 KB Output is correct
11 Correct 313 ms 6260 KB Output is correct
12 Correct 346 ms 6328 KB Output is correct
13 Correct 28 ms 5740 KB Output is correct
14 Correct 25 ms 6200 KB Output is correct
15 Correct 443 ms 20584 KB Output is correct
16 Correct 23 ms 6356 KB Output is correct
17 Correct 631 ms 20732 KB Output is correct
18 Correct 58 ms 8104 KB Output is correct
19 Correct 844 ms 44796 KB Output is correct
20 Execution timed out 15005 ms 25500 KB Time limit exceeded
21 Halted 0 ms 0 KB -