제출 #686533

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
686533		wenqi	Collapse (JOI18_collapse)	C++17	0 / 100	24 ms	7112 KiB

collapse

#include "collapse.h"
#include <bits/stdc++.h>
using namespace std;

int ans[100069];

struct UF {
    int parents[100069];
    int heights[100069];
    int ncomp;

    using Action = tuple<int, int, int, int>;
    vector<Action> actions;

    void init(int N) {
        for (int i = 0; i < N; i++) {
            parents[i] = i;
            heights[i] = 0;
        }
        ncomp = N;
    }

    int getp(int i) {
        return i == parents[i] ? i : getp(parents[i]);
    }

    bool merge(int i, int j) {
        int pi = getp(i);
        int pj = getp(j);
        if (pi == pj) return false;
        if (heights[pi] < heights[pj]) {
            swap(pi, pj);
        }
        actions.push_back({pj, parents[pj], pi, heights[pi]});
        parents[pj] = pi;
        heights[pi] = max(heights[pi], heights[pj] + 1);
        ncomp--;
        return true;
    }

    void pop() {
        auto [a, x, b, y] = actions.back();
        parents[a] = x;
        heights[b] = y;
        ncomp++;
        actions.pop_back();
    }
};

UF uf;

struct Point {
    int x, y;
};

struct Rect {
    int x1, x2, y1, y2;

    bool contains(const Rect &a) const {
        return x1 <= a.x1 and a.x2 <= x2 and y1 <= a.y1 and a.y2 <= y2;
    }

    bool outside(const Rect &a) const {
        return x2 < a.x1 or a.x2 < x1 or y2 < a.y1 or a.y2 < y1;
    }

    bool contains(const Point &a) const {
        return x1 <= a.x and a.x <= x2 and y1 <= a.y and a.y <= y2;
    }

    bool outside(const Point &a) const {
        return x2 < a.x or a.x < x1 or y2 < a.y or a.y < y1;
    }
};

using Update = tuple<Rect, int, int>;
using Query = pair<Point, int>;

void decomp(Rect cur, vector<Update> ups, vector<Query> queries) {
    if (queries.empty()) return;
    if (ups.empty()) {
        for (auto [p, qid] : queries) {
            ans[qid] = uf.ncomp;
        }
        return;
    }
    int cnt = 0;
    for (auto &[r, i, j] : ups) if (r.contains(cur)) cnt += uf.merge(i, j);
    if (cur.x1 == cur.x2 and cur.y1 == cur.y2) {
        for (auto [p, qid] : queries) {
            ans[qid] = uf.ncomp;
        }
        for (int i = 0; i < cnt; i++) uf.pop();
        return;
    }
    int mx = (cur.x1 + cur.x2) / 2;
    int my = (cur.y1 + cur.y2) / 2;
    Rect up {cur.x1, cur.x2, cur.y1, my}, down {cur.x1, cur.x2, my + 1, cur.y2}, left {cur.x1, mx, cur.y1, cur.y2}, right {mx + 1, cur.x2, cur.y1, cur.y2};
    vector<Update> uup, udown, uleft, uright;
    for (auto &[r, i, j] : ups) {
        if (cur.contains(r)) continue;
        if (not up.outside(r)) uup.push_back({r, i, j});
        if (not down.outside(r)) udown.push_back({r, i, j});
        if (not left.outside(r)) uleft.push_back({r, i, j});
        if (not right.outside(r)) uright.push_back({r, i, j});
    }
    if ((uup.size() + udown.size() < uleft.size() + uright.size() and cur.y1 != cur.y2) || cur.x1 == cur.x2) {
        vector<Query> qup, qdown;
        for (auto &[p, qid] : queries) {
            if (not up.outside(p)) qup.push_back({p, qid});
            if (not down.outside(p)) qdown.push_back({p, qid});
        }
        decomp(up, uup, qup);
        decomp(down, udown, qdown);
    } else {
        vector<Query> qleft, qright;
        for (auto &[p, qid] : queries) {
            if (not left.outside(p)) qleft.push_back({p, qid});
            if (not right.outside(p)) qright.push_back({p, qid});
        }
        decomp(left, uleft, qleft);
        decomp(right, uright, qright);
    }
    for (int i = 0; i < cnt; i++) uf.pop();
}

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
        ) {
    uf.init(N);
    vector<Query> queries;
    vector<Update> ups;
    for (int i = 0; i < W.size(); i++) {
        queries.push_back({{P[i], W[i]}, i});
    }
    map<pair<int, int>, int> S;
    for (int i = 0; i < T.size(); i++) {
        int x = min(X[i], Y[i]);
        int y = max(X[i], Y[i]);
        if (T[i]) {
            int y1 = S[{x, y}];
            ups.push_back({{0, x - 1, y1, i - 1}, x, y});
            ups.push_back({{y, N - 1, y1, i - 1}, x, y});
            S[{x, y}] = -1;
        } else {
            S[{x, y}] = i;
        }
    }
    int e = T.size() - 1;
    for (auto [a, b] : S) {
        if (b == -1) continue;
        auto [x, y] = a;
        int y1 = b;
        ups.push_back({{0, x - 1, y1, e}, x, y});
        ups.push_back({{y, N - 1, y1, e}, x, y});
    }
    decomp(Rect {0, N - 1, 0, (int) T.size() - 1}, ups, queries);
    for (int i = 0; i < W.size(); i++) {
        W[i] = ans[i];
    }
    return W;
}

컴파일 시 표준 에러 (stderr) 메시지

collapse.cpp: In function 'std::vector<int> simulateCollapse(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
collapse.cpp:138:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |     for (int i = 0; i < W.size(); i++) {
      |                     ~~^~~~~~~~~~
collapse.cpp:142:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |     for (int i = 0; i < T.size(); i++) {
      |                     ~~^~~~~~~~~~
collapse.cpp:163:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |     for (int i = 0; i < W.size(); i++) {
      |                     ~~^~~~~~~~~~

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