oj.uz

Submission #441432

# Submission time Handle Problem Language Result Execution time Memory
441432 2021-07-05T07:35:43 Z SorahISA Fountain Parks (IOI21_parks) C++17
5 / 100
 891 ms 68496 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[u[i]] + 1}]) b[i] = Y[u[i]] + 1;
            else if (!bench[{midX, Y[v[i]] - 1}]) b[i] = Y[v[i]] - 1;
            bench[{a[i], b[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 5708 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 3 ms 5708 KB Output is correct
9 Correct 343 ms 37008 KB Output is correct
10 Correct 21 ms 9164 KB Output is correct
11 Correct 115 ms 23272 KB Output is correct
12 Correct 31 ms 10820 KB Output is correct
13 Correct 63 ms 15420 KB Output is correct
14 Correct 5 ms 5964 KB Output is correct
15 Correct 6 ms 6092 KB Output is correct
16 Correct 356 ms 37196 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5708 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 3 ms 5708 KB Output is correct
9 Correct 343 ms 37008 KB Output is correct
10 Correct 21 ms 9164 KB Output is correct
11 Correct 115 ms 23272 KB Output is correct
12 Correct 31 ms 10820 KB Output is correct
13 Correct 63 ms 15420 KB Output is correct
14 Correct 5 ms 5964 KB Output is correct
15 Correct 6 ms 6092 KB Output is correct
16 Correct 356 ms 37196 KB Output is correct
17 Correct 3 ms 5708 KB Output is correct
18 Correct 3 ms 5708 KB Output is correct
19 Correct 3 ms 5708 KB Output is correct
20 Incorrect 3 ms 5708 KB Tree (a[6], b[6]) = (3, -1) is not adjacent to edge between u[6]=3 @(2, 4) and v[6]=6 @(4, 4)
21 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5708 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 3 ms 5708 KB Output is correct
9 Correct 343 ms 37008 KB Output is correct
10 Correct 21 ms 9164 KB Output is correct
11 Correct 115 ms 23272 KB Output is correct
12 Correct 31 ms 10820 KB Output is correct
13 Correct 63 ms 15420 KB Output is correct
14 Correct 5 ms 5964 KB Output is correct
15 Correct 6 ms 6092 KB Output is correct
16 Correct 356 ms 37196 KB Output is correct
17 Correct 3 ms 5708 KB Output is correct
18 Correct 3 ms 5708 KB Output is correct
19 Correct 3 ms 5708 KB Output is correct
20 Incorrect 3 ms 5708 KB Tree (a[6], b[6]) = (3, -1) is not adjacent to edge between u[6]=3 @(2, 4) and v[6]=6 @(4, 4)
21 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5708 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 3 ms 5708 KB Output is correct
9 Correct 343 ms 37008 KB Output is correct
10 Correct 21 ms 9164 KB Output is correct
11 Correct 115 ms 23272 KB Output is correct
12 Correct 31 ms 10820 KB Output is correct
13 Correct 63 ms 15420 KB Output is correct
14 Correct 5 ms 5964 KB Output is correct
15 Correct 6 ms 6092 KB Output is correct
16 Correct 356 ms 37196 KB Output is correct
17 Correct 3 ms 5708 KB Output is correct
18 Correct 3 ms 5708 KB Output is correct
19 Correct 3 ms 5708 KB Output is correct
20 Incorrect 891 ms 55816 KB Tree (a[0], b[0]) = (195231, -1) is not adjacent to edge between u[0]=0 @(195232, 4772) and v[0]=183397 @(195230, 4772)
21 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5708 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 3 ms 5708 KB Output is correct
9 Correct 343 ms 37008 KB Output is correct
10 Correct 21 ms 9164 KB Output is correct
11 Correct 115 ms 23272 KB Output is correct
12 Correct 31 ms 10820 KB Output is correct
13 Correct 63 ms 15420 KB Output is correct
14 Correct 5 ms 5964 KB Output is correct
15 Correct 6 ms 6092 KB Output is correct
16 Correct 356 ms 37196 KB Output is correct
17 Correct 842 ms 68404 KB Output is correct
18 Correct 865 ms 68496 KB Output is correct
19 Incorrect 879 ms 56348 KB Tree (a[5], b[5]) = (30859, -1) is not adjacent to edge between u[5]=2 @(30860, 80858) and v[5]=32658 @(30858, 80858)
20 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5708 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 3 ms 5708 KB Output is correct
9 Correct 343 ms 37008 KB Output is correct
10 Correct 21 ms 9164 KB Output is correct
11 Correct 115 ms 23272 KB Output is correct
12 Correct 31 ms 10820 KB Output is correct
13 Correct 63 ms 15420 KB Output is correct
14 Correct 5 ms 5964 KB Output is correct
15 Correct 6 ms 6092 KB Output is correct
16 Correct 356 ms 37196 KB Output is correct
17 Correct 3 ms 5708 KB Output is correct
18 Correct 3 ms 5708 KB Output is correct
19 Correct 3 ms 5708 KB Output is correct
20 Incorrect 3 ms 5708 KB Tree (a[6], b[6]) = (3, -1) is not adjacent to edge between u[6]=3 @(2, 4) and v[6]=6 @(4, 4)
21 Halted 0 ms 0 KB -