Submission #452141

#	Time	Username	Problem	Language	Result	Execution time	Memory
452141		mjhmjh1104	Fountain Parks (IOI21_parks)	C++17	100 / 100	813 ms	56116 KiB

parks

#include "parks.h"
#include <set>
#include <map>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;

int uf[200006];
 
int _find(int x) {
    if (uf[x] == -1) return x;
    return uf[x] = _find(uf[x]);
}
 
bool _merge(int x, int y) {
    x = _find(x), y = _find(y);
    if (x != y) return uf[x] = y, true;
    return false;
}

set<pair<int, int>> points;
map<pair<int, int>, int> fountains;
vector<pair<int, int>> edges, sel;

int construct_roads(vector<int> x, vector<int> y) {
    int n = (int)x.size();
    for (int i = 0; i < n; i++) uf[i] = -1;
    for (int i = 0; i < n; i++) {
        points.insert({ x[i] - 1, y[i] - 1 });
        points.insert({ x[i] - 1, y[i] + 1 });
        points.insert({ x[i] + 1, y[i] - 1 });
        points.insert({ x[i] + 1, y[i] + 1 });
        fountains[{ x[i], y[i] }] = i;
    }
    for (auto &i: points) {
        if ((i.first / 2 + i.second / 2) % 2) {
            bool pos = false;
            if (!pos && fountains.find({ i.first - 1, i.second - 1 }) != fountains.end() && fountains.find({ i.first + 1, i.second - 1 }) != fountains.end()) {
                int a = fountains[{ i.first - 1, i.second - 1 }], b = fountains[{ i.first + 1, i.second - 1 }];
                if (_merge(a, b)) {
                    edges.push_back({ a, b });
                    sel.push_back(i);
                    pos = true;
                }
            }
            if (!pos && fountains.find({ i.first - 1, i.second + 1 }) != fountains.end() && fountains.find({ i.first + 1, i.second + 1 }) != fountains.end()) {
                int a = fountains[{ i.first - 1, i.second + 1 }], b = fountains[{ i.first + 1, i.second + 1 }];
                if (_merge(a, b)) {
                    edges.push_back({ a, b });
                    sel.push_back(i);
                    pos = true;
                }
            }
        } else {
            bool pos = false;
            if (!pos && fountains.find({ i.first - 1, i.second - 1 }) != fountains.end() && fountains.find({ i.first - 1, i.second + 1 }) != fountains.end()) {
                int a = fountains[{ i.first - 1, i.second - 1 }], b = fountains[{ i.first - 1, i.second + 1 }];
                if (_merge(a, b)) {
                    edges.push_back({ a, b });
                    sel.push_back(i);
                    pos = true;
                }
            }
            if (!pos && fountains.find({ i.first + 1, i.second - 1 }) != fountains.end() && fountains.find({ i.first + 1, i.second + 1 }) != fountains.end()) {
                int a = fountains[{ i.first + 1, i.second - 1 }], b = fountains[{ i.first + 1, i.second + 1 }];
                if (_merge(a, b)) {
                    edges.push_back({ a, b });
                    sel.push_back(i);
                    pos = true;
                }
            }
        }
    }
    if ((int)edges.size() < n - 1) return 0;
    vector<int> u(n - 1), v(n - 1), a(n - 1), b(n - 1);
    for (int i = 0; i < n - 1; i++) u[i] = edges[i].first, v[i] = edges[i].second, a[i] = sel[i].first, b[i] = sel[i].second;
    build(u, v, a, 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: 30 / 30