Submission #1070414

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070414		Arapak	Fountain Parks (IOI21_parks)	C++17	30 / 100	280 ms	41340 KiB

parks

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

#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;

#ifdef DEBUG
auto& operator<<(auto &os, const pair<auto,auto> &p) {
    return os<<"("<<p.first<<", "<<p.second<<")";
}
auto& operator<<(auto &os, const auto &v) {
    os<<"{";
    for(auto it=begin(v);it!=end(v);++it) {
        if(it != begin(v)) os<<", ";
        os<<(*it);
    }
    return os<<"}";
}

void dbg_out(auto... x) {
    ((cerr<<' '<<x), ...) << endl;
}
#define dbg(x...) cerr<<"("<<#x<<"):", dbg_out(x);
#else
#define dbg(...)
#endif

struct UF {
    vi e;
    UF(int n) : e(n, -1) {}
    bool sameSet(int a, int b) { return find(a) == find(b); }
    int size(int x) { return -e[find(x)]; }
    int find(int x) { return e[x] < 0 ? x : e[x] = find(e[x]); }
    bool join(int a, int b) {
        a = find(a), b = find(b);
        if (a == b) return false;
        if (e[a] > e[b]) swap(a, b);
        e[a] += e[b]; e[b] = a;
        return true;
    }
};

struct Fountain {
    int x, y, index;

    friend bool operator<(const Fountain &a, const Fountain &b) {
        return tie(a.x, a.y) < tie(b.x, b.y);
    }
};

struct Bench {
    int a, b;
    int x, y;

    friend bool operator<(const Bench &a, const Bench &b) {
        return tie(a.x, a.y) < tie(b.x, b.y);
    }
};

void build_from_benches(set<Bench> &benches) {
    vi u, v, a, b;
    for(auto bench : benches) {
        u.push_back(bench.a);
        v.push_back(bench.b);
        a.push_back(bench.x);
        b.push_back(bench.y);
    }
    build(u, v, a, b);
}

int construct_roads(vi x, vi y) {
    int n = sz(x);
    dbg(x, y);
    set<Fountain> s;
    rep(i,0,n) s.insert({x[i], y[i], i});
    set<Bench> benches;
    UF uf(n);
    for(auto f : s) {
        {
            auto it = s.find({f.x - 2, f.y, -1});
            if(it != s.end()) {
                auto t = *it;
                if(uf.find(f.index) != uf.find(t.index)) {
                    Bench b;
                    b.a = f.index;
                    b.b = t.index;
                    b.x = f.x - 1;

                    b.y = f.y - 1;
                    if(benches.count(b))
                        b.y = f.y + 1;
                    if(benches.count(b))
                        return 0;
                    benches.insert(b);
                    uf.join(f.index, t.index);
                }
            }
        }

        {
            auto it = s.find({f.x, f.y - 2, -1});
            if(it != s.end()) {
                auto t = *it;
                if(uf.find(f.index) != uf.find(t.index)) {
                    Bench b;
                    b.a = f.index;
                    b.b = t.index;
                    b.y = f.y - 1;

                    b.x = f.x - 1;
                    if(benches.count(b))
                        b.x = f.x + 1;
                    if(benches.count(b))
                        return 0;
                    benches.insert(b);
                    uf.join(f.index, t.index);
                }
            }
        }
    }
    int index = uf.find(0);
    rep(i,0,n)
        if(uf.find(i) != index)
            return 0;
    build_from_benches(benches);
    return 1;
}

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