oj.uz

Submission #804207

# Submission time Handle Problem Language Result Execution time Memory
804207 2023-08-03T07:33:52 Z finn__ Fountain Parks (IOI21_parks) C++17
45 / 100
 347 ms 46752 KB 
#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];
bitset<N> visited;
size_t l;

void mark_cut_points(uint32_t u)
{
    visited[u] = 1;
    for (auto const &v : dual[u])
        if (!visited[v])
        {
            if (u == l)
            {
                bool placed = 0;
                for (size_t i = 0; i < 4; ++i)
                {
                    pair<int, int> cand = {dual_coords[v].first + (-2 + (i & 1) * 4) * !(bool)(i & 2),
                                           dual_coords[v].second + (-2 + (i & 1) * 4) * (bool)(i & 2)};
                    bool not_present = 1;
                    for (auto const &w : dual[v])
                        if (w != u)
                            not_present &= dual_coords[w] != cand;
                    if (not_present)
                    {
                        marked.emplace((dual_coords[v].first + cand.first) >> 1,
                                       (dual_coords[v].second + cand.second) >> 1);
                        placed = 1;
                        break;
                    }
                }
                assert(placed);
            }
            else
            {
                marked.emplace((dual_coords[u].first + dual_coords[v].first) >> 1,
                               (dual_coords[u].second + dual_coords[v].second) >> 1);
            }
            mark_cut_points(v);
        }
}

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]);
    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)
        {
            if (((x & 3) == 1) ^ ((y & 3) == 3))
                dual[get<2>(*it)].push_back(i);
            else
                dual[i].push_back(get<2>(*it));
        }
        it = midpoints.lower_bound({x, y + 2, 0});
        if (it != midpoints.end() && get<0>(*it) == x && get<1>(*it) == y + 2)
        {
            if (((y & 3) == 1) ^ ((x & 3) == 3))
                dual[i].push_back(get<2>(*it));
            else
                dual[get<2>(*it)].push_back(i);
        }
    }
    for (size_t i = 0; i < l; ++i)
        if (dual[i].size() < 4)
        {
            int x = dual_coords[i].first, y = dual_coords[i].second;
            for (size_t i = 0; i < 4; ++i)
            {
                pair<int, int> cand = {dual_coords[i].first + (-2 + (i & 1) * 4) * !(i & 2),
                                       dual_coords[i].second + (-2 + (i & 1) * 4) * (bool)(i & 2)};
                bool not_present = 1;
                for (auto const &w : dual[i])
                    if (w != l)
                        not_present &= dual_coords[w] != cand;
                if (not_present)
                {
                    if (cand.second == y && ((min(x, cand.first) & 3) == 1) ^ ((y & 3) == 3) ^ x > cand.first)
                    {
                        dual[l].push_back(i);
                        break;
                    }
                    if (cand.first == x && ((min(y, cand.second) & 3) == 1) ^ ((x & 3) == 3) ^ y > cand.second)
                    {
                        dual[l].push_back(i);
                        break;
                    }
                }
            }
        }
    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 (j < n && 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

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:133:98: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
  133 |                     if (cand.second == y && ((min(x, cand.first) & 3) == 1) ^ ((y & 3) == 3) ^ x > cand.first)
      |                                                                                                ~~^~~~~~~~~~~~
parks.cpp:138:98: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
  138 |                     if (cand.first == x && ((min(y, cand.second) & 3) == 1) ^ ((x & 3) == 3) ^ y > cand.second)
      |                                                                                                ~~^~~~~~~~~~~~~
parks.cpp:188:23: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
  188 |     if (d.set_size(0) != n)
      |         ~~~~~~~~~~~~~~^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6484 KB Output is correct
2 Correct 3 ms 6484 KB Output is correct
3 Correct 3 ms 6484 KB Output is correct
4 Correct 3 ms 6484 KB Output is correct
5 Correct 3 ms 6484 KB Output is correct
6 Correct 4 ms 6484 KB Output is correct
7 Correct 3 ms 6484 KB Output is correct
8 Correct 3 ms 6484 KB Output is correct
9 Correct 82 ms 22180 KB Output is correct
10 Correct 11 ms 8152 KB Output is correct
11 Correct 47 ms 14888 KB Output is correct
12 Correct 13 ms 9048 KB Output is correct
13 Correct 19 ms 11212 KB Output is correct
14 Correct 4 ms 6612 KB Output is correct
15 Correct 3 ms 6740 KB Output is correct
16 Correct 96 ms 22172 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6484 KB Output is correct
2 Correct 3 ms 6484 KB Output is correct
3 Correct 3 ms 6484 KB Output is correct
4 Correct 3 ms 6484 KB Output is correct
5 Correct 3 ms 6484 KB Output is correct
6 Correct 4 ms 6484 KB Output is correct
7 Correct 3 ms 6484 KB Output is correct
8 Correct 3 ms 6484 KB Output is correct
9 Correct 82 ms 22180 KB Output is correct
10 Correct 11 ms 8152 KB Output is correct
11 Correct 47 ms 14888 KB Output is correct
12 Correct 13 ms 9048 KB Output is correct
13 Correct 19 ms 11212 KB Output is correct
14 Correct 4 ms 6612 KB Output is correct
15 Correct 3 ms 6740 KB Output is correct
16 Correct 96 ms 22172 KB Output is correct
17 Correct 3 ms 6484 KB Output is correct
18 Correct 3 ms 6464 KB Output is correct
19 Correct 3 ms 6484 KB Output is correct
20 Correct 3 ms 6484 KB Output is correct
21 Correct 3 ms 6484 KB Output is correct
22 Correct 3 ms 6484 KB Output is correct
23 Incorrect 334 ms 46752 KB Tree @(3, 3) appears more than once: for edges on positions 1 and 2
24 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6484 KB Output is correct
2 Correct 3 ms 6484 KB Output is correct
3 Correct 3 ms 6484 KB Output is correct
4 Correct 3 ms 6484 KB Output is correct
5 Correct 3 ms 6484 KB Output is correct
6 Correct 4 ms 6484 KB Output is correct
7 Correct 3 ms 6484 KB Output is correct
8 Correct 3 ms 6484 KB Output is correct
9 Correct 82 ms 22180 KB Output is correct
10 Correct 11 ms 8152 KB Output is correct
11 Correct 47 ms 14888 KB Output is correct
12 Correct 13 ms 9048 KB Output is correct
13 Correct 19 ms 11212 KB Output is correct
14 Correct 4 ms 6612 KB Output is correct
15 Correct 3 ms 6740 KB Output is correct
16 Correct 96 ms 22172 KB Output is correct
17 Correct 3 ms 6484 KB Output is correct
18 Correct 3 ms 6464 KB Output is correct
19 Correct 3 ms 6484 KB Output is correct
20 Correct 3 ms 6484 KB Output is correct
21 Correct 3 ms 6484 KB Output is correct
22 Correct 3 ms 6484 KB Output is correct
23 Incorrect 334 ms 46752 KB Tree @(3, 3) appears more than once: for edges on positions 1 and 2
24 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6484 KB Output is correct
2 Correct 3 ms 6484 KB Output is correct
3 Correct 3 ms 6484 KB Output is correct
4 Correct 3 ms 6484 KB Output is correct
5 Correct 3 ms 6484 KB Output is correct
6 Correct 4 ms 6484 KB Output is correct
7 Correct 3 ms 6484 KB Output is correct
8 Correct 3 ms 6484 KB Output is correct
9 Correct 82 ms 22180 KB Output is correct
10 Correct 11 ms 8152 KB Output is correct
11 Correct 47 ms 14888 KB Output is correct
12 Correct 13 ms 9048 KB Output is correct
13 Correct 19 ms 11212 KB Output is correct
14 Correct 4 ms 6612 KB Output is correct
15 Correct 3 ms 6740 KB Output is correct
16 Correct 96 ms 22172 KB Output is correct
17 Correct 4 ms 6484 KB Output is correct
18 Correct 4 ms 6484 KB Output is correct
19 Correct 4 ms 6484 KB Output is correct
20 Correct 303 ms 39056 KB Output is correct
21 Correct 284 ms 38776 KB Output is correct
22 Correct 249 ms 38808 KB Output is correct
23 Correct 258 ms 34232 KB Output is correct
24 Correct 158 ms 22104 KB Output is correct
25 Correct 267 ms 26372 KB Output is correct
26 Correct 150 ms 26436 KB Output is correct
27 Correct 229 ms 38516 KB Output is correct
28 Correct 224 ms 38140 KB Output is correct
29 Correct 347 ms 38112 KB Output is correct
30 Correct 334 ms 38168 KB Output is correct
31 Correct 3 ms 6484 KB Output is correct
32 Correct 18 ms 8916 KB Output is correct
33 Correct 73 ms 14364 KB Output is correct
34 Correct 245 ms 39060 KB Output is correct
35 Correct 9 ms 7640 KB Output is correct
36 Correct 42 ms 11584 KB Output is correct
37 Correct 92 ms 16532 KB Output is correct
38 Correct 94 ms 19800 KB Output is correct
39 Correct 155 ms 24188 KB Output is correct
40 Correct 171 ms 30216 KB Output is correct
41 Correct 232 ms 34292 KB Output is correct
42 Correct 287 ms 39608 KB Output is correct
43 Correct 3 ms 6484 KB Output is correct
44 Correct 3 ms 6484 KB Output is correct
45 Correct 3 ms 6484 KB Output is correct
46 Correct 3 ms 6484 KB Output is correct
47 Correct 3 ms 6484 KB Output is correct
48 Correct 3 ms 6484 KB Output is correct
49 Correct 4 ms 6568 KB Output is correct
50 Correct 4 ms 6484 KB Output is correct
51 Correct 3 ms 6484 KB Output is correct
52 Correct 3 ms 6484 KB Output is correct
53 Correct 3 ms 6484 KB Output is correct
54 Correct 5 ms 6740 KB Output is correct
55 Correct 4 ms 6868 KB Output is correct
56 Correct 98 ms 22268 KB Output is correct
57 Correct 166 ms 30120 KB Output is correct
58 Correct 157 ms 30244 KB Output is correct
59 Correct 3 ms 6484 KB Output is correct
60 Correct 3 ms 6484 KB Output is correct
61 Correct 3 ms 6484 KB Output is correct
62 Correct 179 ms 38136 KB Output is correct
63 Correct 197 ms 38172 KB Output is correct
64 Correct 179 ms 38008 KB Output is correct
65 Correct 5 ms 6996 KB Output is correct
66 Correct 7 ms 7336 KB Output is correct
67 Correct 102 ms 22136 KB Output is correct
68 Correct 163 ms 31036 KB Output is correct
69 Correct 228 ms 38160 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6484 KB Output is correct
2 Correct 3 ms 6484 KB Output is correct
3 Correct 3 ms 6484 KB Output is correct
4 Correct 3 ms 6484 KB Output is correct
5 Correct 3 ms 6484 KB Output is correct
6 Correct 4 ms 6484 KB Output is correct
7 Correct 3 ms 6484 KB Output is correct
8 Correct 3 ms 6484 KB Output is correct
9 Correct 82 ms 22180 KB Output is correct
10 Correct 11 ms 8152 KB Output is correct
11 Correct 47 ms 14888 KB Output is correct
12 Correct 13 ms 9048 KB Output is correct
13 Correct 19 ms 11212 KB Output is correct
14 Correct 4 ms 6612 KB Output is correct
15 Correct 3 ms 6740 KB Output is correct
16 Correct 96 ms 22172 KB Output is correct
17 Correct 231 ms 38540 KB Output is correct
18 Correct 227 ms 38708 KB Output is correct
19 Correct 264 ms 38816 KB Output is correct
20 Correct 255 ms 37432 KB Output is correct
21 Correct 219 ms 34252 KB Output is correct
22 Correct 3 ms 6484 KB Output is correct
23 Correct 34 ms 11716 KB Output is correct
24 Correct 17 ms 8684 KB Output is correct
25 Correct 63 ms 14152 KB Output is correct
26 Correct 110 ms 18116 KB Output is correct
27 Correct 120 ms 22844 KB Output is correct
28 Correct 176 ms 26552 KB Output is correct
29 Correct 209 ms 31892 KB Output is correct
30 Correct 234 ms 35224 KB Output is correct
31 Correct 286 ms 39128 KB Output is correct
32 Correct 240 ms 38160 KB Output is correct
33 Correct 175 ms 38120 KB Output is correct
34 Correct 5 ms 7124 KB Output is correct
35 Correct 8 ms 7636 KB Output is correct
36 Correct 104 ms 22428 KB Output is correct
37 Correct 180 ms 30860 KB Output is correct
38 Correct 265 ms 38236 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6484 KB Output is correct
2 Correct 3 ms 6484 KB Output is correct
3 Correct 3 ms 6484 KB Output is correct
4 Correct 3 ms 6484 KB Output is correct
5 Correct 3 ms 6484 KB Output is correct
6 Correct 4 ms 6484 KB Output is correct
7 Correct 3 ms 6484 KB Output is correct
8 Correct 3 ms 6484 KB Output is correct
9 Correct 82 ms 22180 KB Output is correct
10 Correct 11 ms 8152 KB Output is correct
11 Correct 47 ms 14888 KB Output is correct
12 Correct 13 ms 9048 KB Output is correct
13 Correct 19 ms 11212 KB Output is correct
14 Correct 4 ms 6612 KB Output is correct
15 Correct 3 ms 6740 KB Output is correct
16 Correct 96 ms 22172 KB Output is correct
17 Correct 3 ms 6484 KB Output is correct
18 Correct 3 ms 6464 KB Output is correct
19 Correct 3 ms 6484 KB Output is correct
20 Correct 3 ms 6484 KB Output is correct
21 Correct 3 ms 6484 KB Output is correct
22 Correct 3 ms 6484 KB Output is correct
23 Incorrect 334 ms 46752 KB Tree @(3, 3) appears more than once: for edges on positions 1 and 2
24 Halted 0 ms 0 KB -