oj.uz

Submission #1058917

# Submission time Handle Problem Language Result Execution time Memory
1058917 2024-08-14T15:04:03 Z RaresFelix Fountain Parks (IOI21_parks) C++17
0 / 100
 0 ms 348 KB 
#include "parks.h"
#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;
using ii = pair<int, int>;

int DX[] = {-1, 0, 1, 0};
int DY[] = {0, 1, 0, -1};
const int MV = 1e9;

int construct_roads(vi x, vi y) {
    auto get_bench_coord = [&](int u, int v) -> pair<ii, ii> {
        int xcm = (x[u] + x[v]) / 2, ycm = (y[u] + y[v]) / 2;
        int dx = 2 - abs(x[u] - x[v]), dy = 2 - abs(y[u] - y[v]);
        return make_pair(ii{xcm - dx / 2, ycm - dy / 2}, ii{xcm + dx / 2, ycm + dy / 2});
    };
    int n = x.size();

    vector<ii> B;
    map<ii, int> Id;

    for(int i = 0; i < n; ++i) 
        Id[ii{x[i], y[i]}] = i;

    for(int i = 0; i < n; ++i) {
        for(int d = 0; d < 4; ++d) {
            int nx = x[i] + 2 * DX[d], ny = y[i] + 2 * DY[d];
            if(Id.count({nx, ny})) {
                int u = Id[{nx, ny}];
                auto [a, b] = get_bench_coord(u, i);
                B.push_back(a);
                B.push_back(b);
            }
        }
    }
    sort(B.begin(), B.end());
    B.resize(unique(B.begin(), B.end()) - B.begin());
    map<ii, int> IdB;
    int m = B.size();
    for(int i = 0; i < m; ++i) {
        IdB[B[i]] = i;
    }
    vi U, V, RA, RB;
    for(int i = 0; i < m; ++i) {
        auto [x, y] = B[i];
        int tip = (((x + MV) / 2) & 1 + ((y + MV) / 2) & 1) % 2;
        if(tip) {
            //leg la ceva vertical
            int x1, y1, x2, y2;
            x1 = x2 = x + 1;
            y1 = y - 1; y2 = y + 1;
            if(Id.count({x1, y1}) && Id.count({x2, y2})) {
                int u = Id[{x1, y1}], v = Id[{x2, y2}];
                U.push_back(u);
                V.push_back(v);
                RA.push_back(x);
                RB.push_back(y);
                continue;
            }
            x1 = x2 = x - 1;
            y1 = y - 1; y2 = y + 1;
            if(Id.count({x1, y1}) && Id.count({x2, y2})) {
                int u = Id[{x1, y1}], v = Id[{x2, y2}];
                U.push_back(u);
                V.push_back(v);
                RA.push_back(x);
                RB.push_back(y);
                continue;
            }
        } else {
            //leg la ceva orizontal
            int x1, y1, x2, y2;
            y1 = y2 = y + 1;
            x1 = x - 1; x2 = x + 1;
            if(Id.count({x1, y1}) && Id.count({x2, y2})) {
                int u = Id[{x1, y1}], v = Id[{x2, y2}];
                U.push_back(u);
                V.push_back(v);
                RA.push_back(x);
                RB.push_back(y);
                continue;
            }
            y1 = y2 = y - 1;
            x1 = x - 1; x2 = x + 1;
            if(Id.count({x1, y1}) && Id.count({x2, y2})) {
                int u = Id[{x1, y1}], v = Id[{x2, y2}];
                U.push_back(u);
                V.push_back(v);
                RA.push_back(x);
                RB.push_back(y);
                continue;
            }
        }
    }
    build(U, V, RA, RB);
    return 1;
}

Compilation message

parks.cpp: In function 'int construct_roads(vi, vi)':
parks.cpp:48:39: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
   48 |         int tip = (((x + MV) / 2) & 1 + ((y + MV) / 2) & 1) % 2;
      |                                     ~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Given structure is not connected: There is no path between vertices 0 and 1
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Given structure is not connected: There is no path between vertices 0 and 1
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Given structure is not connected: There is no path between vertices 0 and 1
3 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Given structure is not connected: There is no path between vertices 0 and 1
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Given structure is not connected: There is no path between vertices 0 and 1
3 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Given structure is not connected: There is no path between vertices 0 and 1
3 Halted 0 ms 0 KB -