제출 #1246387

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1246387		RecursiveCo	분수 공원 (IOI21_parks)	C++20	45 / 100	807 ms	51416 KiB

parks

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

vector<int> parent;

int find(int v) {
    if (v == parent[v]) return v;
    return parent[v] = find(parent[v]);
}

void unite(int a, int b) {
    a = find(a);
    b = find(b);
    parent[a] = b;
}

map<pair<int, int>, int> mp;

int construct_roads(vector<int> X, vector<int> Y) {
    int N = X.size();
    for (int i = 0; i < N; ++i) {
        mp[{X[i], Y[i]}] = i;
        parent.push_back(i);
    }
    for (int i = 0; i < N; ++i) {
        int x = X[i];
        int y = Y[i];
        if (mp.find({x, y + 2}) != mp.end()) unite(i, mp[{x, y + 2}]);
        if (mp.find({x, y - 2}) != mp.end()) unite(i, mp[{x, y - 2}]);
        if (mp.find({x - 2, y}) != mp.end()) unite(i, mp[{x - 2, y}]);
        if (mp.find({x + 2, y}) != mp.end()) unite(i, mp[{x + 2, y}]);
    }
    for (int i = 0; i < N; ++i) if (find(i) != find(0)) return 0;
    // assume X is 2, 4, or 6 first.
    for (int i = 0; i < N; ++i) parent[i] = i;
    vector<int> u;
    vector<int> v;
    vector<int> a;
    vector<int> b;
    set<pair<int, int>> taken;
    vector<vector<int>> by_x(200008);
    vector<vector<int>> by_y(200008);
    for (int i = 0; i < N; ++i) {
        int x = X[i];
        int y = Y[i];
        by_x[x].push_back(y);
        by_y[y].push_back(x);
    }
    for (int x = 0; x <= 200006; x += 2) {
        sort(by_x[x].begin(), by_x[x].end());
        for (int y: by_x[x]) {
            if (mp.find({x, y + 2}) != mp.end()) {
                int i = mp[{x, y}];
                int j = mp[{x, y + 2}];
                unite(i, j);
                int a_here = (x / 2 + y / 2) % 2? x - 1: x + 1;
                u.push_back(i);
                v.push_back(j);
                a.push_back(a_here);
                b.push_back(y + 1);
                taken.insert({a_here, y + 1});
            }
        }
    }
    for (int y = 200006; y >= 0; y -= 2) {
        sort(by_y[y].begin(), by_y[y].end());
        for (int x: by_y[y]) {
            if (mp.find({x + 2, y}) != mp.end()) {
                int i = mp[{x, y}];
                int j = mp[{x + 2, y}];
                if (find(i) == find(j)) continue;
                unite(i, j);
                u.push_back(i);
                v.push_back(j);
                int a_here, b_here;
                if (taken.find({x + 1, y + 1}) == taken.end()) {
                    a_here = x + 1;
                    b_here = y + 1;
                } else {
                    a_here = x + 1;
                    b_here = y - 1;
                }
                a.push_back(a_here);
                b.push_back(b_here);
                taken.insert({a_here, b_here});
            }
        }
    }
    build(u, v, a, b);
    return 1;
}

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