Submission #681530

#	Time	Username	Problem	Language	Result	Execution time	Memory
681530		nutella	Collapse (JOI18_collapse)	C++17	100 / 100	1060 ms	61524 KiB

collapse

#include <bits/stdc++.h>
#include "collapse.h"

using namespace std;

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) {
    vector<Edge> nxt;
    for (auto &ed: e) {
        if (ed.l >= rx || ed.r <= lx) {
        } else {
            nxt.push_back(ed);
        }
    }
    swap(e, nxt);
    
    vector<int> alive(sz);
    for (auto &ed : e) {
        alive[ed.u] = alive[ed.v] = 1;
    }
    
    vector<int> id(sz);
    int last_id = 0;
    for (int i = 0; i < sz; ++i) {
        if (alive[i]) {
            id[i] = last_id++;
        }
    }
    
    sz = last_id;
    for (auto &ed : e) {
        ed.u = id[ed.u], ed.v = id[ed.v];
    }
    
    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);
        }
    } else {
        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 = inf, r = -inf;
            }
        }

        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 (stderr)

collapse.cpp: In constructor 'Fenwick::Fenwick(int)':
collapse.cpp:33:9: warning: 'Fenwick::n' will be initialized after [-Wreorder]
   33 |     int n{};
      |         ^
collapse.cpp:32:17: warning:   'std::vector<int> Fenwick::t' [-Wreorder]
   32 |     vector<int> t;
      |                 ^
collapse.cpp:37:5: warning:   when initialized here [-Wreorder]
   37 |     Fenwick(int n) : n(n), t(n + 1) {}
      |     ^~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 35 / 35