oj.uz

답안 #680763

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
680763 2023-01-11T18:02:45 Z nutella Collapse (JOI18_collapse) C++17
0 / 100
 15000 ms 11564 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 dd(n);
        vector<pair<int, int>> nxt;
        
        for (auto [l, r, a, b, w, x, y] : e) {
            if (l <= W[i] && r > W[i] && dd.unite(a, b)) {
                nxt.push_back({a, b});
            }
        }
        
        DSU d(n);
        for (auto [a, b] : nxt) {
            if ((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
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 3028 KB Output is correct
2 Correct 3 ms 2644 KB Output is correct
3 Incorrect 5 ms 2644 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 4604 KB Output is correct
2 Correct 43 ms 4604 KB Output is correct
3 Execution timed out 15080 ms 11564 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 4564 KB Output is correct
2 Correct 45 ms 4600 KB Output is correct
3 Incorrect 74 ms 4616 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 3028 KB Output is correct
2 Correct 3 ms 2644 KB Output is correct
3 Incorrect 5 ms 2644 KB Output isn't correct
4 Halted 0 ms 0 KB -