Submission #1172259

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172259		gyg	Fountain Parks (IOI21_parks)	C++20	15 / 100	702 ms	64828 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
#define arr array 
#define vec vector
#define pii pair<int, int>
#define fir first 
#define sec second
const int N = 2e5 + 5;

int n;
arr<pii, N> ps;
map<pii, int> id;

vec<pii> edg;
void edg_cmp() {
    for (int u = 1; u <= n; u++) {
        vec<pii> dlt = {{-2, 0}, {2, 0}, {0, -2}, {0, 2}};
        for (pii x : dlt) {
            int a = ps[u].fir + x.fir, b = ps[u].sec + x.sec;
            if (!id[{a, b}]) continue;
            edg.push_back({u, id[{a, b}]});
        }
    }
}

struct Dsj {
    arr<int, N> prnt, sz;
    void intl() {
        for (int u = 1; u <= n; u++)
            prnt[u] = u, sz[u] = 1;
    }
    int pr(int u) {
        return (prnt[u] == u) ? u : prnt[u] = pr(prnt[u]);
    }
    bool mrg(int u, int v) {
        u = pr(u), v = pr(v);
        if (u == v) return false;
        prnt[v] = u, sz[u] += sz[v];
        return true;
    }
} dsj;
vec<pii> usd;
void usd_cmp() {
    dsj.intl();
    for (pii x : edg) {
        int u = x.fir, v = x.sec;
        if (!dsj.mrg(u, v)) continue;
        usd.push_back(x);
    }
}

vec<pii> sd;
void sd_cmp() {
    for (pii x : usd) {
        int u = x.fir, v = x.sec;
        if (ps[u] > ps[v]) swap(u, v);

        if (ps[u].fir != ps[v].fir) {
            sd.push_back({ps[u].fir + 1, ps[u].sec - 1});
        } else if (ps[u].fir == 2) {
            sd.push_back({ps[u].fir - 1, ps[u].sec + 1});
        } else {
            sd.push_back({ps[u].fir + 1, ps[u].sec + 1});
        }
    }
}

int construct_roads(vec<int> _x, vec<int> _y) {
    n = _x.size();
    for (int u = 1; u <= n; u++) {
        ps[u] = {_x[u - 1], _y[u - 1]};
        id[ps[u]] = u;
    }

    edg_cmp();
    usd_cmp();
    if (dsj.sz[dsj.pr(1)] != n) return 0;
    sd_cmp();

    vec<int> a, b, c, d;
    for (pii x : usd)
        a.push_back(x.fir - 1), b.push_back(x.sec - 1);
    for (pii x : sd)
        c.push_back(x.fir), d.push_back(x.sec);
    build(a, b, c, d);
    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