oj.uz

Submission #441433

# Submission time Handle Problem Language Result Execution time Memory
441433 2021-07-05T07:40:13 Z SorahISA Fountain Parks (IOI21_parks) C++17
45 / 100
 983 ms 68408 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 == X[u[i]] % 4) a[i] = X[u[i]] + 1;
            else 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 4 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 4 ms 5708 KB Output is correct
9 Correct 341 ms 37004 KB Output is correct
10 Correct 21 ms 9204 KB Output is correct
11 Correct 117 ms 23260 KB Output is correct
12 Correct 32 ms 10820 KB Output is correct
13 Correct 62 ms 15452 KB Output is correct
14 Correct 5 ms 5964 KB Output is correct
15 Correct 6 ms 6092 KB Output is correct
16 Correct 348 ms 37012 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 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 4 ms 5708 KB Output is correct
9 Correct 341 ms 37004 KB Output is correct
10 Correct 21 ms 9204 KB Output is correct
11 Correct 117 ms 23260 KB Output is correct
12 Correct 32 ms 10820 KB Output is correct
13 Correct 62 ms 15452 KB Output is correct
14 Correct 5 ms 5964 KB Output is correct
15 Correct 6 ms 6092 KB Output is correct
16 Correct 348 ms 37012 KB Output is correct
17 Incorrect 4 ms 5708 KB Tree @(3, 3) appears more than once: for edges on positions 1 and 2
18 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 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 4 ms 5708 KB Output is correct
9 Correct 341 ms 37004 KB Output is correct
10 Correct 21 ms 9204 KB Output is correct
11 Correct 117 ms 23260 KB Output is correct
12 Correct 32 ms 10820 KB Output is correct
13 Correct 62 ms 15452 KB Output is correct
14 Correct 5 ms 5964 KB Output is correct
15 Correct 6 ms 6092 KB Output is correct
16 Correct 348 ms 37012 KB Output is correct
17 Incorrect 4 ms 5708 KB Tree @(3, 3) appears more than once: for edges on positions 1 and 2
18 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 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 4 ms 5708 KB Output is correct
9 Correct 341 ms 37004 KB Output is correct
10 Correct 21 ms 9204 KB Output is correct
11 Correct 117 ms 23260 KB Output is correct
12 Correct 32 ms 10820 KB Output is correct
13 Correct 62 ms 15452 KB Output is correct
14 Correct 5 ms 5964 KB Output is correct
15 Correct 6 ms 6092 KB Output is correct
16 Correct 348 ms 37012 KB Output is correct
17 Correct 4 ms 5708 KB Output is correct
18 Correct 4 ms 5708 KB Output is correct
19 Correct 4 ms 5708 KB Output is correct
20 Correct 791 ms 56028 KB Output is correct
21 Correct 916 ms 55904 KB Output is correct
22 Correct 875 ms 55980 KB Output is correct
23 Correct 715 ms 58952 KB Output is correct
24 Correct 826 ms 46488 KB Output is correct
25 Correct 681 ms 35604 KB Output is correct
26 Correct 686 ms 35612 KB Output is correct
27 Correct 983 ms 55932 KB Output is correct
28 Correct 847 ms 55992 KB Output is correct
29 Correct 906 ms 55884 KB Output is correct
30 Correct 863 ms 55852 KB Output is correct
31 Correct 3 ms 5708 KB Output is correct
32 Correct 36 ms 9636 KB Output is correct
33 Correct 210 ms 26584 KB Output is correct
34 Correct 761 ms 56332 KB Output is correct
35 Correct 16 ms 7208 KB Output is correct
36 Correct 96 ms 12816 KB Output is correct
37 Correct 283 ms 19220 KB Output is correct
38 Correct 252 ms 24756 KB Output is correct
39 Correct 385 ms 31508 KB Output is correct
40 Correct 545 ms 38444 KB Output is correct
41 Correct 720 ms 45588 KB Output is correct
42 Correct 889 ms 52384 KB Output is correct
43 Correct 3 ms 5708 KB Output is correct
44 Correct 3 ms 5708 KB Output is correct
45 Correct 3 ms 5796 KB Output is correct
46 Correct 3 ms 5708 KB Output is correct
47 Correct 3 ms 5708 KB Output is correct
48 Correct 4 ms 5708 KB Output is correct
49 Correct 3 ms 5708 KB Output is correct
50 Correct 4 ms 5708 KB Output is correct
51 Correct 4 ms 5800 KB Output is correct
52 Correct 3 ms 5708 KB Output is correct
53 Correct 4 ms 5708 KB Output is correct
54 Correct 6 ms 6092 KB Output is correct
55 Correct 7 ms 6220 KB Output is correct
56 Correct 363 ms 33716 KB Output is correct
57 Correct 634 ms 46060 KB Output is correct
58 Correct 603 ms 46080 KB Output is correct
59 Correct 3 ms 5708 KB Output is correct
60 Correct 3 ms 5708 KB Output is correct
61 Correct 3 ms 5708 KB Output is correct
62 Correct 904 ms 62752 KB Output is correct
63 Correct 899 ms 62764 KB Output is correct
64 Correct 876 ms 62492 KB Output is correct
65 Correct 8 ms 6348 KB Output is correct
66 Correct 15 ms 7040 KB Output is correct
67 Correct 368 ms 32228 KB Output is correct
68 Correct 643 ms 45356 KB Output is correct
69 Correct 936 ms 58500 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 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 4 ms 5708 KB Output is correct
9 Correct 341 ms 37004 KB Output is correct
10 Correct 21 ms 9204 KB Output is correct
11 Correct 117 ms 23260 KB Output is correct
12 Correct 32 ms 10820 KB Output is correct
13 Correct 62 ms 15452 KB Output is correct
14 Correct 5 ms 5964 KB Output is correct
15 Correct 6 ms 6092 KB Output is correct
16 Correct 348 ms 37012 KB Output is correct
17 Correct 813 ms 68360 KB Output is correct
18 Correct 832 ms 68408 KB Output is correct
19 Correct 797 ms 55892 KB Output is correct
20 Correct 789 ms 47408 KB Output is correct
21 Correct 796 ms 53932 KB Output is correct
22 Correct 4 ms 5708 KB Output is correct
23 Correct 87 ms 14088 KB Output is correct
24 Correct 33 ms 8376 KB Output is correct
25 Correct 214 ms 14752 KB Output is correct
26 Correct 303 ms 20536 KB Output is correct
27 Correct 342 ms 28052 KB Output is correct
28 Correct 450 ms 33588 KB Output is correct
29 Correct 589 ms 39084 KB Output is correct
30 Correct 831 ms 44460 KB Output is correct
31 Correct 855 ms 50040 KB Output is correct
32 Correct 906 ms 56348 KB Output is correct
33 Correct 898 ms 62668 KB Output is correct
34 Correct 9 ms 6604 KB Output is correct
35 Correct 15 ms 7160 KB Output is correct
36 Correct 371 ms 31744 KB Output is correct
37 Correct 647 ms 44428 KB Output is correct
38 Correct 915 ms 57080 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 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 4 ms 5708 KB Output is correct
9 Correct 341 ms 37004 KB Output is correct
10 Correct 21 ms 9204 KB Output is correct
11 Correct 117 ms 23260 KB Output is correct
12 Correct 32 ms 10820 KB Output is correct
13 Correct 62 ms 15452 KB Output is correct
14 Correct 5 ms 5964 KB Output is correct
15 Correct 6 ms 6092 KB Output is correct
16 Correct 348 ms 37012 KB Output is correct
17 Incorrect 4 ms 5708 KB Tree @(3, 3) appears more than once: for edges on positions 1 and 2
18 Halted 0 ms 0 KB -