제출 #1172268

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1172268		gyg	분수 공원 (IOI21_parks)	C++20	5 / 100	1259 ms	129008 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
#define arr array 
#define vec vector
#define pii pair<int, int>
#define fir first 
#define sec second
const int N = 2e5 + 5, INF = 1e9;

int n;
arr<pii, N> ps;
map<pii, int> id;

vec<pii> edg;
void edg_cmp() {
    for (int u = 1; u <= n; u++) {
        vec<pii> dlt = {{-2, 0}, {2, 0}, {0, -2}, {0, 2}};
        for (pii x : dlt) {
            int a = ps[u].fir + x.fir, b = ps[u].sec + x.sec;
            if (!id[{a, b}]) continue;
            edg.push_back({u, id[{a, b}]});
        }
    }
}

struct Dsj {
    arr<int, N> prnt, sz;
    void intl() {
        for (int u = 1; u <= n; u++)
            prnt[u] = u, sz[u] = 1;
    }
    int pr(int u) {
        return (prnt[u] == u) ? u : prnt[u] = pr(prnt[u]);
    }
    bool mrg(int u, int v) {
        u = pr(u), v = pr(v);
        if (u == v) return false;
        prnt[v] = u, sz[u] += sz[v];
        return true;
    }
} dsj;
vec<pii> usd;
void usd_cmp() {
    dsj.intl();
    for (pii x : edg) {
        int u = x.fir, v = x.sec;
        if (!dsj.mrg(u, v)) continue;
        usd.push_back(x);
    }
}

map<pii, int> sd_id;
vec<pii> sd;
arr<set<int>, N> usd_adj, sd_adj;
void sd_cmp() {
    for (int i = 0; i < usd.size(); i++) {
        int u = usd[i].fir, v = usd[i].sec;
        if (ps[u] > ps[v]) swap(u, v);  
        
        vec<pii> nw;
        if (ps[u].fir == ps[v].fir) {
            nw.push_back({ps[u].fir - 1, ps[u].sec + 1});
            nw.push_back({ps[u].fir + 1, ps[u].sec + 1});
        } else {
            nw.push_back({ps[u].fir + 1, ps[u].sec - 1});
            nw.push_back({ps[u].fir + 1, ps[u].sec + 1});
        }

        for (pii y : nw) {
            if (!sd_id.count(y)) {
                int j = sd_id.size();
                sd_id[y] = j;
                sd.push_back(y);
            }
            usd_adj[i].insert(sd_id[y]);
            sd_adj[sd_id[y]].insert(i);
        }
    }

    // for (pii x : usd) cout << x.fir << " " << x.sec << '\n';
    // cout << '\n';
    // for (pii x : sd) cout << x.fir << " " << x.sec << '\n';
    // cout << '\n';
}

set<pii> ord;
vec<pii> cpl;
void cpl_cmp() {
    for (int u = 0; u < sd.size(); u++) 
        ord.insert({sd_adj[u].size(), u});

    while (ord.size()) {
        int u = ord.begin()->sec; ord.erase(ord.begin());
        // cout << u << '\n';
        if (sd_adj[u].empty()) continue;

        int v = *sd_adj[u].begin();
        cpl.push_back({v, u});
        for (int w : usd_adj[v]) {
            if (!ord.count({sd_adj[w].size(), w})) continue;
            ord.erase({sd_adj[w].size(), w});
            sd_adj[w].erase(v);
            ord.insert({sd_adj[w].size(), w});
        }
    }

    // while (true) {
    //     int mn = INF;
    //     for (int u = 0; u < sd.size(); u++) {
    //         if (sd_adj[u].empty()) continue;
    //         mn = min(mn, (int) sd_adj[u].size());
    //     }
    //     if (mn == INF) break;

    //     for (int u = 0; u < sd.size(); u++) {
    //         if (sd_adj[u].size() != mn) continue;
    //         int v = *sd_adj[u].begin();
    //         cpl.push_back({v, u});
    //         sd_adj[u].clear();
    //         for (int w : usd_adj[v])
    //             sd_adj[w].erase(v);
    //         break;
    //     }
    // }

    // for (pii x : cpl) cout << x.fir << " " << x.sec << '\n';
}

int construct_roads(vec<int> _x, vec<int> _y) {
    n = _x.size();
    for (int u = 1; u <= n; u++) {
        ps[u] = {_x[u - 1], _y[u - 1]};
        id[ps[u]] = u;
    }

    edg_cmp();
    usd_cmp();
    if (dsj.sz[dsj.pr(1)] != n) return 0;
    sd_cmp();
    cpl_cmp();
    if (cpl.size() != n - 1) return 0;

    vec<int> a, b, c, d;
    for (pii x : cpl) {
        int u = x.fir, v = x.sec;
        a.push_back(usd[u].fir - 1);
        b.push_back(usd[u].sec - 1);
        c.push_back(sd[v].fir);
        d.push_back(sd[v].sec);
    }
    build(a, b, c, d);
    return 1;
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30