oj.uz

Submission #761483

# Submission time Handle Problem Language Result Execution time Memory
761483 2023-06-19T19:10:06 Z caganyanmaz Fountain Parks (IOI21_parks) C++17
5 / 100
 260 ms 70004 KB 
#include <bits/stdc++.h>
#define pb push_back
using namespace std;

void build(vector<int> u, vector<int> v, vector<int> a, vector<int> b);
int construct_roads(vector<int> x, vector<int> y);

#ifdef __DEBUG__
void build(vector<int> u, vector<int> v, vector<int> a, vector<int> b){}
#endif


constexpr static int SIZE = 200001;

vector<array<int, 3>> m;
vector<array<int, 2>> pos;
set<array<int, 2>> fountains;
bitset<SIZE> visited;
vector<int> uu, vv, aa, bb;

int get_node(int x, int y)
{
        array<int, 3> a = {x, y, 0};
        auto it = lower_bound(m.begin(), m.end(), a);
        if (it != m.end() && (*it)[0] == x && (*it)[1] == y)
                return (*it)[2];
        return -1;
}

void dfs(int node, int last, int fx, int fy);

bool try_insert(int u, int v, int fx, int fy)
{
        if (v != -1 && !visited[v] && fountains.find({fx, fy}) == fountains.end())
        {
                uu.pb(u), vv.pb(v), aa.pb(fx), bb.pb(fy);
                fountains.insert({fx, fy});
                dfs(v, u, fx, fy);
                return true;
        }
        return false;
}

// direction: 1 vertical, 0 horizontal
// orientation: 1 ccw, 0 cw
void dfs(int node, int last, int fx, int fy)
{
        visited[node] = true;
        auto [node_x, node_y] = pos[node];
        auto [last_x, last_y] = pos[last];
        int left_x = 2 * fx - last_x, left_y = 2 * fy - last_y;
        int top_x = 2 * node_x - last_x, top_y = 2 * node_y - last_y;
        int right_x = 2 * node_x - left_x, right_y = 2 * node_y - left_y;
        int left_fx = node_x + left_x - fx, left_fy = node_y + left_y - fy;
        int left = get_node(left_x, left_y), top = get_node(top_x, top_y), right = get_node(right_x, right_y);
        if (try_insert(node, left, left_fx, left_fy))
        {
                int top_fx = top_x + node_x - left_fx, top_fy = top_y + node_y - left_fy;
                int right_fx, right_fy;
                if (try_insert(node, top, top_fx, top_fy))
                        right_fx = node_x + right_x - top_fx, right_fy = node_y + right_y - top_fy;
                else
                        right_fx = top_fx, right_fy, top_fy;
                try_insert(node, right, right_fx, right_fy);
        }
        else
        {
                int right_fx = node_x * 2 - fx, right_fy = node_y * 2 - fy;
                try_insert(node, right, right_fx, right_fy);
                int top_fx = left_fx, top_fy = left_fy;
                try_insert(node, top, top_fx, top_fy);
        }
}

int construct_roads(vector<int> x, vector<int> y)
{
        for (int i = 0; i < x.size(); i++)
        {
                m.pb({x[i], y[i], i});
                pos.pb({x[i], y[i]});
        }
        sort(m.begin(), m.end());
        int a = m[0][2];
        visited[a] = true;
        int b = get_node(m[0][0], m[0][1] + 2);
        if (b != -1)
        {
                uu.pb(a), vv.pb(b), aa.pb(m[0][0] -1), bb.pb(m[0][1] + 1);
                fountains.insert({m[0][0] - 1, m[0][1] + 1});
                dfs(b, a, m[0][0] - 1, m[0][1] + 1);
        }
        int c = get_node(m[0][0] + 2, m[0][1]);
        if (c != -1 && !visited[c])
        {
                uu.pb(a), vv.pb(c), aa.pb(m[0][0] + 1), bb.pb(m[0][1] - 1);
                fountains.insert({m[0][0] + 1, m[0][1] - 1});
                dfs(c, a, m[0][0] + 1, m[0][1] - 1);
        }
        if (visited.count() == x.size())
        {
                build(uu, vv, aa, bb);
                return 1;
        }
        return 0;

}

#ifdef __DEBUG__
int main()
{
        int n;
        cin >> n;
        vector<int> x(n), y(n);
        for (int i = 0; i < n; i++)
                cin >> x[i] >> y[i];
        if (construct_roads(x, y))
        {
                cout << "YES\n";
                for (int i = 0; i < uu.size(); i++)
                        cout << uu[i] << "-" << vv[i] << ": (" << aa[i] << ", " << bb[i] <<")\n";
        }
        else
        {
                cout << "NO\n";
        }
}

#endif

Compilation message

parks.cpp: In function 'void dfs(int, int, int, int)':
parks.cpp:63:54: warning: right operand of comma operator has no effect [-Wunused-value]
   63 |                         right_fx = top_fx, right_fy, top_fy;
      |                                                      ^~~~~~
parks.cpp:63:60: warning: right operand of comma operator has no effect [-Wunused-value]
   63 |                         right_fx = top_fx, right_fy, top_fy;
      |                                                            ^
parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:77:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |         for (int i = 0; i < x.size(); i++)
      |                         ~~^~~~~~~~~~
parks.cpp: In function 'void dfs(int, int, int, int)':
parks.cpp:64:27: warning: 'right_fy' may be used uninitialized in this function [-Wmaybe-uninitialized]
   64 |                 try_insert(node, right, right_fx, right_fy);
      |                 ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 97 ms 23144 KB Output is correct
10 Correct 10 ms 2600 KB Output is correct
11 Correct 46 ms 12516 KB Output is correct
12 Correct 13 ms 3836 KB Output is correct
13 Correct 21 ms 6412 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 340 KB Output is correct
16 Correct 95 ms 23236 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 97 ms 23144 KB Output is correct
10 Correct 10 ms 2600 KB Output is correct
11 Correct 46 ms 12516 KB Output is correct
12 Correct 13 ms 3836 KB Output is correct
13 Correct 21 ms 6412 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 340 KB Output is correct
16 Correct 95 ms 23236 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Incorrect 1 ms 300 KB b[4] = 0 is not an odd integer
20 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 97 ms 23144 KB Output is correct
10 Correct 10 ms 2600 KB Output is correct
11 Correct 46 ms 12516 KB Output is correct
12 Correct 13 ms 3836 KB Output is correct
13 Correct 21 ms 6412 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 340 KB Output is correct
16 Correct 95 ms 23236 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Incorrect 1 ms 300 KB b[4] = 0 is not an odd integer
20 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 97 ms 23144 KB Output is correct
10 Correct 10 ms 2600 KB Output is correct
11 Correct 46 ms 12516 KB Output is correct
12 Correct 13 ms 3836 KB Output is correct
13 Correct 21 ms 6412 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 340 KB Output is correct
16 Correct 95 ms 23236 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 260 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 241 ms 70004 KB Output is correct
21 Correct 228 ms 50892 KB Output is correct
22 Correct 243 ms 69628 KB Output is correct
23 Correct 178 ms 37148 KB Output is correct
24 Correct 56 ms 9456 KB Output is correct
25 Correct 56 ms 9328 KB Output is correct
26 Correct 53 ms 9344 KB Output is correct
27 Correct 180 ms 30792 KB Output is correct
28 Correct 188 ms 30784 KB Output is correct
29 Correct 230 ms 30796 KB Output is correct
30 Correct 235 ms 30828 KB Output is correct
31 Correct 1 ms 212 KB Output is correct
32 Incorrect 7 ms 1108 KB Solution announced impossible, but it is possible.
33 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 97 ms 23144 KB Output is correct
10 Correct 10 ms 2600 KB Output is correct
11 Correct 46 ms 12516 KB Output is correct
12 Correct 13 ms 3836 KB Output is correct
13 Correct 21 ms 6412 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 340 KB Output is correct
16 Correct 95 ms 23236 KB Output is correct
17 Correct 233 ms 47260 KB Output is correct
18 Incorrect 260 ms 43596 KB b[149999] = 0 is not an odd integer
19 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 97 ms 23144 KB Output is correct
10 Correct 10 ms 2600 KB Output is correct
11 Correct 46 ms 12516 KB Output is correct
12 Correct 13 ms 3836 KB Output is correct
13 Correct 21 ms 6412 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 340 KB Output is correct
16 Correct 95 ms 23236 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Incorrect 1 ms 300 KB b[4] = 0 is not an odd integer
20 Halted 0 ms 0 KB -