Submission #593782

#	Time	Username	Problem	Language	Result	Execution time	Memory
593782		SlavicG	Fountain Parks (IOI21_parks)	C++17	5 / 100	247 ms	30520 KiB

parks

#include "parks.h"
#include "bits/stdc++.h"
using namespace std;

#define         sz(a)     (int)a.size()
#define        all(a)     a.begin(),a.end()
#define    forn(i, n)     for(int i = 0; i < n; ++i)

const int N = 2e5 + 10;
int p[N];
int get(int a) {
    return p[a] = (a == p[a] ? a : get(p[a]));
}
bool uni(int a, int b) {
    a = get(a), b = get(b);
    if(a == b) return false;
    p[a] = b;
    return true;
}

int construct_roads(vector<int> x, vector<int> y) {
    forn(i, N) p[i] = i;
    if (x.size() == 1) {
        build({}, {}, {}, {});
        return 1;
    }
    vector<int> u, v, a, b;
    vector<pair<int, int>> points;
    map<pair<int, int>, int> idx;
    vector<int> bruh[N];
    for(int i = 0; i < sz(x); ++i) {
        bruh[y[i]].push_back(i);
        idx[{x[i], y[i]}] = i;
        points.push_back({x[i], y[i]});
    }
    sort(all(points));
    for(int i = 0; i + 1 < sz(points); ++i) {
        if(points[i].first == points[i + 1].first) {
            if(points[i].second + 2 != points[i + 1].second) continue;
            if(points[i].first == 2 && uni(idx[points[i]], idx[points[i + 1]])) {
                u.push_back(idx[points[i]]), v.push_back(idx[points[i + 1]]);
                a.push_back(points[i].first - 1);
                b.push_back(points[i].second + 1);
            } else if(points[i].first == 4 && uni(idx[points[i]], idx[points[i + 1]])) {
                u.push_back(idx[points[i]]), v.push_back(idx[points[i + 1]]);
                a.push_back(points[i].first + 1);
                b.push_back(points[i].second + 1);
            }
        }
    }
    for(auto v: bruh) {
        if(sz(v) == 2) {
            if(uni(v[0], v[1])) {
                u.push_back(v[0]);
                u.push_back(v[1]);
                a.push_back(3);
                b.push_back(y[v[0]] - 1);
            }
        }
    }
    for(int i = 1; i < sz(x); ++i) {
        if(get(i) != get(0)) return 0;
    }
    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