Submission #800774

#	Time	Username	Problem	Language	Result	Execution time	Memory
800774		finn__	Fountain Parks (IOI21_parks)	C++17	45 / 100	278 ms	39692 KiB

parks

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

template <size_t N>
struct dsu
{
    int64_t p[N];

    dsu() { fill(p, p + N, -1); }

    int64_t repr(int64_t u) { return p[u] < 0 ? u : p[u] = repr(p[u]); }

    bool merge(int64_t i, int64_t j)
    {
        i = repr(i);
        j = repr(j);
        if (i == j)
            return 0;

        if (p[i] > p[j])
            swap(i, j);
        p[i] += p[j];
        p[j] = i;
        return 1;
    }

    bool same_set(int64_t i, int64_t j) { return repr(i) == repr(j); }

    int64_t set_size(int64_t i) { return -p[repr(i)]; }

    void reset() { fill(p.begin(), p.end(), -1); }
};

struct fountain
{
    int x, y;
    size_t i;
};

constexpr size_t N = 200000;

fountain f[N];
vector<pair<size_t, size_t>> edges;
vector<uint32_t> dual[N];
dsu<N> d;
set<pair<int, int>> points, marked;
set<tuple<int, int, uint32_t>> midpoints;
pair<int, int> dual_coords[N];

void mark_cut_points(uint32_t u, uint32_t p = -1)
{
    for (auto const &v : dual[u])
        if (v != p)
        {
            marked.emplace((dual_coords[u].first + dual_coords[v].first) >> 1, (dual_coords[u].second + dual_coords[v].second) >> 1);
            mark_cut_points(v, u);
        }
}

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

    for (size_t i = 0; i < n; ++i)
        points.emplace(x[i], y[i]);
    size_t l = 0;
    for (size_t i = 0; i < n; ++i)
        if (points.find({x[i] + 2, y[i]}) != points.end() &&
            points.find({x[i], y[i] + 2}) != points.end() &&
            points.find({x[i] + 2, y[i] + 2}) != points.end())
            midpoints.emplace(x[i] + 1, y[i] + 1, l++), dual_coords[l - 1] = {x[i] + 1, y[i] + 1};
    for (auto const &[x, y, i] : midpoints)
    {
        auto it = midpoints.lower_bound({x + 2, y, 0});
        if (it != midpoints.end() && get<0>(*it) == x + 2 && get<1>(*it) == y)
            dual[i].push_back(get<2>(*it)), dual[get<2>(*it)].push_back(i);
        it = midpoints.lower_bound({x, y + 2, 0});
        if (it != midpoints.end() && get<0>(*it) == x && get<1>(*it) == y + 2)
            dual[i].push_back(get<2>(*it)), dual[get<2>(*it)].push_back(i);
    }
    for (size_t i = 0; i < l; ++i)
        if (dual[i].size() < 4)
            dual[l].push_back(i), dual[i].push_back(l);
    mark_cut_points(l);

    for (size_t i = 0; i < x.size(); ++i)
        f[i].i = i, f[i].x = x[i], f[i].y = y[i];
    sort(f, f + n, [](auto const &a, auto const &b)
         { return a.y == b.y ? a.x < b.x : a.y < b.y; });

    for (size_t i = 0; i < n;)
    {
        size_t j = i;
        while (j < n && f[j].y == f[i].y)
            ++j;

        for (size_t k = i + 1; k < j; ++k)
            if (f[k - 1].x + 2 == f[k].x)
                if (marked.find({f[k - 1].x + 1, f[k - 1].y}) == marked.end() &&
                    d.merge(f[k - 1].i, f[k].i))
                    edges.emplace_back(f[k - 1].i, f[k].i);

        if (f[j].y == f[i].y + 2)
        {
            size_t k = j;
            while (i < j && k < n && f[k].y == f[j].y)
            {
                if (f[i].x < f[k].x)
                    ++i;
                else if (f[k].x < f[i].x)
                    ++k;
                else
                {
                    if (marked.find({f[i].x, f[i].y + 1}) == marked.end() &&
                        d.merge(f[i].i, f[k].i))
                        edges.emplace_back(f[k].i, f[i].i);
                    ++i;
                    ++k;
                }
            }
        }

        i = j;
    }

    if (d.set_size(0) != n)
        return 0;
    vector<int> u, v, a, b;
    for (auto const &[i, j] : edges)
    {
        u.push_back(i);
        v.push_back(j);
        if (x[i] == x[j])
        {
            b.push_back((y[i] + y[j]) >> 1);
            if (((x[i] & 3) == 2) ^ ((min(y[i], y[j]) & 3) == 2))
                a.push_back(x[i] - 1);
            else
                a.push_back(x[i] + 1);
        }
        else
        {
            a.push_back((x[i] + x[j]) >> 1);
            if (((y[i] & 3) == 2) ^ ((min(x[i], x[j]) & 3) == 2))
                b.push_back(y[i] + 1);
            else
                b.push_back(y[i] - 1);
        }
    }

    build(u, v, a, b);
    return 1;
}

Compilation message (stderr)

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:127:23: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
  127 |     if (d.set_size(0) != n)
      |         ~~~~~~~~~~~~~~^~~~

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