Submission #1058936

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058936		RaresFelix	Fountain Parks (IOI21_parks)	C++17	100 / 100	661 ms	61736 KiB

parks

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

using namespace std;

using vi = vector<int>;
using ii = pair<int, int>;

int DX[] = {-1, 0, 1, 0};
int DY[] = {0, 1, 0, -1};
const int MV = 1e9;

struct DSU {
    int nrc;
    vi e;
    DSU(int n) : nrc(n), e(n, -1) {}

    int repr(int u) {
        while(e[u] >= 0) u = e[u];
        return u;
    }

    void join(int u, int v) {
        u = repr(u); v = repr(v);
        if(u == v) return;
        if(e[u] >= e[v]) swap(u, v);
        e[u] += e[v];
        e[v] = u;
        --nrc;
    }
};

int construct_roads(vi x, vi y) {
    auto get_bench_coord = [&](int u, int v) -> pair<ii, ii> {
        int xcm = (x[u] + x[v]) / 2, ycm = (y[u] + y[v]) / 2;
        int dx = 2 - abs(x[u] - x[v]), dy = 2 - abs(y[u] - y[v]);
        return make_pair(ii{xcm - dx / 2, ycm - dy / 2}, ii{xcm + dx / 2, ycm + dy / 2});
    };
    int n = x.size();

    vector<ii> B;
    map<ii, int> Id;

    for(int i = 0; i < n; ++i) 
        Id[ii{x[i], y[i]}] = i;

    for(int i = 0; i < n; ++i) {
        for(int d = 0; d < 4; ++d) {
            int nx = x[i] + 2 * DX[d], ny = y[i] + 2 * DY[d];
            if(Id.count({nx, ny})) {
                int u = Id[{nx, ny}];
                auto [a, b] = get_bench_coord(u, i);
                B.push_back(a);
                B.push_back(b);
            }
        }
    }
    sort(B.begin(), B.end());
    B.resize(unique(B.begin(), B.end()) - B.begin());
    map<ii, int> IdB;
    int m = B.size();
    for(int i = 0; i < m; ++i) {
        IdB[B[i]] = i;
    }
    vi U, V, RA, RB;
    DSU Sol(n);
    auto leaga = [&](int x, int y, int x1, int y1, int x2, int y2) -> bool {
        if(Id.count({x1, y1}) && Id.count({x2, y2})) {
            int u = Id[{x1, y1}], v = Id[{x2, y2}];
            U.push_back(u);
            V.push_back(v);
            RA.push_back(x);
            RB.push_back(y);
            Sol.join(u, v);
            return true;
        }
        return false;
    };
    for(int i = 0; i < m; ++i) {
        auto [x, y] = B[i];
        int tip = ((((x + MV) / 2) & 1) + (((y + MV) / 2) & 1)) % 2;
        if(tip) {
            //leg la ceva vertical
            leaga(x, y, x + 1, y - 1, x + 1, y + 1) ||
            leaga(x, y, x - 1, y - 1, x - 1, y + 1);
        } else {
            //leg la ceva orizontal
            leaga(x, y, x - 1, y + 1, x + 1, y + 1) ||
            leaga(x, y, x - 1, y - 1, x + 1, y - 1);
        }
    }
    if(Sol.nrc != 1) return 0;
    build(U, V, RA, RB);
    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