oj.uz

Submission #441431

# Submission time Handle Problem Language Result Execution time Memory
441431 2021-07-05T07:33:12 Z SorahISA Fountain Parks (IOI21_parks) C++17
5 / 100
 876 ms 67944 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[] = {2, 0, -2,  0};
const int dy[] = {0, 2,  0, -2};

map<pii, int> fountain, bench;
// map<pii, vector<int>> candidate;
vector<int> p(maxn);

vector<int> adj[maxn];

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

} /// 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) fountain[{X[i], Y[i]}] = i+1;
    for (int i = 0; i < N; ++i) {
        for (int d = 0; d < 4; ++d) {
            int nei = fountain[{X[i] + dx[d], Y[i] + dy[d]}];
            if (nei-1 > i and U(i, nei-1)) u.eb(i), v.eb(nei-1);
        }
    }
    for (int i = 0; i < N; ++i) if (R(i) != R(0)) return 0;
    
    int M = u.size(); a.assign(M, -1), b.assign(M, -1);
    assert(M == N-1);
    
    // for (int i = 0; i < M; ++i) {
        // if (X[u[i]] == X[v[i]]) {
            // int midY = Y[u[i]] + Y[v[i]] >> 1;
            // candidate[{X[u[i]] + 1, midY}].eb(i);
            // candidate[{X[u[i]] - 1, midY}].eb(i);
        // }
        // else if (Y[u[i]] == Y[v[i]]) {
            // int midX = X[u[i]] + X[v[i]] >> 1;
            // candidate[{midX, Y[u[i]] + 1}].eb(i);
            // candidate[{midX, Y[u[i]] - 1}].eb(i);
        // }
    // }
    
    // for (auto [coord, vec] : candidate) {
        // if (vec.size() >= 2) {
            // for (auto x : vec) for (auto y : vec) {
                // if (x < y) adj[x].eb(y);
            // }
        // }
    // }
    
    for (int i = 0; i < M; ++i) {
        if (X[u[i]] == X[v[i]]) {
            int midY = Y[u[i]] + Y[v[i]] >> 1;
                 if (min(Y[u[i]], Y[v[i]]) % 4 == 0) a[i] = X[u[i]] + 1;
            else if (min(Y[u[i]], Y[v[i]]) % 4 == 2) a[i] = X[u[i]] - 1;
            b[i] = midY;
            bench[{a[i], b[i]}] = 1;
        }
    }
    
    for (int i = 0; i < M; ++i) {
        if (Y[u[i]] == Y[v[i]]) {
            int midX = X[u[i]] + X[v[i]] >> 1;
            a[i] = midX;
                 if (!bench[{midX, Y[i] + 1}]) b[i] = Y[i] + 1;
            else if (!bench[{midX, Y[i] - 1}]) b[i] = Y[i] - 1;
        }
    }
    
    return build(u, v, a, b), 1;
}

Compilation message

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:83:32: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   83 |             int midY = Y[u[i]] + Y[v[i]] >> 1;
parks.cpp:93:32: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   93 |             int midX = X[u[i]] + X[v[i]] >> 1;

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5676 KB Output is correct
2 Correct 3 ms 5708 KB Output is correct
3 Correct 3 ms 5708 KB Output is correct
4 Correct 3 ms 5708 KB Output is correct
5 Correct 3 ms 5708 KB Output is correct
6 Correct 3 ms 5708 KB Output is correct
7 Correct 3 ms 5708 KB Output is correct
8 Correct 4 ms 5708 KB Output is correct
9 Correct 370 ms 37144 KB Output is correct
10 Correct 24 ms 9292 KB Output is correct
11 Correct 129 ms 23180 KB Output is correct
12 Correct 34 ms 10840 KB Output is correct
13 Correct 66 ms 15420 KB Output is correct
14 Correct 4 ms 5964 KB Output is correct
15 Correct 6 ms 6092 KB Output is correct
16 Correct 351 ms 37112 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5676 KB Output is correct
2 Correct 3 ms 5708 KB Output is correct
3 Correct 3 ms 5708 KB Output is correct
4 Correct 3 ms 5708 KB Output is correct
5 Correct 3 ms 5708 KB Output is correct
6 Correct 3 ms 5708 KB Output is correct
7 Correct 3 ms 5708 KB Output is correct
8 Correct 4 ms 5708 KB Output is correct
9 Correct 370 ms 37144 KB Output is correct
10 Correct 24 ms 9292 KB Output is correct
11 Correct 129 ms 23180 KB Output is correct
12 Correct 34 ms 10840 KB Output is correct
13 Correct 66 ms 15420 KB Output is correct
14 Correct 4 ms 5964 KB Output is correct
15 Correct 6 ms 6092 KB Output is correct
16 Correct 351 ms 37112 KB Output is correct
17 Correct 4 ms 5708 KB Output is correct
18 Incorrect 4 ms 5708 KB Tree (a[1], b[1]) = (3, 7) is not adjacent to edge between u[1]=0 @(4, 4) and v[1]=2 @(2, 4)
19 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5676 KB Output is correct
2 Correct 3 ms 5708 KB Output is correct
3 Correct 3 ms 5708 KB Output is correct
4 Correct 3 ms 5708 KB Output is correct
5 Correct 3 ms 5708 KB Output is correct
6 Correct 3 ms 5708 KB Output is correct
7 Correct 3 ms 5708 KB Output is correct
8 Correct 4 ms 5708 KB Output is correct
9 Correct 370 ms 37144 KB Output is correct
10 Correct 24 ms 9292 KB Output is correct
11 Correct 129 ms 23180 KB Output is correct
12 Correct 34 ms 10840 KB Output is correct
13 Correct 66 ms 15420 KB Output is correct
14 Correct 4 ms 5964 KB Output is correct
15 Correct 6 ms 6092 KB Output is correct
16 Correct 351 ms 37112 KB Output is correct
17 Correct 4 ms 5708 KB Output is correct
18 Incorrect 4 ms 5708 KB Tree (a[1], b[1]) = (3, 7) is not adjacent to edge between u[1]=0 @(4, 4) and v[1]=2 @(2, 4)
19 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5676 KB Output is correct
2 Correct 3 ms 5708 KB Output is correct
3 Correct 3 ms 5708 KB Output is correct
4 Correct 3 ms 5708 KB Output is correct
5 Correct 3 ms 5708 KB Output is correct
6 Correct 3 ms 5708 KB Output is correct
7 Correct 3 ms 5708 KB Output is correct
8 Correct 4 ms 5708 KB Output is correct
9 Correct 370 ms 37144 KB Output is correct
10 Correct 24 ms 9292 KB Output is correct
11 Correct 129 ms 23180 KB Output is correct
12 Correct 34 ms 10840 KB Output is correct
13 Correct 66 ms 15420 KB Output is correct
14 Correct 4 ms 5964 KB Output is correct
15 Correct 6 ms 6092 KB Output is correct
16 Correct 351 ms 37112 KB Output is correct
17 Incorrect 4 ms 5708 KB Tree (a[1], b[1]) = (199999, 5) is not adjacent to edge between u[1]=0 @(200000, 2) and v[1]=2 @(199998, 2)
18 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5676 KB Output is correct
2 Correct 3 ms 5708 KB Output is correct
3 Correct 3 ms 5708 KB Output is correct
4 Correct 3 ms 5708 KB Output is correct
5 Correct 3 ms 5708 KB Output is correct
6 Correct 3 ms 5708 KB Output is correct
7 Correct 3 ms 5708 KB Output is correct
8 Correct 4 ms 5708 KB Output is correct
9 Correct 370 ms 37144 KB Output is correct
10 Correct 24 ms 9292 KB Output is correct
11 Correct 129 ms 23180 KB Output is correct
12 Correct 34 ms 10840 KB Output is correct
13 Correct 66 ms 15420 KB Output is correct
14 Correct 4 ms 5964 KB Output is correct
15 Correct 6 ms 6092 KB Output is correct
16 Correct 351 ms 37112 KB Output is correct
17 Incorrect 876 ms 67944 KB Tree (a[1], b[1]) = (82421, 52499) is not adjacent to edge between u[1]=0 @(82422, 100002) and v[1]=148989 @(82420, 100002)
18 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5676 KB Output is correct
2 Correct 3 ms 5708 KB Output is correct
3 Correct 3 ms 5708 KB Output is correct
4 Correct 3 ms 5708 KB Output is correct
5 Correct 3 ms 5708 KB Output is correct
6 Correct 3 ms 5708 KB Output is correct
7 Correct 3 ms 5708 KB Output is correct
8 Correct 4 ms 5708 KB Output is correct
9 Correct 370 ms 37144 KB Output is correct
10 Correct 24 ms 9292 KB Output is correct
11 Correct 129 ms 23180 KB Output is correct
12 Correct 34 ms 10840 KB Output is correct
13 Correct 66 ms 15420 KB Output is correct
14 Correct 4 ms 5964 KB Output is correct
15 Correct 6 ms 6092 KB Output is correct
16 Correct 351 ms 37112 KB Output is correct
17 Correct 4 ms 5708 KB Output is correct
18 Incorrect 4 ms 5708 KB Tree (a[1], b[1]) = (3, 7) is not adjacent to edge between u[1]=0 @(4, 4) and v[1]=2 @(2, 4)
19 Halted 0 ms 0 KB -