oj.uz

Submission #560490

# Submission time Handle Problem Language Result Execution time Memory
560490 2022-05-11T14:13:23 Z kartel Fountain Parks (IOI21_parks) C++17
55 / 100
 1402 ms 314080 KB 
#include <bits/stdc++.h>
//#include "grader.cpp"
#include "parks.h"
#define F first
#define S second
#define pb push_back
#define sz(x) (int)x.size()
#define el "\n"
#define all(x) (x).begin(), (x).end()

#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-O3")
#pragma GCC optimize("Ofast")

using namespace std;
typedef long long ll;

const int N = 2e6 + 500;

mt19937 rnd(time(0));

const int steps[4][2] = {{0, 2}, {2, 0}, {0, -2}, {-2, 0}};

int pr[N];
int cmp[2 * N], to[2 * N];
vector <int> g[2 * N], gr[2 * N], ord;
bool mk[2 * N];

int f(int v) {return (pr[v] == v ? v : pr[v] = f(pr[v]));}
void link(int v, int u) {
    v = f(v); u = f(u);
    if (v == u) {
        return;
    }
    pr[u] = v;
}

int nt(int x) {return (x < N ? x + N : x - N);}

void add_impl(int a, int b) {
    int na = nt(a), nb = nt(b);

    g[na].pb(b); gr[b].pb(na);
    g[nb].pb(a); gr[a].pb(nb);
}

void dfs(int v) {
    mk[v] = 1;
    for (auto u : g[v]) {
        if (mk[u]) {
            continue;
        }
        dfs(u);
    }
    ord.pb(v);
}

int construct_roads(vector <int> x, vector <int> y) {
    int n = sz(x);
    map <pair <int, int>, int> mp;
    vector <pair <int, int> > r;
    vector <int> pm(n);
    iota(all(pm), 0);
    shuffle(all(pm), rnd);

    bool sd = 1;
    for (int i = 0; i < n; i++) {
        mp[{x[i], y[i]}] = i;
        pr[i] = i;
        sd &= (x[i] >= 2 && x[i] <= 4);
    }

    for (auto i : pm) {
        for (int j = 0; j < 4; j++) {
            int cx = x[i] + steps[j][0];
            int cy = y[i] + steps[j][1];

            if (mp.count({cx, cy}) && f(i) != f(mp[{cx, cy}])) {
                int to = mp[{cx, cy}];
                link(i, to);
                r.pb({i, to});
            }
        }
    }
    sort(all(r));
    r.resize(unique(all(r)) - r.begin());

    for (int i = 0; i < n; i++) {
        if (f(i) != f(0)) {
            return 0;
        }
    }
    vector <int> u, v, A, B;
    map <pair <int, int>, vector <int> > e;

    for (int i = 0; i < sz(r); i++) {
        int a = r[i].F, b = r[i].S;
        u.pb(a); v.pb(b);
        if (abs(x[a] - x[b]) == 0) {
            int lx = x[a];
            int ly = min(y[a], y[b]);

            e[{lx - 1, ly + 1}].pb(i);
            e[{lx + 1, ly + 1}].pb(nt(i));
        } else {
            int lx = min(x[a], x[b]);
            int ly = y[a];

            e[{lx + 1, ly + 1}].pb(i);
            e[{lx + 1, ly - 1}].pb(nt(i));
        }
    }
    for (auto [p, v] : e) {
        int x = p.F, y = p.S;
        if (sz(v) == 1) {
            continue;
        }
        for (auto a : v) {
            for (auto b : v) {
                if (a == b) {
                    continue;
                }
                add_impl(a, b);
            }
        }
    }

    for (int i = 0; i < 2 * N; i++) {
        cmp[i] = -1;
        if (mk[i]) {
            continue;
        }
        dfs(i);
    }
    reverse(all(ord));

    int C = 0;
    for (auto v : ord) {
        function <void(int)> dfsr = [&](int v) {
            if (cmp[v] != -1) {
                return;
            }
            cmp[v] = C;
            for (auto u : gr[v]) {
                dfsr(u);
            }
        };

        dfsr(v);
        C++;
    }

    for (int i = 0; i < N; i++) {
        if (cmp[i] == cmp[nt(i)]) {
            return 0;
        }
        to[i] = (cmp[i] > cmp[nt(i)]);
    }

    for (int i = 0; i < sz(r); i++) {
        int a = r[i].F, b = r[i].S;
        if (abs(x[a] - x[b]) == 0) {
            int lx = x[a];
            int ly = min(y[a], y[b]);

            if (to[i]) {
                A.pb(lx + 1);
            } else {
                A.pb(lx - 1);
            }
            B.pb(ly + 1);
        } else {
            int lx = min(x[a], x[b]);
            int ly = y[a];

            if (to[i]) {
                B.pb(ly - 1);
            } else {
                B.pb(ly + 1);
            }
            A.pb(lx + 1);
        }
    }

    build(u, v, A, B);
    return 1;
}

Compilation message

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:114:13: warning: unused variable 'x' [-Wunused-variable]
  114 |         int x = p.F, y = p.S;
      |             ^
parks.cpp:114:22: warning: unused variable 'y' [-Wunused-variable]
  114 |         int x = p.F, y = p.S;
      |                      ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 231312 KB Output is correct
2 Correct 148 ms 231356 KB Output is correct
3 Correct 92 ms 188116 KB Output is correct
4 Correct 156 ms 231356 KB Output is correct
5 Correct 177 ms 231424 KB Output is correct
6 Correct 88 ms 188104 KB Output is correct
7 Correct 89 ms 188176 KB Output is correct
8 Correct 88 ms 188192 KB Output is correct
9 Correct 572 ms 267748 KB Output is correct
10 Correct 172 ms 234948 KB Output is correct
11 Correct 323 ms 250856 KB Output is correct
12 Correct 196 ms 236992 KB Output is correct
13 Correct 165 ms 192684 KB Output is correct
14 Correct 94 ms 188232 KB Output is correct
15 Correct 91 ms 188400 KB Output is correct
16 Correct 533 ms 267944 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 231312 KB Output is correct
2 Correct 148 ms 231356 KB Output is correct
3 Correct 92 ms 188116 KB Output is correct
4 Correct 156 ms 231356 KB Output is correct
5 Correct 177 ms 231424 KB Output is correct
6 Correct 88 ms 188104 KB Output is correct
7 Correct 89 ms 188176 KB Output is correct
8 Correct 88 ms 188192 KB Output is correct
9 Correct 572 ms 267748 KB Output is correct
10 Correct 172 ms 234948 KB Output is correct
11 Correct 323 ms 250856 KB Output is correct
12 Correct 196 ms 236992 KB Output is correct
13 Correct 165 ms 192684 KB Output is correct
14 Correct 94 ms 188232 KB Output is correct
15 Correct 91 ms 188400 KB Output is correct
16 Correct 533 ms 267944 KB Output is correct
17 Correct 156 ms 231356 KB Output is correct
18 Correct 152 ms 231404 KB Output is correct
19 Correct 178 ms 231404 KB Output is correct
20 Correct 155 ms 231396 KB Output is correct
21 Correct 90 ms 188108 KB Output is correct
22 Correct 163 ms 231392 KB Output is correct
23 Correct 1323 ms 304540 KB Output is correct
24 Correct 161 ms 231396 KB Output is correct
25 Correct 158 ms 231716 KB Output is correct
26 Correct 92 ms 188520 KB Output is correct
27 Correct 94 ms 188568 KB Output is correct
28 Correct 527 ms 260468 KB Output is correct
29 Correct 711 ms 274896 KB Output is correct
30 Correct 1010 ms 289880 KB Output is correct
31 Correct 1303 ms 304128 KB Output is correct
32 Correct 156 ms 231348 KB Output is correct
33 Correct 150 ms 231296 KB Output is correct
34 Correct 150 ms 231340 KB Output is correct
35 Correct 87 ms 188184 KB Output is correct
36 Correct 89 ms 188188 KB Output is correct
37 Correct 159 ms 231396 KB Output is correct
38 Correct 151 ms 231352 KB Output is correct
39 Correct 151 ms 231376 KB Output is correct
40 Correct 149 ms 231476 KB Output is correct
41 Correct 88 ms 188108 KB Output is correct
42 Correct 157 ms 231448 KB Output is correct
43 Correct 96 ms 188376 KB Output is correct
44 Correct 99 ms 188528 KB Output is correct
45 Correct 600 ms 269288 KB Output is correct
46 Correct 917 ms 287288 KB Output is correct
47 Correct 904 ms 286612 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 231312 KB Output is correct
2 Correct 148 ms 231356 KB Output is correct
3 Correct 92 ms 188116 KB Output is correct
4 Correct 156 ms 231356 KB Output is correct
5 Correct 177 ms 231424 KB Output is correct
6 Correct 88 ms 188104 KB Output is correct
7 Correct 89 ms 188176 KB Output is correct
8 Correct 88 ms 188192 KB Output is correct
9 Correct 572 ms 267748 KB Output is correct
10 Correct 172 ms 234948 KB Output is correct
11 Correct 323 ms 250856 KB Output is correct
12 Correct 196 ms 236992 KB Output is correct
13 Correct 165 ms 192684 KB Output is correct
14 Correct 94 ms 188232 KB Output is correct
15 Correct 91 ms 188400 KB Output is correct
16 Correct 533 ms 267944 KB Output is correct
17 Correct 156 ms 231356 KB Output is correct
18 Correct 152 ms 231404 KB Output is correct
19 Correct 178 ms 231404 KB Output is correct
20 Correct 155 ms 231396 KB Output is correct
21 Correct 90 ms 188108 KB Output is correct
22 Correct 163 ms 231392 KB Output is correct
23 Correct 1323 ms 304540 KB Output is correct
24 Correct 161 ms 231396 KB Output is correct
25 Correct 158 ms 231716 KB Output is correct
26 Correct 92 ms 188520 KB Output is correct
27 Correct 94 ms 188568 KB Output is correct
28 Correct 527 ms 260468 KB Output is correct
29 Correct 711 ms 274896 KB Output is correct
30 Correct 1010 ms 289880 KB Output is correct
31 Correct 1303 ms 304128 KB Output is correct
32 Correct 156 ms 231348 KB Output is correct
33 Correct 150 ms 231296 KB Output is correct
34 Correct 150 ms 231340 KB Output is correct
35 Correct 87 ms 188184 KB Output is correct
36 Correct 89 ms 188188 KB Output is correct
37 Correct 159 ms 231396 KB Output is correct
38 Correct 151 ms 231352 KB Output is correct
39 Correct 151 ms 231376 KB Output is correct
40 Correct 149 ms 231476 KB Output is correct
41 Correct 88 ms 188108 KB Output is correct
42 Correct 157 ms 231448 KB Output is correct
43 Correct 96 ms 188376 KB Output is correct
44 Correct 99 ms 188528 KB Output is correct
45 Correct 600 ms 269288 KB Output is correct
46 Correct 917 ms 287288 KB Output is correct
47 Correct 904 ms 286612 KB Output is correct
48 Correct 158 ms 231456 KB Output is correct
49 Correct 152 ms 231508 KB Output is correct
50 Correct 160 ms 231404 KB Output is correct
51 Correct 152 ms 231312 KB Output is correct
52 Correct 159 ms 231312 KB Output is correct
53 Correct 150 ms 231392 KB Output is correct
54 Correct 151 ms 231320 KB Output is correct
55 Incorrect 1326 ms 288192 KB Solution announced impossible, but it is possible.
56 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 231312 KB Output is correct
2 Correct 148 ms 231356 KB Output is correct
3 Correct 92 ms 188116 KB Output is correct
4 Correct 156 ms 231356 KB Output is correct
5 Correct 177 ms 231424 KB Output is correct
6 Correct 88 ms 188104 KB Output is correct
7 Correct 89 ms 188176 KB Output is correct
8 Correct 88 ms 188192 KB Output is correct
9 Correct 572 ms 267748 KB Output is correct
10 Correct 172 ms 234948 KB Output is correct
11 Correct 323 ms 250856 KB Output is correct
12 Correct 196 ms 236992 KB Output is correct
13 Correct 165 ms 192684 KB Output is correct
14 Correct 94 ms 188232 KB Output is correct
15 Correct 91 ms 188400 KB Output is correct
16 Correct 533 ms 267944 KB Output is correct
17 Correct 171 ms 231352 KB Output is correct
18 Correct 148 ms 231388 KB Output is correct
19 Correct 91 ms 188164 KB Output is correct
20 Correct 1270 ms 314080 KB Output is correct
21 Correct 1262 ms 310740 KB Output is correct
22 Correct 1280 ms 310264 KB Output is correct
23 Correct 887 ms 293320 KB Output is correct
24 Correct 483 ms 205408 KB Output is correct
25 Correct 725 ms 207604 KB Output is correct
26 Correct 635 ms 207716 KB Output is correct
27 Correct 1163 ms 304348 KB Output is correct
28 Correct 1129 ms 304324 KB Output is correct
29 Correct 1180 ms 304164 KB Output is correct
30 Correct 1133 ms 304344 KB Output is correct
31 Correct 152 ms 231436 KB Output is correct
32 Correct 209 ms 236816 KB Output is correct
33 Correct 241 ms 196844 KB Output is correct
34 Correct 1217 ms 312596 KB Output is correct
35 Correct 104 ms 189268 KB Output is correct
36 Correct 179 ms 193080 KB Output is correct
37 Correct 328 ms 197996 KB Output is correct
38 Correct 514 ms 261656 KB Output is correct
39 Correct 724 ms 272936 KB Output is correct
40 Correct 976 ms 284920 KB Output is correct
41 Correct 1152 ms 296136 KB Output is correct
42 Correct 1388 ms 308216 KB Output is correct
43 Correct 152 ms 231312 KB Output is correct
44 Correct 153 ms 231352 KB Output is correct
45 Correct 165 ms 231412 KB Output is correct
46 Correct 90 ms 188140 KB Output is correct
47 Correct 88 ms 188136 KB Output is correct
48 Correct 159 ms 231384 KB Output is correct
49 Correct 153 ms 231396 KB Output is correct
50 Correct 155 ms 231416 KB Output is correct
51 Correct 149 ms 231340 KB Output is correct
52 Correct 108 ms 188156 KB Output is correct
53 Correct 157 ms 231324 KB Output is correct
54 Correct 92 ms 188400 KB Output is correct
55 Correct 90 ms 188492 KB Output is correct
56 Correct 635 ms 268688 KB Output is correct
57 Correct 912 ms 285808 KB Output is correct
58 Correct 906 ms 285344 KB Output is correct
59 Correct 87 ms 188224 KB Output is correct
60 Correct 150 ms 231416 KB Output is correct
61 Correct 109 ms 188172 KB Output is correct
62 Correct 1060 ms 304340 KB Output is correct
63 Correct 1098 ms 304360 KB Output is correct
64 Correct 1037 ms 303848 KB Output is correct
65 Correct 92 ms 188612 KB Output is correct
66 Correct 100 ms 188936 KB Output is correct
67 Correct 631 ms 268848 KB Output is correct
68 Correct 981 ms 287452 KB Output is correct
69 Correct 1355 ms 306372 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 231312 KB Output is correct
2 Correct 148 ms 231356 KB Output is correct
3 Correct 92 ms 188116 KB Output is correct
4 Correct 156 ms 231356 KB Output is correct
5 Correct 177 ms 231424 KB Output is correct
6 Correct 88 ms 188104 KB Output is correct
7 Correct 89 ms 188176 KB Output is correct
8 Correct 88 ms 188192 KB Output is correct
9 Correct 572 ms 267748 KB Output is correct
10 Correct 172 ms 234948 KB Output is correct
11 Correct 323 ms 250856 KB Output is correct
12 Correct 196 ms 236992 KB Output is correct
13 Correct 165 ms 192684 KB Output is correct
14 Correct 94 ms 188232 KB Output is correct
15 Correct 91 ms 188400 KB Output is correct
16 Correct 533 ms 267944 KB Output is correct
17 Correct 1092 ms 305020 KB Output is correct
18 Correct 1035 ms 304944 KB Output is correct
19 Correct 1266 ms 313172 KB Output is correct
20 Correct 1371 ms 304896 KB Output is correct
21 Correct 1081 ms 296452 KB Output is correct
22 Correct 157 ms 231360 KB Output is correct
23 Correct 291 ms 243248 KB Output is correct
24 Correct 121 ms 190256 KB Output is correct
25 Correct 228 ms 195384 KB Output is correct
26 Correct 446 ms 199776 KB Output is correct
27 Correct 637 ms 269352 KB Output is correct
28 Correct 801 ms 279136 KB Output is correct
29 Correct 992 ms 288512 KB Output is correct
30 Correct 1197 ms 297792 KB Output is correct
31 Correct 1402 ms 307200 KB Output is correct
32 Correct 1315 ms 305728 KB Output is correct
33 Correct 1084 ms 304176 KB Output is correct
34 Correct 106 ms 188752 KB Output is correct
35 Correct 101 ms 189132 KB Output is correct
36 Correct 631 ms 268692 KB Output is correct
37 Correct 1033 ms 287408 KB Output is correct
38 Correct 1357 ms 306344 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 231312 KB Output is correct
2 Correct 148 ms 231356 KB Output is correct
3 Correct 92 ms 188116 KB Output is correct
4 Correct 156 ms 231356 KB Output is correct
5 Correct 177 ms 231424 KB Output is correct
6 Correct 88 ms 188104 KB Output is correct
7 Correct 89 ms 188176 KB Output is correct
8 Correct 88 ms 188192 KB Output is correct
9 Correct 572 ms 267748 KB Output is correct
10 Correct 172 ms 234948 KB Output is correct
11 Correct 323 ms 250856 KB Output is correct
12 Correct 196 ms 236992 KB Output is correct
13 Correct 165 ms 192684 KB Output is correct
14 Correct 94 ms 188232 KB Output is correct
15 Correct 91 ms 188400 KB Output is correct
16 Correct 533 ms 267944 KB Output is correct
17 Correct 156 ms 231356 KB Output is correct
18 Correct 152 ms 231404 KB Output is correct
19 Correct 178 ms 231404 KB Output is correct
20 Correct 155 ms 231396 KB Output is correct
21 Correct 90 ms 188108 KB Output is correct
22 Correct 163 ms 231392 KB Output is correct
23 Correct 1323 ms 304540 KB Output is correct
24 Correct 161 ms 231396 KB Output is correct
25 Correct 158 ms 231716 KB Output is correct
26 Correct 92 ms 188520 KB Output is correct
27 Correct 94 ms 188568 KB Output is correct
28 Correct 527 ms 260468 KB Output is correct
29 Correct 711 ms 274896 KB Output is correct
30 Correct 1010 ms 289880 KB Output is correct
31 Correct 1303 ms 304128 KB Output is correct
32 Correct 156 ms 231348 KB Output is correct
33 Correct 150 ms 231296 KB Output is correct
34 Correct 150 ms 231340 KB Output is correct
35 Correct 87 ms 188184 KB Output is correct
36 Correct 89 ms 188188 KB Output is correct
37 Correct 159 ms 231396 KB Output is correct
38 Correct 151 ms 231352 KB Output is correct
39 Correct 151 ms 231376 KB Output is correct
40 Correct 149 ms 231476 KB Output is correct
41 Correct 88 ms 188108 KB Output is correct
42 Correct 157 ms 231448 KB Output is correct
43 Correct 96 ms 188376 KB Output is correct
44 Correct 99 ms 188528 KB Output is correct
45 Correct 600 ms 269288 KB Output is correct
46 Correct 917 ms 287288 KB Output is correct
47 Correct 904 ms 286612 KB Output is correct
48 Correct 158 ms 231456 KB Output is correct
49 Correct 152 ms 231508 KB Output is correct
50 Correct 160 ms 231404 KB Output is correct
51 Correct 152 ms 231312 KB Output is correct
52 Correct 159 ms 231312 KB Output is correct
53 Correct 150 ms 231392 KB Output is correct
54 Correct 151 ms 231320 KB Output is correct
55 Incorrect 1326 ms 288192 KB Solution announced impossible, but it is possible.
56 Halted 0 ms 0 KB -