oj.uz

Submission #560488

# Submission time Handle Problem Language Result Execution time Memory
560488 2022-05-11T14:11:40 Z kartel Fountain Parks (IOI21_parks) C++17
45 / 100
 1505 ms 381552 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;
        }
        assert(sz(v) == 2);
        int a = v[0], b = v[1];

        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 153 ms 231416 KB Output is correct
2 Correct 151 ms 231388 KB Output is correct
3 Correct 92 ms 188236 KB Output is correct
4 Correct 183 ms 231352 KB Output is correct
5 Correct 165 ms 231404 KB Output is correct
6 Correct 104 ms 188164 KB Output is correct
7 Correct 91 ms 188132 KB Output is correct
8 Correct 95 ms 188152 KB Output is correct
9 Correct 596 ms 267804 KB Output is correct
10 Correct 179 ms 234972 KB Output is correct
11 Correct 310 ms 250844 KB Output is correct
12 Correct 209 ms 236912 KB Output is correct
13 Correct 189 ms 192576 KB Output is correct
14 Correct 102 ms 188316 KB Output is correct
15 Correct 111 ms 188428 KB Output is correct
16 Correct 590 ms 267828 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 231416 KB Output is correct
2 Correct 151 ms 231388 KB Output is correct
3 Correct 92 ms 188236 KB Output is correct
4 Correct 183 ms 231352 KB Output is correct
5 Correct 165 ms 231404 KB Output is correct
6 Correct 104 ms 188164 KB Output is correct
7 Correct 91 ms 188132 KB Output is correct
8 Correct 95 ms 188152 KB Output is correct
9 Correct 596 ms 267804 KB Output is correct
10 Correct 179 ms 234972 KB Output is correct
11 Correct 310 ms 250844 KB Output is correct
12 Correct 209 ms 236912 KB Output is correct
13 Correct 189 ms 192576 KB Output is correct
14 Correct 102 ms 188316 KB Output is correct
15 Correct 111 ms 188428 KB Output is correct
16 Correct 590 ms 267828 KB Output is correct
17 Runtime error 258 ms 381552 KB Execution killed with signal 6
18 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 231416 KB Output is correct
2 Correct 151 ms 231388 KB Output is correct
3 Correct 92 ms 188236 KB Output is correct
4 Correct 183 ms 231352 KB Output is correct
5 Correct 165 ms 231404 KB Output is correct
6 Correct 104 ms 188164 KB Output is correct
7 Correct 91 ms 188132 KB Output is correct
8 Correct 95 ms 188152 KB Output is correct
9 Correct 596 ms 267804 KB Output is correct
10 Correct 179 ms 234972 KB Output is correct
11 Correct 310 ms 250844 KB Output is correct
12 Correct 209 ms 236912 KB Output is correct
13 Correct 189 ms 192576 KB Output is correct
14 Correct 102 ms 188316 KB Output is correct
15 Correct 111 ms 188428 KB Output is correct
16 Correct 590 ms 267828 KB Output is correct
17 Runtime error 258 ms 381552 KB Execution killed with signal 6
18 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 231416 KB Output is correct
2 Correct 151 ms 231388 KB Output is correct
3 Correct 92 ms 188236 KB Output is correct
4 Correct 183 ms 231352 KB Output is correct
5 Correct 165 ms 231404 KB Output is correct
6 Correct 104 ms 188164 KB Output is correct
7 Correct 91 ms 188132 KB Output is correct
8 Correct 95 ms 188152 KB Output is correct
9 Correct 596 ms 267804 KB Output is correct
10 Correct 179 ms 234972 KB Output is correct
11 Correct 310 ms 250844 KB Output is correct
12 Correct 209 ms 236912 KB Output is correct
13 Correct 189 ms 192576 KB Output is correct
14 Correct 102 ms 188316 KB Output is correct
15 Correct 111 ms 188428 KB Output is correct
16 Correct 590 ms 267828 KB Output is correct
17 Correct 154 ms 231296 KB Output is correct
18 Correct 161 ms 231412 KB Output is correct
19 Correct 102 ms 188132 KB Output is correct
20 Correct 1419 ms 311892 KB Output is correct
21 Correct 1457 ms 309320 KB Output is correct
22 Correct 1441 ms 309940 KB Output is correct
23 Correct 1008 ms 293632 KB Output is correct
24 Correct 574 ms 205460 KB Output is correct
25 Correct 816 ms 207560 KB Output is correct
26 Correct 694 ms 207652 KB Output is correct
27 Correct 1099 ms 304224 KB Output is correct
28 Correct 1073 ms 304252 KB Output is correct
29 Correct 1125 ms 304324 KB Output is correct
30 Correct 1125 ms 304180 KB Output is correct
31 Correct 154 ms 231332 KB Output is correct
32 Correct 195 ms 236752 KB Output is correct
33 Correct 200 ms 196848 KB Output is correct
34 Correct 1160 ms 313060 KB Output is correct
35 Correct 106 ms 189260 KB Output is correct
36 Correct 180 ms 193088 KB Output is correct
37 Correct 318 ms 197988 KB Output is correct
38 Correct 481 ms 261628 KB Output is correct
39 Correct 687 ms 273104 KB Output is correct
40 Correct 874 ms 285136 KB Output is correct
41 Correct 1089 ms 296260 KB Output is correct
42 Correct 1314 ms 307432 KB Output is correct
43 Correct 153 ms 231400 KB Output is correct
44 Correct 149 ms 231364 KB Output is correct
45 Correct 151 ms 231464 KB Output is correct
46 Correct 89 ms 188112 KB Output is correct
47 Correct 88 ms 188128 KB Output is correct
48 Correct 163 ms 231432 KB Output is correct
49 Correct 153 ms 231460 KB Output is correct
50 Correct 152 ms 231312 KB Output is correct
51 Correct 149 ms 231396 KB Output is correct
52 Correct 103 ms 188108 KB Output is correct
53 Correct 152 ms 231408 KB Output is correct
54 Correct 92 ms 188380 KB Output is correct
55 Correct 95 ms 188504 KB Output is correct
56 Correct 595 ms 268572 KB Output is correct
57 Correct 872 ms 285480 KB Output is correct
58 Correct 868 ms 285480 KB Output is correct
59 Correct 89 ms 188112 KB Output is correct
60 Correct 150 ms 231312 KB Output is correct
61 Correct 89 ms 188100 KB Output is correct
62 Correct 1143 ms 304508 KB Output is correct
63 Correct 1049 ms 304244 KB Output is correct
64 Correct 1010 ms 303956 KB Output is correct
65 Correct 92 ms 188512 KB Output is correct
66 Correct 97 ms 189008 KB Output is correct
67 Correct 579 ms 268568 KB Output is correct
68 Correct 909 ms 287560 KB Output is correct
69 Correct 1269 ms 306544 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 231416 KB Output is correct
2 Correct 151 ms 231388 KB Output is correct
3 Correct 92 ms 188236 KB Output is correct
4 Correct 183 ms 231352 KB Output is correct
5 Correct 165 ms 231404 KB Output is correct
6 Correct 104 ms 188164 KB Output is correct
7 Correct 91 ms 188132 KB Output is correct
8 Correct 95 ms 188152 KB Output is correct
9 Correct 596 ms 267804 KB Output is correct
10 Correct 179 ms 234972 KB Output is correct
11 Correct 310 ms 250844 KB Output is correct
12 Correct 209 ms 236912 KB Output is correct
13 Correct 189 ms 192576 KB Output is correct
14 Correct 102 ms 188316 KB Output is correct
15 Correct 111 ms 188428 KB Output is correct
16 Correct 590 ms 267828 KB Output is correct
17 Correct 1051 ms 304848 KB Output is correct
18 Correct 1027 ms 304636 KB Output is correct
19 Correct 1224 ms 313340 KB Output is correct
20 Correct 1295 ms 305080 KB Output is correct
21 Correct 1060 ms 296100 KB Output is correct
22 Correct 155 ms 231396 KB Output is correct
23 Correct 262 ms 243340 KB Output is correct
24 Correct 124 ms 190264 KB Output is correct
25 Correct 244 ms 195540 KB Output is correct
26 Correct 383 ms 199628 KB Output is correct
27 Correct 611 ms 269396 KB Output is correct
28 Correct 796 ms 279052 KB Output is correct
29 Correct 947 ms 288732 KB Output is correct
30 Correct 1283 ms 297740 KB Output is correct
31 Correct 1505 ms 307700 KB Output is correct
32 Correct 1444 ms 306212 KB Output is correct
33 Correct 1088 ms 304196 KB Output is correct
34 Correct 99 ms 188752 KB Output is correct
35 Correct 109 ms 189168 KB Output is correct
36 Correct 649 ms 268536 KB Output is correct
37 Correct 1136 ms 287712 KB Output is correct
38 Correct 1300 ms 306212 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 231416 KB Output is correct
2 Correct 151 ms 231388 KB Output is correct
3 Correct 92 ms 188236 KB Output is correct
4 Correct 183 ms 231352 KB Output is correct
5 Correct 165 ms 231404 KB Output is correct
6 Correct 104 ms 188164 KB Output is correct
7 Correct 91 ms 188132 KB Output is correct
8 Correct 95 ms 188152 KB Output is correct
9 Correct 596 ms 267804 KB Output is correct
10 Correct 179 ms 234972 KB Output is correct
11 Correct 310 ms 250844 KB Output is correct
12 Correct 209 ms 236912 KB Output is correct
13 Correct 189 ms 192576 KB Output is correct
14 Correct 102 ms 188316 KB Output is correct
15 Correct 111 ms 188428 KB Output is correct
16 Correct 590 ms 267828 KB Output is correct
17 Runtime error 258 ms 381552 KB Execution killed with signal 6
18 Halted 0 ms 0 KB -