제출 #1124401

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1124401		GasmaskChan	Plahte (COCI17_plahte)	C++17	0 / 160	1207 ms	589824 KiB

plahte

#include <bits/stdc++.h>

using namespace std;
#define ll long long

const int MAX = 8e4 + 5;

struct DSU {
    vector<int> p;

    DSU(int n) {
        p.assign(n + 5, -1);
    }

    int get(int u) {
        return p[u] < 0 ? u : p[u] = get(p[u]);
    }

    bool ketnoi(int u, int v) {
        u = get(u), v = get(v);
        if (u == v) return false;
        if (p[u] > p[v]) swap(u, v);
        p[u] += p[v];
        p[v] = u;
        return true;
    }

    int sz(int u) {
        return -p[get(u)];
    }
};

vector<int> g[MAX];

struct rec {
    int x1, y1, x2, y2;
};

struct event {
    int x, y1, y2, type, id, pre_x;
    bool operator < (const event &other) const {
        if (x != other.x) return x < other.x;
        return type > other.type;
    }
};

int sz[MAX];
bitset<MAX> visited;
void dfs(int u, int p, DSU &color) {
    visited[u] = true;
    sz[u] = color.sz(u) - 1;
    for (int &v : g[u]) {
        if (v != p && !visited[v]) {
            dfs(v, u, color);
            sz[u] += sz[v];
        }
    }
}

rec a[MAX];
array<int, 3> muc[MAX];
vector<set<pair<int, int>, greater<pair<int, int>>>> sech;
vector<int> nenK, nenY;
vector<event> events;
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    // freopen("loangmuc.inp", "r", stdin); freopen("loangmuc.out", "w", stdout);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].x1 >> a[i].y1 >> a[i].x2 >> a[i].y2;
        nenY.push_back(a[i].y1); nenY.push_back(a[i].y2);
    }

    for (int i = 1; i <= m; i++) {
        int x, y, k;
        cin >> x >> y >> k;
        muc[i] = {x, y, k};
        nenY.push_back(y);
        nenK.push_back(k);
    }

    sort(nenY.begin(), nenY.end());
    nenY.erase(unique(nenY.begin(), nenY.end()), nenY.end());

    sort(nenK.begin(), nenK.end());
    nenK.erase(unique(nenK.begin(), nenK.end()), nenK.end());

    for (int i = 1; i <= n; i++) {
        a[i].y1 = lower_bound(nenY.begin(), nenY.end(), a[i].y1) - nenY.begin() + 1;
        a[i].y2 = lower_bound(nenY.begin(), nenY.end(), a[i].y2) - nenY.begin() + 1;

        events.push_back({a[i].x1, a[i].y1, a[i].y2, 2, i, -1});
        events.push_back({a[i].x2, a[i].y1, a[i].y2, -1, i, a[i].x1});
    }

    for (int i = 1; i <= m; i++) {
        muc[i][1] = lower_bound(nenY.begin(), nenY.end(), muc[i][1]) - nenY.begin() + 1;
        muc[i][2] = lower_bound(nenK.begin(), nenK.end(), muc[i][2]) - nenK.begin() + 1;
        events.push_back({muc[i][0], muc[i][1], muc[i][1], 1, n + muc[i][2], -1});
    }

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

    DSU dsu(n);
    DSU color(n + (int)nenK.size());

    sech.resize((int)nenY.size() + 5);
    for (auto &cur : events) {
        int x = cur.x, y1 = cur.y1, y2 = cur.y2, type = cur.type;
        int id = cur.id;
        if (type == 2) {
            for (int i = y1; i <= y2; i++) {
                if (!sech[i].empty()) {
                    int j = (*sech[i].begin()).second;
                    if (dsu.ketnoi(id, j)) {
                        g[id].push_back(j);
                        g[j].push_back(id);
                    }
                }
                sech[i].insert({x, id});
            }
        }
        else if (type == 1) {
            for (int i = y1; i <= y2; i++) {
                if (!sech[i].empty()) {
                    int j = (*sech[i].begin()).second;
                    color.ketnoi(id, j);
                }
            }
        }
        else if (type == -1) {
            int pre_x = cur.pre_x;
            for (int i = y1; i <= y2; i++) {
                sech[i].erase({pre_x, id});
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            dfs(i, 0, color);
        }
    }

    for (int i = 1; i <= n; i++) {
        cout << sz[i] << '\n';
    }
    return 0;
}

• Subtask 1: 0 / 32
• Subtask 2: 0 / 32
• Subtask 3: 0 / 32
• Subtask 4: 0 / 32
• Subtask 5: 0 / 32