oj.uz

Submission #760844

# Submission time Handle Problem Language Result Execution time Memory
760844 2023-06-18T16:49:09 Z caganyanmaz Fountain Parks (IOI21_parks) C++17
15 / 100
 273 ms 100812 KB 
#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];

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;
                                if (fountains.find({fx, fy}) != fountains.end())
                                        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

parks.cpp: In function 'void configure_intervals()':
parks.cpp:31: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]
   31 |                 for (int i = 1; i < rows[y].size(); i++)
      |                                 ~~^~~~~~~~~~~~~~~~
parks.cpp: In function 'void configure_horizontal_connections()':
parks.cpp:60: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]
   60 |                 while (i < intervals[y].size() && j < intervals[y-2].size())
      |                        ~~^~~~~~~~~~~~~~~~~~~~~
parks.cpp:60: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]
   60 |                 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:136:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |         if (node_sum < x.size())
      |             ~~~~~~~~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14396 KB Output is correct
2 Correct 7 ms 14292 KB Output is correct
3 Correct 7 ms 14292 KB Output is correct
4 Correct 7 ms 14396 KB Output is correct
5 Correct 7 ms 14292 KB Output is correct
6 Correct 9 ms 14384 KB Output is correct
7 Correct 7 ms 14292 KB Output is correct
8 Correct 7 ms 14292 KB Output is correct
9 Correct 118 ms 39000 KB Output is correct
10 Correct 15 ms 16980 KB Output is correct
11 Correct 53 ms 27796 KB Output is correct
12 Correct 19 ms 18348 KB Output is correct
13 Correct 24 ms 20580 KB Output is correct
14 Correct 10 ms 14420 KB Output is correct
15 Correct 7 ms 14624 KB Output is correct
16 Correct 113 ms 37072 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14396 KB Output is correct
2 Correct 7 ms 14292 KB Output is correct
3 Correct 7 ms 14292 KB Output is correct
4 Correct 7 ms 14396 KB Output is correct
5 Correct 7 ms 14292 KB Output is correct
6 Correct 9 ms 14384 KB Output is correct
7 Correct 7 ms 14292 KB Output is correct
8 Correct 7 ms 14292 KB Output is correct
9 Correct 118 ms 39000 KB Output is correct
10 Correct 15 ms 16980 KB Output is correct
11 Correct 53 ms 27796 KB Output is correct
12 Correct 19 ms 18348 KB Output is correct
13 Correct 24 ms 20580 KB Output is correct
14 Correct 10 ms 14420 KB Output is correct
15 Correct 7 ms 14624 KB Output is correct
16 Correct 113 ms 37072 KB Output is correct
17 Correct 7 ms 14292 KB Output is correct
18 Correct 7 ms 14292 KB Output is correct
19 Correct 7 ms 14292 KB Output is correct
20 Correct 8 ms 14292 KB Output is correct
21 Correct 9 ms 14292 KB Output is correct
22 Correct 7 ms 14292 KB Output is correct
23 Correct 240 ms 53044 KB Output is correct
24 Correct 7 ms 14292 KB Output is correct
25 Correct 9 ms 14624 KB Output is correct
26 Correct 8 ms 14604 KB Output is correct
27 Correct 8 ms 14676 KB Output is correct
28 Correct 84 ms 29976 KB Output is correct
29 Correct 129 ms 37196 KB Output is correct
30 Correct 183 ms 45412 KB Output is correct
31 Correct 273 ms 52600 KB Output is correct
32 Correct 7 ms 14292 KB Output is correct
33 Correct 7 ms 14292 KB Output is correct
34 Correct 7 ms 14292 KB Output is correct
35 Correct 7 ms 14276 KB Output is correct
36 Correct 7 ms 14340 KB Output is correct
37 Correct 9 ms 14292 KB Output is correct
38 Correct 7 ms 14324 KB Output is correct
39 Correct 7 ms 14292 KB Output is correct
40 Correct 7 ms 14292 KB Output is correct
41 Correct 6 ms 14292 KB Output is correct
42 Correct 9 ms 14292 KB Output is correct
43 Correct 7 ms 14548 KB Output is correct
44 Correct 8 ms 14548 KB Output is correct
45 Correct 113 ms 35648 KB Output is correct
46 Correct 168 ms 45572 KB Output is correct
47 Correct 179 ms 45228 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14396 KB Output is correct
2 Correct 7 ms 14292 KB Output is correct
3 Correct 7 ms 14292 KB Output is correct
4 Correct 7 ms 14396 KB Output is correct
5 Correct 7 ms 14292 KB Output is correct
6 Correct 9 ms 14384 KB Output is correct
7 Correct 7 ms 14292 KB Output is correct
8 Correct 7 ms 14292 KB Output is correct
9 Correct 118 ms 39000 KB Output is correct
10 Correct 15 ms 16980 KB Output is correct
11 Correct 53 ms 27796 KB Output is correct
12 Correct 19 ms 18348 KB Output is correct
13 Correct 24 ms 20580 KB Output is correct
14 Correct 10 ms 14420 KB Output is correct
15 Correct 7 ms 14624 KB Output is correct
16 Correct 113 ms 37072 KB Output is correct
17 Correct 7 ms 14292 KB Output is correct
18 Correct 7 ms 14292 KB Output is correct
19 Correct 7 ms 14292 KB Output is correct
20 Correct 8 ms 14292 KB Output is correct
21 Correct 9 ms 14292 KB Output is correct
22 Correct 7 ms 14292 KB Output is correct
23 Correct 240 ms 53044 KB Output is correct
24 Correct 7 ms 14292 KB Output is correct
25 Correct 9 ms 14624 KB Output is correct
26 Correct 8 ms 14604 KB Output is correct
27 Correct 8 ms 14676 KB Output is correct
28 Correct 84 ms 29976 KB Output is correct
29 Correct 129 ms 37196 KB Output is correct
30 Correct 183 ms 45412 KB Output is correct
31 Correct 273 ms 52600 KB Output is correct
32 Correct 7 ms 14292 KB Output is correct
33 Correct 7 ms 14292 KB Output is correct
34 Correct 7 ms 14292 KB Output is correct
35 Correct 7 ms 14276 KB Output is correct
36 Correct 7 ms 14340 KB Output is correct
37 Correct 9 ms 14292 KB Output is correct
38 Correct 7 ms 14324 KB Output is correct
39 Correct 7 ms 14292 KB Output is correct
40 Correct 7 ms 14292 KB Output is correct
41 Correct 6 ms 14292 KB Output is correct
42 Correct 9 ms 14292 KB Output is correct
43 Correct 7 ms 14548 KB Output is correct
44 Correct 8 ms 14548 KB Output is correct
45 Correct 113 ms 35648 KB Output is correct
46 Correct 168 ms 45572 KB Output is correct
47 Correct 179 ms 45228 KB Output is correct
48 Correct 7 ms 14292 KB Output is correct
49 Correct 7 ms 14292 KB Output is correct
50 Correct 6 ms 14292 KB Output is correct
51 Correct 7 ms 14392 KB Output is correct
52 Correct 7 ms 14292 KB Output is correct
53 Correct 8 ms 14308 KB Output is correct
54 Correct 7 ms 14396 KB Output is correct
55 Correct 229 ms 50304 KB Output is correct
56 Correct 7 ms 14292 KB Output is correct
57 Runtime error 19 ms 29524 KB Execution killed with signal 6
58 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14396 KB Output is correct
2 Correct 7 ms 14292 KB Output is correct
3 Correct 7 ms 14292 KB Output is correct
4 Correct 7 ms 14396 KB Output is correct
5 Correct 7 ms 14292 KB Output is correct
6 Correct 9 ms 14384 KB Output is correct
7 Correct 7 ms 14292 KB Output is correct
8 Correct 7 ms 14292 KB Output is correct
9 Correct 118 ms 39000 KB Output is correct
10 Correct 15 ms 16980 KB Output is correct
11 Correct 53 ms 27796 KB Output is correct
12 Correct 19 ms 18348 KB Output is correct
13 Correct 24 ms 20580 KB Output is correct
14 Correct 10 ms 14420 KB Output is correct
15 Correct 7 ms 14624 KB Output is correct
16 Correct 113 ms 37072 KB Output is correct
17 Correct 7 ms 14268 KB Output is correct
18 Correct 7 ms 14292 KB Output is correct
19 Correct 7 ms 14300 KB Output is correct
20 Correct 245 ms 58024 KB Output is correct
21 Correct 257 ms 53968 KB Output is correct
22 Correct 231 ms 52896 KB Output is correct
23 Correct 210 ms 45920 KB Output is correct
24 Correct 45 ms 21708 KB Output is correct
25 Correct 62 ms 25844 KB Output is correct
26 Correct 103 ms 27800 KB Output is correct
27 Correct 267 ms 46688 KB Output is correct
28 Correct 223 ms 46672 KB Output is correct
29 Correct 198 ms 44340 KB Output is correct
30 Correct 206 ms 44488 KB Output is correct
31 Correct 7 ms 14292 KB Output is correct
32 Runtime error 23 ms 31456 KB Execution killed with signal 6
33 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14396 KB Output is correct
2 Correct 7 ms 14292 KB Output is correct
3 Correct 7 ms 14292 KB Output is correct
4 Correct 7 ms 14396 KB Output is correct
5 Correct 7 ms 14292 KB Output is correct
6 Correct 9 ms 14384 KB Output is correct
7 Correct 7 ms 14292 KB Output is correct
8 Correct 7 ms 14292 KB Output is correct
9 Correct 118 ms 39000 KB Output is correct
10 Correct 15 ms 16980 KB Output is correct
11 Correct 53 ms 27796 KB Output is correct
12 Correct 19 ms 18348 KB Output is correct
13 Correct 24 ms 20580 KB Output is correct
14 Correct 10 ms 14420 KB Output is correct
15 Correct 7 ms 14624 KB Output is correct
16 Correct 113 ms 37072 KB Output is correct
17 Correct 228 ms 55936 KB Output is correct
18 Correct 221 ms 54980 KB Output is correct
19 Runtime error 240 ms 100812 KB Execution killed with signal 6
20 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14396 KB Output is correct
2 Correct 7 ms 14292 KB Output is correct
3 Correct 7 ms 14292 KB Output is correct
4 Correct 7 ms 14396 KB Output is correct
5 Correct 7 ms 14292 KB Output is correct
6 Correct 9 ms 14384 KB Output is correct
7 Correct 7 ms 14292 KB Output is correct
8 Correct 7 ms 14292 KB Output is correct
9 Correct 118 ms 39000 KB Output is correct
10 Correct 15 ms 16980 KB Output is correct
11 Correct 53 ms 27796 KB Output is correct
12 Correct 19 ms 18348 KB Output is correct
13 Correct 24 ms 20580 KB Output is correct
14 Correct 10 ms 14420 KB Output is correct
15 Correct 7 ms 14624 KB Output is correct
16 Correct 113 ms 37072 KB Output is correct
17 Correct 7 ms 14292 KB Output is correct
18 Correct 7 ms 14292 KB Output is correct
19 Correct 7 ms 14292 KB Output is correct
20 Correct 8 ms 14292 KB Output is correct
21 Correct 9 ms 14292 KB Output is correct
22 Correct 7 ms 14292 KB Output is correct
23 Correct 240 ms 53044 KB Output is correct
24 Correct 7 ms 14292 KB Output is correct
25 Correct 9 ms 14624 KB Output is correct
26 Correct 8 ms 14604 KB Output is correct
27 Correct 8 ms 14676 KB Output is correct
28 Correct 84 ms 29976 KB Output is correct
29 Correct 129 ms 37196 KB Output is correct
30 Correct 183 ms 45412 KB Output is correct
31 Correct 273 ms 52600 KB Output is correct
32 Correct 7 ms 14292 KB Output is correct
33 Correct 7 ms 14292 KB Output is correct
34 Correct 7 ms 14292 KB Output is correct
35 Correct 7 ms 14276 KB Output is correct
36 Correct 7 ms 14340 KB Output is correct
37 Correct 9 ms 14292 KB Output is correct
38 Correct 7 ms 14324 KB Output is correct
39 Correct 7 ms 14292 KB Output is correct
40 Correct 7 ms 14292 KB Output is correct
41 Correct 6 ms 14292 KB Output is correct
42 Correct 9 ms 14292 KB Output is correct
43 Correct 7 ms 14548 KB Output is correct
44 Correct 8 ms 14548 KB Output is correct
45 Correct 113 ms 35648 KB Output is correct
46 Correct 168 ms 45572 KB Output is correct
47 Correct 179 ms 45228 KB Output is correct
48 Correct 7 ms 14292 KB Output is correct
49 Correct 7 ms 14292 KB Output is correct
50 Correct 6 ms 14292 KB Output is correct
51 Correct 7 ms 14392 KB Output is correct
52 Correct 7 ms 14292 KB Output is correct
53 Correct 8 ms 14308 KB Output is correct
54 Correct 7 ms 14396 KB Output is correct
55 Correct 229 ms 50304 KB Output is correct
56 Correct 7 ms 14292 KB Output is correct
57 Runtime error 19 ms 29524 KB Execution killed with signal 6
58 Halted 0 ms 0 KB -