oj.uz

Submission #680762

# Submission time Handle Problem Language Result Execution time Memory
680762 2023-01-11T18:00:54 Z nutella Collapse (JOI18_collapse) C++17
5 / 100
 15000 ms 16700 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;
        }
    }

    void modify(int l, int r, int val) {
        modify(l, val), modify(r, -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;
    ll 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], S = 0;

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);
            S += 1;
            fn.modify(x, y, 1);
            d2.unite(u, v);
        }
    }

    if (lx + 1 == rx) {
        for (auto [i, u] : queries[lx]) {
            answer[i] = S - 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(l, r, -1);
        S -= 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;

    fn = Fenwick(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], Y[i] - X[i], X[i], Y[i]});
            last.erase({X[i], Y[i]});
        }
    }

    for (auto [x, y] : last) {
        e.push_back({y, c, x.first, x.second, x.second - x.first, x.first, x.second});
    }

    sort(e.begin(), e.end());

    for (int i = 0; i < c; ++i) {
        queries[W[i]].push_back({i, P[i]});
    }

//    solve(0, c, e, n);

    vector<int> ans(q);
    for (int i = 0; i < q; ++i) {
        ans[i] = n - answer[i];


        int cnt = n;
        DSU d(n);
        for (auto [l, r, a, b, w, x, y] : e) {
            if (l <= W[i] && r > W[i] && (a > P[i] || b <= P[i]) && d.unite(a, b)) {
                cnt -= 1;
            }
        }

        ans[i] = cnt;
    }

    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 16 ms 3028 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 3 ms 2644 KB Output is correct
4 Correct 4 ms 2708 KB Output is correct
5 Correct 32 ms 3048 KB Output is correct
6 Correct 208 ms 3560 KB Output is correct
7 Correct 22 ms 2772 KB Output is correct
8 Correct 27 ms 2824 KB Output is correct
9 Correct 63 ms 3220 KB Output is correct
10 Correct 126 ms 3288 KB Output is correct
11 Correct 281 ms 3668 KB Output is correct
12 Correct 282 ms 3668 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 4600 KB Output is correct
2 Correct 29 ms 4628 KB Output is correct
3 Correct 13758 ms 11636 KB Output is correct
4 Correct 46 ms 5080 KB Output is correct
5 Execution timed out 15069 ms 13248 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 4504 KB Output is correct
2 Correct 31 ms 4564 KB Output is correct
3 Correct 36 ms 4600 KB Output is correct
4 Correct 52 ms 5076 KB Output is correct
5 Correct 492 ms 5232 KB Output is correct
6 Correct 3700 ms 6108 KB Output is correct
7 Execution timed out 15092 ms 16700 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 3028 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 3 ms 2644 KB Output is correct
4 Correct 4 ms 2708 KB Output is correct
5 Correct 32 ms 3048 KB Output is correct
6 Correct 208 ms 3560 KB Output is correct
7 Correct 22 ms 2772 KB Output is correct
8 Correct 27 ms 2824 KB Output is correct
9 Correct 63 ms 3220 KB Output is correct
10 Correct 126 ms 3288 KB Output is correct
11 Correct 281 ms 3668 KB Output is correct
12 Correct 282 ms 3668 KB Output is correct
13 Correct 27 ms 4600 KB Output is correct
14 Correct 29 ms 4628 KB Output is correct
15 Correct 13758 ms 11636 KB Output is correct
16 Correct 46 ms 5080 KB Output is correct
17 Execution timed out 15069 ms 13248 KB Time limit exceeded
18 Halted 0 ms 0 KB -