제출 #1213369

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1213369		omsincoconut	분수 공원 (IOI21_parks)	C++17	70 / 100	1737 ms	226440 KiB

parks

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

using namespace std;

struct DSU{
    vector<int> p, sz;

    void init(int n) {
        sz = vector<int>(n, 1);
        p = vector<int>(n);
        iota(p.begin(), p.end(), 0);
    }

    int find_set(int u) {
        return u == p[u] ? u : p[u] = find_set(p[u]);
    }

    bool merge_set(int u, int v) {
        u = find_set(u);
        v = find_set(v);
        if (u == v) return false;
        if (sz[u] < sz[v]) swap(u, v);
        p[v] = u;
        sz[u] += sz[v];
        return true;
    }
} dsu;

vector<int> x, y;
map<pair<int, int>, int> pos_idx;
map<pair<int, int>, int> edge_side;
set<pair<int, int>> vis;
set<pair<int, int>> bench_used;
vector<int> ret_u, ret_v, ret_a, ret_b;

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

void dfs(int u, int ent) {
    int xu = x[u], yu = y[u];

    for (int id = 0; id < 4; id++) {
        int i = (ent+id+1)%4;
        int xv = x[u] + 2*dx[i], yv = y[u] + 2*dy[i];
        if (!pos_idx.count({xv, yv})) continue;
        int v = pos_idx[{xv, yv}];

        if (vis.count({u, v})) continue;

        if (dsu.find_set(u) == dsu.find_set(v)) {
            vis.insert({u, v});
            dfs(v, i);
            continue;
        }

        int bx, by;

        if (dx[i] == 1) {
            bx = xu + dx[i];
            by = yu + 1;
        } else if (dx[i] == -1) {
            bx = xu + dx[i];
            by = yu - 1;
        } else if (dy[i] == 1) {
            bx = xu - 1;
            by = yu + dy[i];
        } else if (dy[i] == -1) {
            bx = xu + 1;
            by = yu + dy[i];
        }

        if (!bench_used.count({bx, by})) {
            ret_u.push_back(u);
            ret_v.push_back(v);
            ret_a.push_back(bx);
            ret_b.push_back(by);
            bench_used.insert({bx, by});
            dsu.merge_set(u, v);
        }

        vis.insert({u, v});
        dfs(v, i);
    }
}

int construct_roads(vector<int> _x, vector<int> _y) {
    x = _x; y = _y;
    int n = x.size();
    dsu.init(n);
    for (int i = 0; i < n; i++) pos_idx[{x[i], y[i]}] = i;

    int start = 0;
    for (int i = 0; i < n; i++) {
        if (make_pair(y[i], -x[i]) > make_pair(y[start], -x[start])) start = i;
    }

    dfs(start, 0);

    // Check connectivity
    vector<vector<int>> edge_used(n, vector<int>());
    for (int i = 0; i < ret_u.size(); i++) {
        edge_used[ret_u[i]].push_back(ret_v[i]);
        edge_used[ret_v[i]].push_back(ret_u[i]);
    }

    vector<bool> visited(n);
    queue<int> bfs;
    bfs.push(0);
    while (!bfs.empty()) {
        int u = bfs.front();
        bfs.pop();
        if (visited[u]) continue;
        visited[u] = true;

        for (int v : edge_used[u]) bfs.push(v);
    }

    for (int i = 0; i < n; i++) if (!visited[i]) return 0;

    build(ret_u, ret_v, ret_a, ret_b);
    return 1;
}

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