Submission #1061395

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061395		TheQuantiX	Fountain Parks (IOI21_parks)	C++17	30 / 100	123 ms	37944 KiB

parks

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

using namespace std;
using ll = long long;

ll n, m, q, k, x, y, a, b, c;

struct dsu {
    ll n;
    vector<ll> par;
    vector<ll> sz;
    
    dsu(ll N) : n(N) {
        par.resize(n);
        sz.resize(n);
        for (int i = 0; i < n; i++) {
            par[i] = i;
            sz[i] = 1;
        }
    }

    ll find_p(ll x) {
        if (par[x] == x) {
            return x;
        }
        ll p = find_p(par[x]);
        par[x] = p;
        return p;
    }

    void join(ll x, ll y) {
        x = find_p(x);
        y = find_p(y);
        if (x == y) {
            return;
        }
        if (sz[y] > sz[x]) {
            swap(x, y);
        }
        par[y] = x;
        sz[x] += sz[y];
    }
};

int construct_roads(vector<int> x, vector<int> y) {
    vector< vector<ll> > v(7, vector<ll> (200001, -1));
    n = x.size();
    for (int i = 0; i < n; i++) {
        v[x[i]][y[i]] = i;
    }
    dsu d(n);
    array< vector<int>, 4 > ans;
    for (int i = 2; i < 200000; i += 2) {
        if (v[2][i] != -1 && v[2][i + 2] != -1 && d.find_p(v[2][i]) != d.find_p(v[2][i + 2])) {
            d.join(v[2][i], v[2][i + 2]);
            ans[0].push_back(v[2][i]);
            ans[1].push_back(v[2][i + 2]);
            ans[2].push_back(1);
            ans[3].push_back(i + 1);
        }
        if (v[6][i] != -1 && v[6][i + 2] != -1 && d.find_p(v[6][i]) != d.find_p(v[6][i + 2])) {
            d.join(v[6][i], v[6][i + 2]);
            ans[0].push_back(v[6][i]);
            ans[1].push_back(v[6][i + 2]);
            ans[2].push_back(7);
            ans[3].push_back(i + 1);
        }
    }
    vector< pair< ll, pair<ll, ll> > > vec;
    for (int i = 2; i < 200000; i += 2) {
        if (v[4][i] != -1 && v[4][i + 2] != -1 && d.find_p(v[4][i]) != d.find_p(v[4][i + 2])) {
            d.join(v[4][i], v[4][i + 2]);
            vec.push_back({i + 1, {v[4][i], v[4][i + 2]}});
        }
    }
    for (int i = 2; i <= 200000; i += 2) {
        if (v[4][i] != -1 && v[2][i] != -1 && d.find_p(v[4][i]) != d.find_p(v[2][i])) {
            d.join(v[4][i], v[2][i]);
            vec.push_back({i, {v[4][i], v[2][i]}});
        }
        if (v[4][i] != -1 && v[6][i] != -1 && d.find_p(v[4][i]) != d.find_p(v[6][i])) {
            d.join(v[4][i], v[6][i]);
            vec.push_back({i, {v[4][i], v[6][i]}});
        }
    }
    set< pair<ll, ll> > st;
    sort(vec.begin(), vec.end());
    for (auto i : vec) {
        if (i.first % 2 == 0) {
            if (!st.count({(x[i.second.first] + x[i.second.second]) / 2, i.first - 1})) {
                st.insert({(x[i.second.first] + x[i.second.second]) / 2, i.first - 1});
                ans[0].push_back(i.second.first);
                ans[1].push_back(i.second.second);
                ans[2].push_back((x[i.second.first] + x[i.second.second]) / 2);
                ans[3].push_back(i.first - 1);
            }
            else {
                st.insert({(x[i.second.first] + x[i.second.second]) / 2, i.first + 1});
                ans[0].push_back(i.second.first);
                ans[1].push_back(i.second.second);
                ans[2].push_back((x[i.second.first] + x[i.second.second]) / 2);
                ans[3].push_back(i.first + 1);
            }
        }
        else {
            if (!st.count({(x[i.second.first] + x[i.second.second]) / 2 - 1, (y[i.second.first] + y[i.second.second]) / 2})) {
                st.insert({(x[i.second.first] + x[i.second.second]) / 2 - 1, (y[i.second.first] + y[i.second.second]) / 2});
                ans[0].push_back(i.second.first);
                ans[1].push_back(i.second.second);
                ans[2].push_back((x[i.second.first] + x[i.second.second]) / 2 - 1);
                ans[3].push_back((y[i.second.first] + y[i.second.second]) / 2);
            }
            else {
                st.insert({(x[i.second.first] + x[i.second.second]) / 2 + 1, (y[i.second.first] + y[i.second.second]) / 2});
                ans[0].push_back(i.second.first);
                ans[1].push_back(i.second.second);
                ans[2].push_back((x[i.second.first] + x[i.second.second]) / 2 + 1);
                ans[3].push_back((y[i.second.first] + y[i.second.second]) / 2);
            }
        }
    }
    if (d.sz[d.find_p(0)] != n) {
        return 0;
    }
    build(ans[0], ans[1], ans[2], ans[3]);
    return 1;
}

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