oj.uz

Submission #761485

# Submission time Handle Problem Language Result Execution time Memory
761485 2023-06-19T19:13:16 Z caganyanmaz Fountain Parks (IOI21_parks) C++17
5 / 100
 259 ms 61268 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);
        try_insert(a, b, m[0][0] - 1, m[0][1] + 1);
        int c = get_node(m[0][0] + 2, m[0][1]);
        try_insert(a, c, 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 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 94 ms 19268 KB Output is correct
10 Correct 8 ms 2260 KB Output is correct
11 Correct 45 ms 10424 KB Output is correct
12 Correct 12 ms 3232 KB Output is correct
13 Correct 20 ms 5100 KB Output is correct
14 Correct 1 ms 308 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 114 ms 19304 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 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 94 ms 19268 KB Output is correct
10 Correct 8 ms 2260 KB Output is correct
11 Correct 45 ms 10424 KB Output is correct
12 Correct 12 ms 3232 KB Output is correct
13 Correct 20 ms 5100 KB Output is correct
14 Correct 1 ms 308 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 114 ms 19304 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Incorrect 0 ms 212 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 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 94 ms 19268 KB Output is correct
10 Correct 8 ms 2260 KB Output is correct
11 Correct 45 ms 10424 KB Output is correct
12 Correct 12 ms 3232 KB Output is correct
13 Correct 20 ms 5100 KB Output is correct
14 Correct 1 ms 308 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 114 ms 19304 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Incorrect 0 ms 212 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 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 94 ms 19268 KB Output is correct
10 Correct 8 ms 2260 KB Output is correct
11 Correct 45 ms 10424 KB Output is correct
12 Correct 12 ms 3232 KB Output is correct
13 Correct 20 ms 5100 KB Output is correct
14 Correct 1 ms 308 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 114 ms 19304 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 223 ms 61268 KB Output is correct
21 Correct 217 ms 45444 KB Output is correct
22 Correct 259 ms 61076 KB Output is correct
23 Correct 169 ms 31304 KB Output is correct
24 Correct 56 ms 7684 KB Output is correct
25 Correct 57 ms 7668 KB Output is correct
26 Correct 52 ms 7680 KB Output is correct
27 Correct 178 ms 29136 KB Output is correct
28 Correct 193 ms 29148 KB Output is correct
29 Correct 228 ms 29044 KB Output is correct
30 Correct 226 ms 29060 KB Output is correct
31 Correct 0 ms 212 KB Output is correct
32 Incorrect 5 ms 852 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 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 94 ms 19268 KB Output is correct
10 Correct 8 ms 2260 KB Output is correct
11 Correct 45 ms 10424 KB Output is correct
12 Correct 12 ms 3232 KB Output is correct
13 Correct 20 ms 5100 KB Output is correct
14 Correct 1 ms 308 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 114 ms 19304 KB Output is correct
17 Correct 214 ms 38908 KB Output is correct
18 Incorrect 205 ms 36700 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 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 94 ms 19268 KB Output is correct
10 Correct 8 ms 2260 KB Output is correct
11 Correct 45 ms 10424 KB Output is correct
12 Correct 12 ms 3232 KB Output is correct
13 Correct 20 ms 5100 KB Output is correct
14 Correct 1 ms 308 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 114 ms 19304 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Incorrect 0 ms 212 KB b[4] = 0 is not an odd integer
20 Halted 0 ms 0 KB -