Submission #760846

#	Time	Username	Problem	Language	Result	Execution time	Memory
760846		caganyanmaz	Fountain Parks (IOI21_parks)	C++17	30 / 100	293 ms	59296 KiB

parks

#include <bits/stdc++.h>
#define pb push_back
using namespace std;

constexpr static int SIZE = 200001;

vector<int> g[SIZE];
bitset<SIZE> visited;
vector<array<int, 2>> rows[SIZE];
vector<array<int, 2>> intervals[SIZE];

vector<int> uu, vv, aa, bb;
void build(vector<int> u, vector<int> v, vector<int> a, vector<int> b);

void configure_rows(const vector<int>& x, const vector<int>& y)
{
        int n = x.size();
        for (int i = 0; i < n; i++)
                rows[y[i]].pb({x[i], i});
        for (int i = 0; i < SIZE; i+=2)
                sort(rows[i].begin(), rows[i].end());

}

void configure_intervals()
{
        for (int y = 0; y < SIZE; y+=2)
        {
                if (rows[y].empty())
                        continue;
                intervals[y].pb({rows[y][0][0], rows[y][0][0]});
                for (int i = 1; i < rows[y].size(); i++)
                {
                        if (intervals[y].back()[1] + 2 == rows[y][i][0])
                        {
                                intervals[y].back()[1] = rows[y][i][0];
                                g[rows[y][i-1][1]].pb(rows[y][i][1]);
                                g[rows[y][i][1]].pb(rows[y][i-1][1]);
                        }
                        else
                        {
                                intervals[y].pb({rows[y][i][0], rows[y][i][0]});
                        }

                }
        }
}

// Line from a1 to a2 and line from b1 to b2
// Checking intersection (touching also counts)
bool is_intersecting(int a1, int a2, int b1, int b2)
{
        return (b2 >= a1 && a1 >= b1) || (b2 >= a2 && a2 >= b1) || (a2 >= b1 && b1 >= a1) || (a2 >= b2 && b2 >= a1);
}

void configure_horizontal_connections()
{
        for (int y = 2; y < SIZE; y+=2)
        {
                int i = 0, j = 0;
                while (i < intervals[y].size() && j < intervals[y-2].size())
                {
                        if (is_intersecting(intervals[y][i][0], intervals[y][i][1], intervals[y-2][j][0], intervals[y-2][j][1]))
                        {
                                int x = max(intervals[y][i][0], intervals[y-2][j][0]);
                                array<int, 2> pos = {x, 0};
                                int a = (*lower_bound(rows[y].begin(), rows[y].end(), pos))[1];
                                int b = (*lower_bound(rows[y-2].begin(), rows[y-2].end(), pos))[1];
                                g[a].pb(b);
                                g[b].pb(a);

                        }
                        if (intervals[y][i][1] > intervals[y-2][j][1])
                                j++;
                        else
                                i++;
                }
        }
}


int node_sum = 0;
void dfs(int node)
{
        visited[node] = true;
        node_sum++;
        for (int c : g[node])
                if (!visited[c])
                        dfs(c);
}

void build_grid(const vector<int>& xv, const vector<int>& yv)
{
        vector<int> u, v, a, b;
        set<array<int, 2>> fountains;
        for (int y = 0; y < SIZE; y+=2)
        {
                for (auto [x, node] : rows[y])
                {
                        for (int c : g[node])
                        {
                                if (yv[c] != y || xv[c] > x)
                                        continue;
                                int fx = x-1, fy = y-1;
                                if (fountains.find({fx, fy}) != fountains.end())
                                        fy += 2;
                                assert(fountains.find({fx, fy}) == fountains.end());
                                u.pb(node), v.pb(c), a.pb(fx), b.pb(fy);
                                fountains.insert({fx, fy});
                        }
                }
                for (auto [x, node] : rows[y])
                {
                        for (int c : g[node])
                        {
                                if (yv[c] <= y)
                                        continue;
                                int fx = x-1, fy = y+1;
                                array<int, 2> pos = {x+2, -1};
                                if (fountains.find({fx, fy}) != fountains.end() || (fountains.find({fx+2, fy}) == fountains.end() && (*lower_bound(rows[y+2].begin(), rows[y+2].end(), pos))[0] != x+2))
                                        fx += 2;
                                assert(fountains.find({fx, fy}) == fountains.end());
                                u.pb(node), v.pb(c), a.pb(fx), b.pb(fy);
                                fountains.insert({fx, fy});
                        }
                }
        }
        build(u, v, a, b);

}

int construct_roads(vector<int> x, vector<int> y)
{
        configure_rows(x, y);
        configure_intervals();
        configure_horizontal_connections();
        dfs(0);
        if (node_sum < x.size())
                return 0;
        else
                build_grid(x, y);
        return 1;
}

Compilation message (stderr)

parks.cpp: In function 'void configure_intervals()':
parks.cpp:32:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |                 for (int i = 1; i < rows[y].size(); i++)
      |                                 ~~^~~~~~~~~~~~~~~~
parks.cpp: In function 'void configure_horizontal_connections()':
parks.cpp:61:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |                 while (i < intervals[y].size() && j < intervals[y-2].size())
      |                        ~~^~~~~~~~~~~~~~~~~~~~~
parks.cpp:61:53: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |                 while (i < intervals[y].size() && j < intervals[y-2].size())
      |                                                   ~~^~~~~~~~~~~~~~~~~~~~~~~
parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:138:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |         if (node_sum < x.size())
      |             ~~~~~~~~~^~~~~~~~~~

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