Submission #1061576

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061576		TheQuantiX	Fountain Parks (IOI21_parks)	C++17	30 / 100	3594 ms	114384 KiB

parks

#include<bits/stdc++.h>
#include "parks.h"
#pragma GCC optimize("O3,unroll-loops")

using namespace std;
using ll = int;

ll n, m, q, k, x, y, a, b, c;
unordered_map< long long, vector< pair< pair<ll, ll>, pair<ll, ll> > > > G;
vector< pair< pair<ll, ll>, pair<ll, ll> > > prs;

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];
    }
};

long long hsh(pair<ll, ll> p) {
    return p.first * 10000000LL + p.second;
}

long long hsh(pair< pair<ll, ll>, pair<ll, ll> > p) {
    return (p.first.first * 10000000LL + p.first.second) + (10000000LL * 10000000LL * (p.first > p.second));
}

void dfs(pair< pair<ll, ll>, pair<ll, ll> > x, unordered_set<long long> &mp, vector< pair< pair<ll, ll>, pair<ll, ll> > > &mp1) {
    // cout << x.first.first << ' ';
    // cout << x.first.second << '\t';
    // cout << x.second.first << ' ';
    // cout << x.second.second << '\n';
    mp.insert(hsh(x));
    mp1.push_back(x);
    for (auto i : G[hsh(x)]) {
        if (!mp.count(hsh(i.first))) {
            dfs(i, mp, mp1);
        }
    }
}

int construct_roads(vector<int> x, vector<int> y) {
    n = x.size();
    array< vector<int>, 4 > ans;
    map< pair<ll, ll>, ll > pts;
    for (int i = 0; i < n; i++) {
        pts[{x[i], y[i]}] = i;
    }
    dsu d(n);
    map< pair<ll, ll>, vector< pair<ll, ll> > > vec;
    for (int i = 0; i < n; i++) {
        if (pts.count({x[i], y[i] - 2}) && d.find_p(i) != d.find_p(pts[{x[i], y[i] - 2}])) {
            d.join(i, pts[{x[i], y[i] - 2}]);
            vec[{x[i] - 1, y[i] - 1}].push_back({x[i], y[i] - 1});
            vec[{x[i] + 1, y[i] - 1}].push_back({x[i], y[i] - 1});
        }
        if (pts.count({x[i], y[i] + 2}) && d.find_p(i) != d.find_p(pts[{x[i], y[i] + 2}])) {
            d.join(i, pts[{x[i], y[i] + 2}]);
            vec[{x[i] - 1, y[i] + 1}].push_back({x[i], y[i] + 1});
            vec[{x[i] + 1, y[i] + 1}].push_back({x[i], y[i] + 1});
        }
    }
    for (int i = 0; i < n; i++) {
        if (pts.count({x[i] - 2, y[i]}) && d.find_p(i) != d.find_p(pts[{x[i] - 2, y[i]}])) {
            d.join(i, pts[{x[i] - 2, y[i]}]);
            vec[{x[i] - 1, y[i] + 1}].push_back({x[i] - 1, y[i]});
            vec[{x[i] - 1, y[i] - 1}].push_back({x[i] - 1, y[i]});
        }
        if (pts.count({x[i] + 2, y[i]}) && d.find_p(i) != d.find_p(pts[{x[i] + 2, y[i]}])) {
            d.join(i, pts[{x[i] + 2, y[i]}]);
            vec[{x[i] + 1, y[i] + 1}].push_back({x[i] + 1, y[i]});
            vec[{x[i] + 1, y[i] - 1}].push_back({x[i] + 1, y[i]});
        }
    }
    if (d.sz[d.find_p(0)] != n) {
        return 0;
    }
    for (auto &i : vec) {
        // cout << i.first.first << ' ' << i.first.second << '\n';
        for (auto j : i.second) {
            prs.push_back({j, i.first});
            // cout << '\t' << j.first << ' ' << j.second << '\n';
            for (auto k : i.second) {
                if (j != k) {
                    G[hsh({j, i.first})].push_back({k, {k.first + (k.first - i.first.first), k.second + (k.second - i.first.second)}});
                    // cout << "\t\t" << k.first + (k.first - i.first.first) << ' ' << k.second + (k.second - i.first.second) << '\n';
                }
            }
        }
    }
    unordered_set<long long> mp;
    for (auto i : prs) {
        // cout << i.first.first.first << ' ' << i.first.first.second << '\n';
        if (mp.count(hsh(i.first))) {
            continue;
        }
        unordered_set<long long> mp2;
        vector< pair< pair<ll, ll>, pair<ll, ll> > > mp1;
        dfs(i, mp2, mp1);
        for (auto j : mp1) {
            if (mp.count(hsh(j.first))) {
                continue;
            }
            if (j.first.first % 2 == 0) {
                ans[0].push_back(pts[{j.first.first, j.first.second - 1}]);
                ans[1].push_back(pts[{j.first.first, j.first.second + 1}]);
            }
            else {
                ans[0].push_back(pts[{j.first.first - 1, j.first.second}]);
                ans[1].push_back(pts[{j.first.first + 1, j.first.second}]);
            }
            ans[2].push_back(j.second.first);
            ans[3].push_back(j.second.second);
            mp.insert(hsh(j.first));
        }
    }
    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