Submission #1061449

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061449		Ignut	Fountain Parks (IOI21_parks)	C++17	0 / 100	1 ms	348 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;
    auto MakeEdge = [&u, &v, &a, &b, &dsu, &x, &y](int i, int j) -> void {
        u.push_back(i);
        v.push_back(j);
        dsu.Unite(i, j);
        int X;
        if (x[i] == 2 && x[j] == 2) X = 1;
        else if (x[i] == 4 && x[j] == 4) X = 5;
        else X = 3;
        int Y;
        if (y[i] == y[j]) Y = y[i] - 1;
        else Y = (y[i] + y[j]) / 2;
        a.push_back(X);
        b.push_back(Y);
    };
    for (int i = 0; i < n; i ++) {
        if (mp.count({x[i] + 2, y[i]})) {
            MakeEdge(i, mp[{x[i] + 2, y[i]}]);
        }
        if (mp.count({x[i], y[i] + 2})) {
            MakeEdge(i, mp[{x[i], y[i] + 2}]);
        }
    }
    if (dsu.cntComp > 1) return 0;
    build(u, v, a, b);
    return 1;
}

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