Submission #1050560

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050560		Zicrus	Fountain Parks (IOI21_parks)	C++17	15 / 100	206 ms	50164 KiB

parks

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

typedef long long ll;

ll n;

vector<ll> lnk;
vector<ll> sz;

ll find(ll a) {
    if (a != lnk[a]) lnk[a] = find(lnk[a]);
    return lnk[a];
}

bool unite(ll a, ll b) {
    a = find(a); b = find(b);
    if (a == b) return false;
    if (sz[a] > sz[b]) swap(a, b);
    lnk[a] = b;
    sz[b] += sz[a];
    return true;
}

int construct_roads(vector<int> x, vector<int> y) {
    n = x.size();
    lnk = vector<ll>(n);
    sz = vector<ll>(n, 1);
    for (int i = 0; i < n; i++) lnk[i] = i;
    unordered_map<ll, ll> pts;
    vector<pair<ll, ll>> edges;
    unordered_set<ll> hasEdge;
    for (int i = 0; i < n; i++) {
        ll hash = ((ll)x[i] << 31) | (ll)y[i];
        pts[hash] = i;
    }
    for (ll i = 0; i < n; i++) {
        ll hashL = (((ll)x[i]-2) << 31) | ((ll)y[i]);
        if (pts.count(hashL)) {
            ll hash = (min(i, pts[hashL]) << 31) | max(i, pts[hashL]);
            if (!hasEdge.count(hash)) {
                edges.push_back({i, pts[hashL]});
                hasEdge.insert(hash);
            }
        }
        ll hashR = (((ll)x[i]+2) << 31) | ((ll)y[i]);
        if (pts.count(hashR)) {
            ll hash = (min(i, pts[hashR]) << 31) | max(i, pts[hashR]);
            if (!hasEdge.count(hash)) {
                edges.push_back({i, pts[hashR]});
                hasEdge.insert(hash);
            }
        }
        ll hashD = (((ll)x[i]) << 31) | ((ll)y[i]-2);
        if (pts.count(hashD)) {
            ll hash = (min(i, pts[hashD]) << 31) | max(i, pts[hashD]);
            if (!hasEdge.count(hash)) {
                edges.push_back({i, pts[hashD]});
                hasEdge.insert(hash);
            }
        }
        ll hashU = (((ll)x[i]) << 31) | ((ll)y[i]+2);
        if (pts.count(hashU)) {
            ll hash = (min(i, pts[hashU]) << 31) | max(i, pts[hashU]);
            if (!hasEdge.count(hash)) {
                edges.push_back({i, pts[hashU]});
                hasEdge.insert(hash);
            }
        }
    }

    vector<int> u, v, a, b;
    for (auto &e : edges) {
        unite(e.first, e.second);
        u.push_back(e.first);
        v.push_back(e.second);
        if (x[e.first] == 2 && x[e.second] == 2) {
            a.push_back(1);
            b.push_back((y[e.first] + y[e.second]) / 2);
        }
        else if (x[e.first] == 4 && x[e.second] == 4) {
            a.push_back(5);
            b.push_back((y[e.first] + y[e.second]) / 2);
        }
        else {
            a.push_back(3);
            b.push_back(y[e.first] + 1);
        }
    }

    if (sz[find(0)] < n) return 0;

    build(u, v, a, b);
    return 1;
}

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