Submission #441816

#	Time	Username	Problem	Language	Result	Execution time	Memory
441816		baluteshih	Fountain Parks (IOI21_parks)	C++17	70 / 100	591 ms	51088 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define pb push_back
#define ALL(v) v.begin(), v.end()
#define SZ(a) ((int)a.size())

pii operator+(const pii &a, const pii &b) { return pii(a.X + b.X, a.Y + b.Y); }
pii operator-(const pii &a, const pii &b) { return pii(a.X - b.X, a.Y - b.Y); }

vector<int> dt[200005];
int boss[200005], conn;
int vis[200005];
map<pii, int> id, chair;

int finds(int x) {
    if (x == boss[x]) return x;
    return boss[x] = finds(boss[x]);
}

bool Union(int x, int y) {
    x = finds(x), y = finds(y);
    if (x == y) return 0;
    boss[x] = y, --conn;
    return 1;
}

vector<int> u, v, a, b, gx, gy;

int goaway(pii p) {
    auto q = chair.find(p);
    if (q == chair.end())
        return 1;
    if (vis[q->Y])
        return 0;
    vis[q->Y] = 1;
    if (gx[u[q->Y]] == gx[v[q->Y]]) {
        pii d = q->X - pii(gx[u[q->Y]], gy[u[q->Y]]);
        d.X *= -1;
        if (!goaway(pii(gx[u[q->Y]], gy[u[q->Y]]) + d))
            return 0;
        a[q->Y] = gx[u[q->Y]] + d.X;
        b[q->Y] = gy[u[q->Y]] + d.Y;
        chair[pii(a[q->Y], b[q->Y])] = q->Y;
    }
    else {
        pii d = q->X - pii(gx[u[q->Y]], gy[u[q->Y]]);
        d.Y *= -1;
        if (!goaway(pii(gx[u[q->Y]], gy[u[q->Y]]) + d))
            return 0;
        a[q->Y] = gx[u[q->Y]] + d.X;
        b[q->Y] = gy[u[q->Y]] + d.Y;
        chair[pii(a[q->Y], b[q->Y])] = q->Y;
    }
    return 1;
}

int construct_roads(vector<int> x, vector<int> y) {
    gx = x, gy = y;
    if (x.size() == 1) {
	    build({}, {}, {}, {});
        return 1;
    }
    int n = SZ(x);
    conn = n;
    iota(boss, boss + n, 0);
    int L = *min_element(ALL(y));
    int R = *max_element(ALL(y));
    for (int i = 0; i < n; ++i) {
        dt[y[i]].pb(i);
        id[pii(x[i], y[i])] = i;
    }
    for (int i = L; i <= R; i += 2) {
        if (dt[i].empty())
            return 0;
        sort(ALL(dt[i]), [&](int p, int q){ return x[p] < x[q]; });
    }
    for (int i = L; i <= R; i += 2) {
        for (int p : dt[i]) {

            auto q = id.find(pii(x[p], y[p]) + pii(2, 0));
            if (q != id.end() && finds(p) != finds(q->Y)) {
                Union(p, q->Y);
                if (chair.find(pii(x[p], y[p]) + pii(1, -1)) == chair.end()) {
                    chair[pii(x[p], y[p]) + pii(1, -1)] = SZ(u);
                    u.pb(p), v.pb(q->Y);
                    a.pb(x[p] + 1);
                    b.pb(y[p] - 1);
                }
                else {
                    assert(goaway(pii(x[p], y[p]) + pii(1, 1)));
                    chair[pii(x[p], y[p]) + pii(1, 1)] = SZ(u);
                    u.pb(p), v.pb(q->Y);
                    a.pb(x[p] + 1);
                    b.pb(y[p] + 1);
                }
            }

            q = id.find(pii(x[p], y[p]) + pii(0, 2));
            if (q != id.end() && finds(p) != finds(q->Y)) {
                Union(p, q->Y);
                if (chair.find(pii(x[p], y[p]) + pii(-1, 1)) == chair.end()) {
                    chair[pii(x[p], y[p]) + pii(-1, 1)] = SZ(u);
                    u.pb(p), v.pb(q->Y);
                    a.pb(x[p] - 1);
                    b.pb(y[p] + 1);
                }
                else {
                    assert(goaway(pii(x[p], y[p]) + pii(1, 1)));
                    chair[pii(x[p], y[p]) + pii(1, 1)] = SZ(u);
                    u.pb(p), v.pb(q->Y);
                    a.pb(x[p] + 1);
                    b.pb(y[p] + 1);
                }
            }
        }
    }
    
    if (conn != 1)
        return 0;
    build(u, v, a, b);
    return 1;
}

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