Submission #593998

#	Time	Username	Problem	Language	Result	Execution time	Memory
593998		SlavicG	Fountain Parks (IOI21_parks)	C++17	45 / 100	362 ms	31404 KiB

parks

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

#define         sz(a)     (int)a.size()
#define        all(a)     a.begin(),a.end()
#define    forn(i, n)     for(int i = 0; i < n; ++i)

const int N = 2e5 + 10;
int p[N];
int get(int a) {
    return p[a] = (a == p[a] ? a : get(p[a]));
}
bool uni(int a, int b) {
    a = get(a), b = get(b);
    if(a == b) return false;
    p[a] = b;
    return true;
}

struct point {
    int x, y, idx;
};
bool cmp(point a, point b) {
    if(a.x < b.x) return 1;
    if(a.x > b.x) return 0;
    return a.y < b.y;
}
map<pair<int, int>, int> st;
int construct_roads(vector<int> x, vector<int> y) {
    forn(i, N) p[i] = i;
    if (x.size() == 1) {
        build({}, {}, {}, {});
        return 1;
    }
    vector<int> u, v, a, b;
    vector<point> points;
    forn(i, sz(x)) points.push_back({x[i], y[i], i}), st[{x[i], y[i]}] = i;
    sort(all(points), cmp);

    for(auto p: points) {
        pair<int, int> c = {p.x - 2, p.y};
        if(st.count(c) && uni(st[c], p.idx)) {
            u.push_back(st[c]), v.push_back(p.idx);
            if(p.x % 4 == 0) {
                if(p.y % 4 == 2) {
                    a.push_back(p.x - 1);
                    b.push_back(p.y - 1);
                } else {
                    a.push_back(p.x - 1);
                    b.push_back(p.y + 1);
                }
            } else {
                if(p.y % 4 == 2) {
                    a.push_back(p.x - 1);
                    b.push_back(p.y + 1);
                } else {
                    a.push_back(p.x - 1);
                    b.push_back(p.y - 1);
                }
            }
        }
        /*
        c = {p.x, p.y - 2};
        if(st.count(c) && uni(st[c], p.idx)) {
            u.push_back(st[c]), v.push_back(p.idx);
            if(p.y % 4 == 0) {
                if(p.x % 4 == 2) {
                    a.push_back(p.x + 1);
                    b.push_back(p.y - 1);
                } else {
                    a.push_back(p.x - 1);
                    b.push_back(p.y - 1);
                }
            } else {
                if(p.x % 4 == 2) {
                    a.push_back(p.x - 1);
                    b.push_back(p.y - 1);
                } else {
                    a.push_back(p.x + 1);
                    b.push_back(p.y - 1);
                }
            }
        }
        */
    }

    for(auto p: points) {
        pair<int, int> c = {p.x - 2, p.y};
        /*
        if(st.count(c) && uni(st[c], p.idx)) {
            u.push_back(st[c]), v.push_back(p.idx);
            if(p.x % 4 == 0) {
                if(p.y % 4 == 2) {
                    a.push_back(p.x - 1);
                    b.push_back(p.y - 1);
                } else {
                    a.push_back(p.x - 1);
                    b.push_back(p.y + 1);
                }
            } else {
                if(p.y % 4 == 2) {
                    a.push_back(p.x - 1);
                    b.push_back(p.y + 1);
                } else {
                    a.push_back(p.x - 1);
                    b.push_back(p.y - 1);
                }
            }
        }
        */
        c = {p.x, p.y - 2};
        if(st.count(c) && uni(st[c], p.idx)) {
            u.push_back(st[c]), v.push_back(p.idx);
            if(p.y % 4 == 0) {
                if(p.x % 4 == 2) {
                    a.push_back(p.x + 1);
                    b.push_back(p.y - 1);
                } else {
                    a.push_back(p.x - 1);
                    b.push_back(p.y - 1);
                }
            } else {
                if(p.x % 4 == 2) {
                    a.push_back(p.x - 1);
                    b.push_back(p.y - 1);
                } else {
                    a.push_back(p.x + 1);
                    b.push_back(p.y - 1);
                }
            }
        }

    }

    for(int i = 0; i < sz(x); ++i) if(get(i) != get(0)) return 0;
    build(u, v, a, b);
    return 1;
}

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