Submission #559942

#	Time	Username	Problem	Language	Result	Execution time	Memory
559942		nghiass001	Fountain Parks (IOI21_parks)	C++17	100 / 100	381 ms	37316 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
#define FOR(i,l,r) for(int i=(l); i<=(r); ++i)
#define REP(i,l,r) for(int i=(l); i<(r); ++i)
#define FORD(i,r,l) for(int i=(r); i>=(l); --i)
#define REPD(i,r,l) for(int i=(r)-1; i>=(l); --i)
using namespace std;
const int N = 2e5 + 5;
int component, a[N], dsu[N];
map<int, int> M[N];
vector<int> px, py;
vector<int> edgex, edgey, pointx, pointy;

int getD(int u) {
    return dsu[u] < 0 ? u : dsu[u] = getD(dsu[u]);
}

void add(int u, int v, int chair_x, int chair_y) {
    int pu = getD(u);
    int pv = getD(v);
    if (pu == pv) return;
    edgex.push_back(u);
    edgey.push_back(v);
    pointx.push_back(chair_x);
    pointy.push_back(chair_y);
    if (dsu[pu] > dsu[pv]) swap(pu, pv);
    dsu[pu] += dsu[pv];
    dsu[pv] = pu;
    --component;
}

int construct_roads(vector<int> xxx, vector<int> yyy) {
    px = xxx; py = yyy;
    int n = component = px.size();
    REP(i, 0, n) dsu[i] = -1;
    REP(i, 0, n) M[px[i]][py[i]] = i;

    REP(i, 0, n) if ((px[i] + py[i]) & 2) {
        if (M[px[i]].count(py[i] + 2))
            add(i, M[px[i]][py[i] + 2], px[i] - 1, py[i] + 1);
        if (M[px[i] + 2].count(py[i]))
            add(i, M[px[i] + 2][py[i]], px[i] + 1, py[i] + 1);
    }

    REP(i, 0, n) if (!((px[i] + py[i]) & 2)) {
        if (M[px[i]].count(py[i] + 2)) {
            if (!(M[px[i] + 2].count(py[i]) && M[px[i] + 2].count(py[i] + 2)))
                add(i, M[px[i]][py[i] + 2], px[i] + 1, py[i] + 1);
        }
        if (M[px[i] + 2].count(py[i])) {
            if (!(M[px[i]].count(py[i] - 2) && M[px[i] + 2].count(py[i] - 2)))
                add(i, M[px[i] + 2][py[i]], px[i] + 1, py[i] - 1);
        }
    }

    if (component != 1) return 0;

    build(edgex, edgey, pointx, pointy);
    return 1;
}

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