Submission #1246356

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246356		RecursiveCo	분수 공원 (IOI21_parks)	C++20	5 / 100	539 ms	26824 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;
    bool side = false; // false = left, true = right
    set<pair<int, int>> taken;
    for (int i = 0; i < N; ++i) {
        int x = X[i];
        int y = Y[i];
        if (mp.find({x, y - 2}) != mp.end()) {
            int j = mp[{x, y - 2}];
            unite(i, j);
            int a_here;
            if (x == 2) a_here = 1;
            else if (x == 6) a_here = 7;
            else {
                a_here = side? 5: 3;
                side = !side;
            }
            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) {
        for (int x = 2; x <= 4; x += 2) {
            if (mp.find({x, y}) != mp.end() && 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: 0 / 20
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30