oj.uz

Submission #441393

# Submission time Handle Problem Language Result Execution time Memory
441393 2021-07-05T06:40:37 Z SorahISA Fountain Parks (IOI21_parks) C++17
0 / 100
 1 ms 972 KB 
#include "parks.h"
#pragma GCC optimize("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;

// #define int long long
// #define double long double
using pii = pair<int, int>;
template<typename T>
using Prior = std::priority_queue<T>;
template<typename T>
using prior = std::priority_queue<T, vector<T>, greater<T>>;

// #define X first
// #define Y second
#define eb emplace_back
#define pb pop_back
#define pf pop_front
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)

namespace {

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 2E5 + 5;
const int dx[] = {1, 0, -1,  0};
const int dy[] = {0, 1,  0, -1};

map<pii, int> points;
vector<int> p(maxn);

int R(int x) {return x ^ p[x] ? p[x] = R(p[x]) : x;}
void U(int x, int y) {x = R(x), y = R(y); p[x] = y;}

} /// end of namespace

int construct_roads(vector<int> X, vector<int> Y) {
    int N = X.size();
    vector<int> u, v, a, b;
    
    if (N == 1) return build({}, {}, {}, {}), 1;
    
    iota(ALL(p), 0);
    for (int i = 0; i < N; ++i) points[{X[i], Y[i]}] = i+1;
    for (int i = 0; i < N; ++i) {
        for (int d = 0; d < 4; ++d) {
            int neighbor = points[{X[i] + dx[d], Y[i] + dy[d]}];
            if (neighbor) {
                U(i, neighbor-1);
                u.eb(i), v.eb(neighbor-1);
                if (X[i] == X[neighbor-1] and X[i] == 2) a.eb(1), b.eb(Y[i] + Y[neighbor-1] >> 1);
                if (X[i] == X[neighbor-1] and X[i] == 4) a.eb(5), b.eb(Y[i] + Y[neighbor-1] >> 1);
                if (Y[i] == Y[neighbor-1]) a.eb(3), b.eb(Y[i] + 1);
            }
        }
    }
    for (int i = 0; i < N; ++i) if (R(i) != R(0)) return 0;
    
    return build(u, v, a, b), 1;
}

Compilation message

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:52:77: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |                 if (X[i] == X[neighbor-1] and X[i] == 2) a.eb(1), b.eb(Y[i] + Y[neighbor-1] >> 1);
parks.cpp:53:77: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |                 if (X[i] == X[neighbor-1] and X[i] == 4) a.eb(5), b.eb(Y[i] + Y[neighbor-1] >> 1);

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 972 KB Output is correct
2 Incorrect 1 ms 972 KB Solution announced impossible, but it is possible.
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 972 KB Output is correct
2 Incorrect 1 ms 972 KB Solution announced impossible, but it is possible.
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 972 KB Output is correct
2 Incorrect 1 ms 972 KB Solution announced impossible, but it is possible.
3 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 972 KB Output is correct
2 Incorrect 1 ms 972 KB Solution announced impossible, but it is possible.
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 972 KB Output is correct
2 Incorrect 1 ms 972 KB Solution announced impossible, but it is possible.
3 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 972 KB Output is correct
2 Incorrect 1 ms 972 KB Solution announced impossible, but it is possible.
3 Halted 0 ms 0 KB -