oj.uz

Submission #565325

# Submission time Handle Problem Language Result Execution time Memory
565325 2022-05-20T17:06:12 Z kartel Fountain Parks (IOI21_parks) C++17
55 / 100
 3039 ms 2097152 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}};
const int dsteps[4][2] = {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}};

map <pair <int, int>, pair <int, int> > road;

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);
}

void get_erased_2x2(const vector <int> &x, const vector <int> &y, map<pair <int, int>, int> &del) {
    map <pair <int, int>, int> cnt, who;
    vector <pair <int, int> > pts;

    for (int i = 0; i < sz(x); i++) {
        who[{x[i], y[i]}] = i;
        for (int j = 0; j < 4; j++) {
            int cx = x[i] + dsteps[j][0];
            int cy = y[i] + dsteps[j][1];

            cnt[{cx, cy}]++;
            if (cnt[{cx, cy}] == 4) {
                pts.pb({cx, cy});
            }
        }
    }
    sort(all(pts));
    vector <vector <int> > g(sz(pts));
    cnt.clear();
    int ptr = 0;
    for (auto &[x, y] : pts) {
        cnt[{x, y}] = ptr++;
    }

    ptr = 0;
    for (auto &[x, y] : pts) {
        int par = (x / 2 + y / 2) % 2;
        for (int i = 0; i < 2; i++) {
            int cx = x + steps[i * 2 + par][0];
            int cy = y + steps[i * 2 + par][1];

            if (!cnt.count({cx, cy})) {
                continue;
            }
            g[cnt[{cx, cy}]].pb(ptr);
        }
        ptr++;
    }

    vector <pair <int, int> > block(sz(pts));
    for (int i = 0; i < sz(pts); i++) {
        if (mk[i]) {
            continue;
        }
        function <void(int)> dfs = [&](int v) {
            for (auto u : g[v]) {
                if (mk[u]) {
                    continue;
                }
                dfs(u);
                int dx = pts[v].F - pts[u].F;
                int dy = pts[v].S - pts[u].S;
                block[u] = road[{dx, dy}];
            }
        };

        int par = (pts[i].F / 2 + pts[i].S / 2) & 1;
        if (par & 1) {
            block[i] = road[{-2, 0}];
        } else {
            block[i] = road[{0, -2}];
        }
        dfs(i);
    }

    for (int i = 0; i < sz(pts); i++) {
        auto [x, y] = pts[i];

        auto [a, b] = block[i];
        int v = who[{x + dsteps[a][0], y + dsteps[a][1]}];
        int u = who[{x + dsteps[b][0], y + dsteps[b][1]}];

        del[{v, u}] = del[{u, v}] = 1;
    }
}

/*

5
4 4
4 6
6 4
4 2
2 4

*/

int construct_roads(vector <int> x, vector <int> y) {
    int n = sz(x);

    road[{0, 2}]  = {2, 0}; road[{2, 0}]  = {0, 1};
    road[{0, -2}] = {1, 3}; road[{-2, 0}] = {3, 2};

    map <pair <int, int>, int> mp;
    vector <pair <int, int> > r;
    map <pair <int, int>, int> del;
    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);
    }

    get_erased_2x2(x, y, del);
    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}];
                if (del[{i, to}]) {
                    continue;
                }
                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:214:13: warning: unused variable 'x' [-Wunused-variable]
  214 |         int x = p.F, y = p.S;
      |             ^
parks.cpp:214:22: warning: unused variable 'y' [-Wunused-variable]
  214 |         int x = p.F, y = p.S;
      |                      ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 231308 KB Output is correct
2 Correct 168 ms 231388 KB Output is correct
3 Correct 93 ms 188252 KB Output is correct
4 Correct 154 ms 231324 KB Output is correct
5 Correct 167 ms 231400 KB Output is correct
6 Correct 102 ms 188108 KB Output is correct
7 Correct 94 ms 188144 KB Output is correct
8 Correct 93 ms 188128 KB Output is correct
9 Correct 1031 ms 275180 KB Output is correct
10 Correct 217 ms 235760 KB Output is correct
11 Correct 453 ms 254704 KB Output is correct
12 Correct 267 ms 238048 KB Output is correct
13 Correct 261 ms 200848 KB Output is correct
14 Correct 91 ms 188472 KB Output is correct
15 Correct 110 ms 188772 KB Output is correct
16 Correct 972 ms 275148 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 231308 KB Output is correct
2 Correct 168 ms 231388 KB Output is correct
3 Correct 93 ms 188252 KB Output is correct
4 Correct 154 ms 231324 KB Output is correct
5 Correct 167 ms 231400 KB Output is correct
6 Correct 102 ms 188108 KB Output is correct
7 Correct 94 ms 188144 KB Output is correct
8 Correct 93 ms 188128 KB Output is correct
9 Correct 1031 ms 275180 KB Output is correct
10 Correct 217 ms 235760 KB Output is correct
11 Correct 453 ms 254704 KB Output is correct
12 Correct 267 ms 238048 KB Output is correct
13 Correct 261 ms 200848 KB Output is correct
14 Correct 91 ms 188472 KB Output is correct
15 Correct 110 ms 188772 KB Output is correct
16 Correct 972 ms 275148 KB Output is correct
17 Correct 172 ms 231400 KB Output is correct
18 Correct 166 ms 231420 KB Output is correct
19 Correct 163 ms 231308 KB Output is correct
20 Correct 156 ms 231312 KB Output is correct
21 Correct 92 ms 188108 KB Output is correct
22 Correct 183 ms 231324 KB Output is correct
23 Correct 2918 ms 332224 KB Output is correct
24 Correct 168 ms 231344 KB Output is correct
25 Correct 198 ms 231896 KB Output is correct
26 Correct 103 ms 188992 KB Output is correct
27 Correct 110 ms 189332 KB Output is correct
28 Correct 1026 ms 270516 KB Output is correct
29 Correct 1774 ms 291712 KB Output is correct
30 Correct 2403 ms 310172 KB Output is correct
31 Correct 3039 ms 331816 KB Output is correct
32 Correct 170 ms 231296 KB Output is correct
33 Correct 167 ms 231332 KB Output is correct
34 Correct 178 ms 231352 KB Output is correct
35 Correct 99 ms 188200 KB Output is correct
36 Correct 104 ms 188200 KB Output is correct
37 Correct 163 ms 231380 KB Output is correct
38 Correct 166 ms 231328 KB Output is correct
39 Correct 166 ms 231420 KB Output is correct
40 Correct 188 ms 231400 KB Output is correct
41 Correct 113 ms 188200 KB Output is correct
42 Correct 157 ms 231436 KB Output is correct
43 Correct 108 ms 188668 KB Output is correct
44 Correct 111 ms 189132 KB Output is correct
45 Correct 971 ms 275760 KB Output is correct
46 Correct 1521 ms 295500 KB Output is correct
47 Correct 1522 ms 295636 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 231308 KB Output is correct
2 Correct 168 ms 231388 KB Output is correct
3 Correct 93 ms 188252 KB Output is correct
4 Correct 154 ms 231324 KB Output is correct
5 Correct 167 ms 231400 KB Output is correct
6 Correct 102 ms 188108 KB Output is correct
7 Correct 94 ms 188144 KB Output is correct
8 Correct 93 ms 188128 KB Output is correct
9 Correct 1031 ms 275180 KB Output is correct
10 Correct 217 ms 235760 KB Output is correct
11 Correct 453 ms 254704 KB Output is correct
12 Correct 267 ms 238048 KB Output is correct
13 Correct 261 ms 200848 KB Output is correct
14 Correct 91 ms 188472 KB Output is correct
15 Correct 110 ms 188772 KB Output is correct
16 Correct 972 ms 275148 KB Output is correct
17 Correct 172 ms 231400 KB Output is correct
18 Correct 166 ms 231420 KB Output is correct
19 Correct 163 ms 231308 KB Output is correct
20 Correct 156 ms 231312 KB Output is correct
21 Correct 92 ms 188108 KB Output is correct
22 Correct 183 ms 231324 KB Output is correct
23 Correct 2918 ms 332224 KB Output is correct
24 Correct 168 ms 231344 KB Output is correct
25 Correct 198 ms 231896 KB Output is correct
26 Correct 103 ms 188992 KB Output is correct
27 Correct 110 ms 189332 KB Output is correct
28 Correct 1026 ms 270516 KB Output is correct
29 Correct 1774 ms 291712 KB Output is correct
30 Correct 2403 ms 310172 KB Output is correct
31 Correct 3039 ms 331816 KB Output is correct
32 Correct 170 ms 231296 KB Output is correct
33 Correct 167 ms 231332 KB Output is correct
34 Correct 178 ms 231352 KB Output is correct
35 Correct 99 ms 188200 KB Output is correct
36 Correct 104 ms 188200 KB Output is correct
37 Correct 163 ms 231380 KB Output is correct
38 Correct 166 ms 231328 KB Output is correct
39 Correct 166 ms 231420 KB Output is correct
40 Correct 188 ms 231400 KB Output is correct
41 Correct 113 ms 188200 KB Output is correct
42 Correct 157 ms 231436 KB Output is correct
43 Correct 108 ms 188668 KB Output is correct
44 Correct 111 ms 189132 KB Output is correct
45 Correct 971 ms 275760 KB Output is correct
46 Correct 1521 ms 295500 KB Output is correct
47 Correct 1522 ms 295636 KB Output is correct
48 Correct 162 ms 231400 KB Output is correct
49 Correct 150 ms 231404 KB Output is correct
50 Correct 158 ms 231400 KB Output is correct
51 Correct 168 ms 231312 KB Output is correct
52 Correct 152 ms 231392 KB Output is correct
53 Correct 179 ms 231400 KB Output is correct
54 Correct 208 ms 231408 KB Output is correct
55 Runtime error 1951 ms 2097152 KB Execution killed with signal 9
56 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 231308 KB Output is correct
2 Correct 168 ms 231388 KB Output is correct
3 Correct 93 ms 188252 KB Output is correct
4 Correct 154 ms 231324 KB Output is correct
5 Correct 167 ms 231400 KB Output is correct
6 Correct 102 ms 188108 KB Output is correct
7 Correct 94 ms 188144 KB Output is correct
8 Correct 93 ms 188128 KB Output is correct
9 Correct 1031 ms 275180 KB Output is correct
10 Correct 217 ms 235760 KB Output is correct
11 Correct 453 ms 254704 KB Output is correct
12 Correct 267 ms 238048 KB Output is correct
13 Correct 261 ms 200848 KB Output is correct
14 Correct 91 ms 188472 KB Output is correct
15 Correct 110 ms 188772 KB Output is correct
16 Correct 972 ms 275148 KB Output is correct
17 Correct 172 ms 231420 KB Output is correct
18 Correct 205 ms 231416 KB Output is correct
19 Correct 108 ms 188180 KB Output is correct
20 Correct 2365 ms 329460 KB Output is correct
21 Correct 2287 ms 327036 KB Output is correct
22 Correct 2236 ms 327612 KB Output is correct
23 Correct 1638 ms 306448 KB Output is correct
24 Correct 1323 ms 270004 KB Output is correct
25 Correct 1743 ms 244660 KB Output is correct
26 Correct 1572 ms 244800 KB Output is correct
27 Correct 2011 ms 318028 KB Output is correct
28 Correct 2162 ms 318792 KB Output is correct
29 Correct 2280 ms 318856 KB Output is correct
30 Correct 2237 ms 318892 KB Output is correct
31 Correct 172 ms 231356 KB Output is correct
32 Correct 253 ms 237956 KB Output is correct
33 Correct 509 ms 223160 KB Output is correct
34 Correct 2076 ms 328384 KB Output is correct
35 Correct 131 ms 190840 KB Output is correct
36 Correct 366 ms 201888 KB Output is correct
37 Correct 701 ms 214896 KB Output is correct
38 Correct 806 ms 268444 KB Output is correct
39 Correct 1181 ms 281516 KB Output is correct
40 Correct 1594 ms 294280 KB Output is correct
41 Correct 2094 ms 309772 KB Output is correct
42 Correct 2565 ms 323336 KB Output is correct
43 Correct 167 ms 231312 KB Output is correct
44 Correct 165 ms 231316 KB Output is correct
45 Correct 168 ms 231400 KB Output is correct
46 Correct 109 ms 188216 KB Output is correct
47 Correct 114 ms 188140 KB Output is correct
48 Correct 179 ms 231328 KB Output is correct
49 Correct 163 ms 231328 KB Output is correct
50 Correct 193 ms 231408 KB Output is correct
51 Correct 162 ms 231396 KB Output is correct
52 Correct 107 ms 188228 KB Output is correct
53 Correct 172 ms 231316 KB Output is correct
54 Correct 126 ms 188748 KB Output is correct
55 Correct 112 ms 189056 KB Output is correct
56 Correct 1096 ms 275732 KB Output is correct
57 Correct 1787 ms 295532 KB Output is correct
58 Correct 1687 ms 295312 KB Output is correct
59 Correct 96 ms 188212 KB Output is correct
60 Correct 164 ms 231400 KB Output is correct
61 Correct 114 ms 188124 KB Output is correct
62 Correct 2143 ms 318864 KB Output is correct
63 Correct 2098 ms 318896 KB Output is correct
64 Correct 2094 ms 318452 KB Output is correct
65 Correct 127 ms 189200 KB Output is correct
66 Correct 126 ms 190428 KB Output is correct
67 Correct 1153 ms 275924 KB Output is correct
68 Correct 1824 ms 299232 KB Output is correct
69 Correct 2494 ms 320736 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 231308 KB Output is correct
2 Correct 168 ms 231388 KB Output is correct
3 Correct 93 ms 188252 KB Output is correct
4 Correct 154 ms 231324 KB Output is correct
5 Correct 167 ms 231400 KB Output is correct
6 Correct 102 ms 188108 KB Output is correct
7 Correct 94 ms 188144 KB Output is correct
8 Correct 93 ms 188128 KB Output is correct
9 Correct 1031 ms 275180 KB Output is correct
10 Correct 217 ms 235760 KB Output is correct
11 Correct 453 ms 254704 KB Output is correct
12 Correct 267 ms 238048 KB Output is correct
13 Correct 261 ms 200848 KB Output is correct
14 Correct 91 ms 188472 KB Output is correct
15 Correct 110 ms 188772 KB Output is correct
16 Correct 972 ms 275148 KB Output is correct
17 Correct 2032 ms 319296 KB Output is correct
18 Correct 2072 ms 320328 KB Output is correct
19 Correct 2546 ms 331004 KB Output is correct
20 Correct 2673 ms 319096 KB Output is correct
21 Correct 2299 ms 307828 KB Output is correct
22 Correct 221 ms 231396 KB Output is correct
23 Correct 410 ms 246064 KB Output is correct
24 Correct 199 ms 193472 KB Output is correct
25 Correct 564 ms 206176 KB Output is correct
26 Correct 1024 ms 218888 KB Output is correct
27 Correct 1097 ms 276956 KB Output is correct
28 Correct 1481 ms 288208 KB Output is correct
29 Correct 1835 ms 300748 KB Output is correct
30 Correct 2112 ms 309972 KB Output is correct
31 Correct 2546 ms 323480 KB Output is correct
32 Correct 2429 ms 320300 KB Output is correct
33 Correct 2213 ms 318868 KB Output is correct
34 Correct 126 ms 189548 KB Output is correct
35 Correct 141 ms 190628 KB Output is correct
36 Correct 1110 ms 275644 KB Output is correct
37 Correct 1692 ms 299496 KB Output is correct
38 Correct 2517 ms 320716 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 231308 KB Output is correct
2 Correct 168 ms 231388 KB Output is correct
3 Correct 93 ms 188252 KB Output is correct
4 Correct 154 ms 231324 KB Output is correct
5 Correct 167 ms 231400 KB Output is correct
6 Correct 102 ms 188108 KB Output is correct
7 Correct 94 ms 188144 KB Output is correct
8 Correct 93 ms 188128 KB Output is correct
9 Correct 1031 ms 275180 KB Output is correct
10 Correct 217 ms 235760 KB Output is correct
11 Correct 453 ms 254704 KB Output is correct
12 Correct 267 ms 238048 KB Output is correct
13 Correct 261 ms 200848 KB Output is correct
14 Correct 91 ms 188472 KB Output is correct
15 Correct 110 ms 188772 KB Output is correct
16 Correct 972 ms 275148 KB Output is correct
17 Correct 172 ms 231400 KB Output is correct
18 Correct 166 ms 231420 KB Output is correct
19 Correct 163 ms 231308 KB Output is correct
20 Correct 156 ms 231312 KB Output is correct
21 Correct 92 ms 188108 KB Output is correct
22 Correct 183 ms 231324 KB Output is correct
23 Correct 2918 ms 332224 KB Output is correct
24 Correct 168 ms 231344 KB Output is correct
25 Correct 198 ms 231896 KB Output is correct
26 Correct 103 ms 188992 KB Output is correct
27 Correct 110 ms 189332 KB Output is correct
28 Correct 1026 ms 270516 KB Output is correct
29 Correct 1774 ms 291712 KB Output is correct
30 Correct 2403 ms 310172 KB Output is correct
31 Correct 3039 ms 331816 KB Output is correct
32 Correct 170 ms 231296 KB Output is correct
33 Correct 167 ms 231332 KB Output is correct
34 Correct 178 ms 231352 KB Output is correct
35 Correct 99 ms 188200 KB Output is correct
36 Correct 104 ms 188200 KB Output is correct
37 Correct 163 ms 231380 KB Output is correct
38 Correct 166 ms 231328 KB Output is correct
39 Correct 166 ms 231420 KB Output is correct
40 Correct 188 ms 231400 KB Output is correct
41 Correct 113 ms 188200 KB Output is correct
42 Correct 157 ms 231436 KB Output is correct
43 Correct 108 ms 188668 KB Output is correct
44 Correct 111 ms 189132 KB Output is correct
45 Correct 971 ms 275760 KB Output is correct
46 Correct 1521 ms 295500 KB Output is correct
47 Correct 1522 ms 295636 KB Output is correct
48 Correct 162 ms 231400 KB Output is correct
49 Correct 150 ms 231404 KB Output is correct
50 Correct 158 ms 231400 KB Output is correct
51 Correct 168 ms 231312 KB Output is correct
52 Correct 152 ms 231392 KB Output is correct
53 Correct 179 ms 231400 KB Output is correct
54 Correct 208 ms 231408 KB Output is correct
55 Runtime error 1951 ms 2097152 KB Execution killed with signal 9
56 Halted 0 ms 0 KB -