Submission #558828

#	Time	Username	Problem	Language	Result	Execution time	Memory
558828		teraqqq	Fountain Parks (IOI21_parks)	C++17	100 / 100	437 ms	30520 KiB

parks

#include "parks.h"

#include <iostream>
#include <numeric>
#include <algorithm>
#include <utility>
#include <map>

#include <cassert>

using namespace std;
using vi = vector<int>;
using pi = pair<int, int>;

struct Dsu {
	vector<int> rnk, par;

	Dsu(int n) : rnk(n, 1), par(n) {
		iota(par.begin(), par.end(), 0);
	}

	int root(int v) {
		return v == par[v] ? v : par[v] = root(par[v]);
	}

	bool same(int a, int b) {
		return root(a) == root(b);
	}

	bool unite(int a, int b) {
		a = root(a), b = root(b);
		if (a == b) {
			return false;
		} else {
			if (rnk[a] < rnk[b]) swap(a, b);
			rnk[a] += rnk[b];
			par[b] = a;
			return true;
		}
	}
};


int construct_roads(std::vector<int> x, std::vector<int> y) {
    const int n = x.size();

    vector<int> p(n);
    iota(p.begin(), p.end(), 0);
    sort(p.begin(), p.end(), [&](int i, int j) {
        return make_pair(x[i], y[i]) < make_pair(x[j], y[j]);
    });

    map<pi, int> ord;
    for (int i = 0; i < n; ++i) {
        ord[{x[i], y[i]}] = i;
    }

    Dsu dsu(n);
    vi u, v, a, b;

    int edges = 0;

    auto get_id = [&](int x, int y) {
        if (!ord.count({x, y})) return -1;
        return ord[{x, y}];
    };

    auto get_chair = [&] (int x1, int y1, int x2, int y2) {
        if ((x1 + y1) % 4) swap(x1, x2), swap(y1, y2);
        const int x3 = x1 - (y2 - y1);
        const int y3 = y1 + (x2 - x1);
        return pi {(x2+x3)>>1, (y2+y3)>>1};
    };

    auto add_edge = [&](int x1, int y1, int x2, int y2) {
        if (!ord.count({x1, y1}) || !ord.count({x2, y2})) return;
        const int i = ord[{x1, y1}];
        const int j = ord[{x2, y2}];

        const auto [cx, cy] = get_chair(x1, y1, x2, y2);

        if (dsu.unite(i, j)) {
            u.push_back(i);
            v.push_back(j);
            a.push_back(cx);
            b.push_back(cy);
            edges++;
        }
    };

    for (int i : p) {
        const int px = x[i], py = y[i];

        if (get_id(px-2, py-2) != -1 && get_id(px-2, py) != -1 && get_id(px, py-2) != -1) {
            const auto [nx, ny] = get_chair(px, py, px-2, py);
            if (nx != px - 1 || ny != py - 1) {
                add_edge(px, py, px-2, py);
            } else {
                add_edge(px, py, px, py-2);
            }
        } else {
            add_edge(px, py, px, py-2);
            add_edge(px, py, px-2, py);
        }
    }

    if (edges == n - 1) {
        build(u, v, a, b);
        return 1;
    } else {
        return 0;
    }
}

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