Submission #1061707

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061707		Ignut	Fountain Parks (IOI21_parks)	C++17	45 / 100	1096 ms	67248 KiB

parks

/* Ignut
started: 16.08.2024
now: 16.08.2024
████████████████████████████████████████████████████████████████████
████████████████████████████████    ████████████████████████████████
██████████████████████████████        ██████████████████████████████
██████      ██████████████████        ██████████████████      ██████
██████          ██████████████        ██████████████          ██████
██████      ██    ████████████        ████████████    ██      ██████
██████      ████    ██████████        ██████████    ████      ██████
██████      ████      ██████████    ██████████      ████      ██████
██████      ████      ██████████    ██████████    ██████      ██████
██████      ██████    ██████████    ██████████    ██████      ██████
██████      ██████    ████████        ████████    ██████      ██████
██████      ██████      ██████        ██████      ██████      ██████
██████      ████        ████            ████        ████      ██████
██████            ██████████    ████    ██████████            ██████
██████      ██      ██████    ████████    ██████      ██      ██████
██████      ██████            ████████            ██████      ██████
██████                    ██            ██                    ██████
██████████████████████      ████    ████      ██████████████████████
████████████████████████      ██    ██      ████████████████████████
██████████████████████████                ██████████████████████████
██████████████████████████████        ██████████████████████████████
████████████████████████████████████████████████████████████████████
*/

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

void build(vector<int> u, vector<int> v, vector<int> a, vector<int> b);

struct DSU {
    int cntComp;
    vector<int> p, sz;
    void Init(int n) {
        cntComp = n;
        p.assign(n, 0);
        iota(p.begin(), p.end(), 0);
        sz.assign(n, 1);
    }
    int Get(int v) {
        return p[v] == v ? v : p[v] = Get(p[v]);
    }
    void Unite(int u, int v) {
        u = Get(u), v = Get(v);
        if (u == v) return;
        cntComp --;
        if (sz[u] > sz[v]) swap(u, v);
        p[u] = v;
        sz[v] += sz[u];
    }
};

int construct_roads(vector<int> x, vector<int> y) {
    int n = x.size();
    map<pair<int, int>, int> mp;
    for (int i = 0; i < n; i ++) mp[{x[i], y[i]}] = i + 1;

    DSU dsu; dsu.Init(n);
    vector<int> u, v, a, b;
    map<tuple<int, int, int, int>, int> have;
    auto MakeEdge = [&u, &v, &dsu, &x, &y, &have](int i, int j) -> void {
        u.push_back(i);
        v.push_back(j);
        dsu.Unite(i, j);
        have[{x[i], y[i], x[j], y[j]}] ++;
        have[{x[j], y[j], x[i], y[j]}] ++;
    };
    for (int i = 0; i < n; i ++) {
        if (mp.count({x[i] + 2, y[i]})) {
            int j = mp[{x[i] + 2, y[i]}] - 1;
            if (dsu.Get(i) != dsu.Get(j))
                MakeEdge(i, j);
        }
        if (mp.count({x[i], y[i] + 2})) {
            int j = mp[{x[i], y[i] + 2}] - 1;
            if (dsu.Get(i) != dsu.Get(j))
                MakeEdge(i, j);
        }
    }
    if (dsu.cntComp > 1) return 0;

    a.assign(n - 1, 0), b.assign(n - 1, 0);

    map<tuple<int, int, int, int>, pair<int, int>> res;
    for (int i = 0; i < u.size(); i ++) {
        if (res.count({x[u[i]], y[u[i]], x[v[i]], y[v[i]]})) {
            auto [xx, yy] = res[{x[u[i]], y[u[i]], x[v[i]], y[v[i]]}];
            a[i] = xx, b[i] = yy;
            continue;
        }
        if (res.count({x[v[i]], y[v[i]], x[u[i]], y[u[i]]})) {
            auto [xx, yy] = res[{x[v[i]], y[v[i]], x[u[i]], y[u[i]]}];
            a[i] = xx, b[i] = yy;
            continue;
        }

        int x1 = x[u[i]], y1 = y[u[i]], x2 = x[v[i]], y2 = y[v[i]];
        int xf, yf;
        if (x1 == x2) xf = x1 - 1;
        else xf = (x1 + x2) / 2;
        if (y1 == y2) yf = y1 - 1;
        else yf = (y1 + y2) / 2;

        a[i] = xf, b[i] = yf;

        auto Try = [&x1, &y1, &x2, &y2, &xf, &yf, &have, &res](int xx1, int yy1, int xx2, int yy2, int dxf, int dyf) -> bool {
            if (res.count({xx1, yy1, xx2, yy2})) return false;
            if (res.count({xx2, yy2, xx1, yy1})) return false;
            if (have.count({xx1, yy1, xx2, yy2})) {
                x1 = xx1, y1 = yy1, x2 = xx2, y2 = yy2;
                xf += dxf;
                yf += dyf;
                return true;
            }
            return false;
        };

        while (true) {
            res[{x1, y1, x2, y2}] = {xf, yf};

            if (x1 == x2) {
                if (xf < x1) {
                    if (Try(x1 - 2, y2, x1, y2, 0, +2)) continue;
                    if (Try(x1 - 2, y1, x1 - 2, y2, -2, 0)) continue;
                    if (Try(x1 - 2, y1, x1, y1, 0, -2)) continue;
                }
                else {
                    if (Try(x1, y2, x1 + 2, y2, 0, +2)) continue;
                    if (Try(x1 + 2, y1, x1 + 1, y2, +2, 0)) continue;
                    if (Try(x1, y1, x1 + 2, y1, 0, -2)) continue;
                }
            }
            else {
                if (yf > y1) {
                    if (Try(x1, y1, x1, y1 + 2, -2, 0)) continue;
                    if (Try(x1, y1 + 2, x2, y1 + 2, 0, +2)) continue;
                    if (Try(x2, y2, x2, y2 + 2, +2, 0)) continue;
                }
                else {
                    if (Try(x1, y1 - 2, x1, y1, -2, 0)) continue;
                    if (Try(x1, y1 - 2, x2, y1 - 2, 0, -2)) continue;
                    if (Try(x2, y1 - 2, x2, y2, +2, 0)) continue;
                }
            }
            break;
        }
    }
    build(u, v, a, b);
    return 1;
}

Compilation message (stderr)

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:89:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     for (int i = 0; i < u.size(); i ++) {
      |                     ~~^~~~~~~~~~

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