oj.uz

Submission #566571

# Submission time Handle Problem Language Result Execution time Memory
566571 2022-05-22T12:19:34 Z kartel Fountain Parks (IOI21_parks) C++17
5 / 100
 1194 ms 74480 KB 
#include <bits/stdc++.h>
//#include "grader.cpp"
#include "ext/pb_ds/assoc_container.hpp"
#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;
using namespace __gnu_pbds;
typedef long long ll;

const int N = 1e5 + 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}};

pair <int, int> road[10][10];

pair <int, int> block[N * 2];
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);
}
vector <pair <int, int> > pts;

void dfsd(int v) {
    mk[v] = 1;
    for (auto &u : g[v]) {
        if (mk[u]) {
            continue;
        }
        int dx = pts[v].F - pts[u].F;
        int dy = pts[v].S - pts[u].S;
        block[u] = road[dx + 4][dy + 4];
        dfsd(u);
    }
}

inline ll geth(int a, int b) {return ((ll)a << 20) + b;}

void get_erased_2x2(vector <int> &x, vector <int> &y, unordered_map<ll, int> &del) {
    unordered_map <ll, int> cnt, who;

    for (int i = 0; i < sz(x); i++) {
        who[geth(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[geth(cx, cy)]++;
            if (cnt[geth(cx, cy)] == 4) {
                pts.pb({cx, cy});
            }
        }
    }
    sort(all(pts));
    cnt.clear();
    int ptr = 0;
    for (auto &[x, y] : pts) {
        cnt[geth(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.find(geth(cx, cy)) == cnt.end()) {
                continue;
            }
            g[cnt[geth(cx, cy)]].pb(ptr);
        }
        ptr++;
    }

    queue <int> q;
    for (int i = 0; i < sz(pts); i++) {
        if (mk[i]) {
            continue;
        }

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

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

        auto &[a, b] = block[i];
        int v = who[geth(x + dsteps[a][0], y + dsteps[a][1])];
        int u = who[geth(x + dsteps[b][0], y + dsteps[b][1])];

        del[geth(v, u)] = del[geth(u, v)] = 1;
    }
}

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

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

    unordered_map <ll, int> mp;
    vector <pair <int, int> > r;
    unordered_map <ll, 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[geth(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.find(geth(cx, cy)) != mp.end() && f(i) != f(mp[geth(cx, cy)])) {
                int to = mp[geth(cx, cy)];
                if (del.find(geth(i, to)) != del.end()) {
                    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;
    unordered_map <ll, 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[geth(lx - 1, ly + 1)].pb(i);
            e[geth(lx + 1, ly + 1)].pb(nt(i));
        } else {
            int lx = min(x[a], x[b]);
            int ly = y[a];

            e[geth(lx + 1, ly + 1)].pb(i);
            e[geth(lx + 1, ly - 1)].pb(nt(i));
        }
    }
    for (int i = 0; i < 2 * N; i++) {
        mk[i] = 0;
        g[i].clear();
    }
    for (auto &[p, v] : e) {
        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;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 11976 KB Output is correct
2 Correct 10 ms 11968 KB Output is correct
3 Correct 7 ms 9684 KB Output is correct
4 Correct 11 ms 11976 KB Output is correct
5 Correct 10 ms 11976 KB Output is correct
6 Correct 5 ms 9712 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 409 ms 43052 KB Output is correct
10 Correct 23 ms 15016 KB Output is correct
11 Correct 89 ms 28732 KB Output is correct
12 Correct 28 ms 16548 KB Output is correct
13 Correct 43 ms 19780 KB Output is correct
14 Correct 7 ms 9940 KB Output is correct
15 Correct 8 ms 10068 KB Output is correct
16 Correct 433 ms 43292 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 11976 KB Output is correct
2 Correct 10 ms 11968 KB Output is correct
3 Correct 7 ms 9684 KB Output is correct
4 Correct 11 ms 11976 KB Output is correct
5 Correct 10 ms 11976 KB Output is correct
6 Correct 5 ms 9712 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 409 ms 43052 KB Output is correct
10 Correct 23 ms 15016 KB Output is correct
11 Correct 89 ms 28732 KB Output is correct
12 Correct 28 ms 16548 KB Output is correct
13 Correct 43 ms 19780 KB Output is correct
14 Correct 7 ms 9940 KB Output is correct
15 Correct 8 ms 10068 KB Output is correct
16 Correct 433 ms 43292 KB Output is correct
17 Correct 20 ms 11968 KB Output is correct
18 Correct 9 ms 11976 KB Output is correct
19 Correct 12 ms 11976 KB Output is correct
20 Correct 11 ms 12028 KB Output is correct
21 Correct 7 ms 9684 KB Output is correct
22 Correct 9 ms 11976 KB Output is correct
23 Incorrect 1194 ms 62132 KB Given structure is not connected: There is no path between vertices 0 and 1
24 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 11976 KB Output is correct
2 Correct 10 ms 11968 KB Output is correct
3 Correct 7 ms 9684 KB Output is correct
4 Correct 11 ms 11976 KB Output is correct
5 Correct 10 ms 11976 KB Output is correct
6 Correct 5 ms 9712 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 409 ms 43052 KB Output is correct
10 Correct 23 ms 15016 KB Output is correct
11 Correct 89 ms 28732 KB Output is correct
12 Correct 28 ms 16548 KB Output is correct
13 Correct 43 ms 19780 KB Output is correct
14 Correct 7 ms 9940 KB Output is correct
15 Correct 8 ms 10068 KB Output is correct
16 Correct 433 ms 43292 KB Output is correct
17 Correct 20 ms 11968 KB Output is correct
18 Correct 9 ms 11976 KB Output is correct
19 Correct 12 ms 11976 KB Output is correct
20 Correct 11 ms 12028 KB Output is correct
21 Correct 7 ms 9684 KB Output is correct
22 Correct 9 ms 11976 KB Output is correct
23 Incorrect 1194 ms 62132 KB Given structure is not connected: There is no path between vertices 0 and 1
24 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 11976 KB Output is correct
2 Correct 10 ms 11968 KB Output is correct
3 Correct 7 ms 9684 KB Output is correct
4 Correct 11 ms 11976 KB Output is correct
5 Correct 10 ms 11976 KB Output is correct
6 Correct 5 ms 9712 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 409 ms 43052 KB Output is correct
10 Correct 23 ms 15016 KB Output is correct
11 Correct 89 ms 28732 KB Output is correct
12 Correct 28 ms 16548 KB Output is correct
13 Correct 43 ms 19780 KB Output is correct
14 Correct 7 ms 9940 KB Output is correct
15 Correct 8 ms 10068 KB Output is correct
16 Correct 433 ms 43292 KB Output is correct
17 Correct 11 ms 11976 KB Output is correct
18 Correct 12 ms 11976 KB Output is correct
19 Correct 5 ms 9684 KB Output is correct
20 Incorrect 1194 ms 68908 KB Solution announced impossible, but it is possible.
21 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 11976 KB Output is correct
2 Correct 10 ms 11968 KB Output is correct
3 Correct 7 ms 9684 KB Output is correct
4 Correct 11 ms 11976 KB Output is correct
5 Correct 10 ms 11976 KB Output is correct
6 Correct 5 ms 9712 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 409 ms 43052 KB Output is correct
10 Correct 23 ms 15016 KB Output is correct
11 Correct 89 ms 28732 KB Output is correct
12 Correct 28 ms 16548 KB Output is correct
13 Correct 43 ms 19780 KB Output is correct
14 Correct 7 ms 9940 KB Output is correct
15 Correct 8 ms 10068 KB Output is correct
16 Correct 433 ms 43292 KB Output is correct
17 Correct 1085 ms 74480 KB Output is correct
18 Incorrect 1168 ms 74416 KB Tree @(100001, 50003) appears more than once: for edges on positions 105434 and 124197
19 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 11976 KB Output is correct
2 Correct 10 ms 11968 KB Output is correct
3 Correct 7 ms 9684 KB Output is correct
4 Correct 11 ms 11976 KB Output is correct
5 Correct 10 ms 11976 KB Output is correct
6 Correct 5 ms 9712 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 409 ms 43052 KB Output is correct
10 Correct 23 ms 15016 KB Output is correct
11 Correct 89 ms 28732 KB Output is correct
12 Correct 28 ms 16548 KB Output is correct
13 Correct 43 ms 19780 KB Output is correct
14 Correct 7 ms 9940 KB Output is correct
15 Correct 8 ms 10068 KB Output is correct
16 Correct 433 ms 43292 KB Output is correct
17 Correct 20 ms 11968 KB Output is correct
18 Correct 9 ms 11976 KB Output is correct
19 Correct 12 ms 11976 KB Output is correct
20 Correct 11 ms 12028 KB Output is correct
21 Correct 7 ms 9684 KB Output is correct
22 Correct 9 ms 11976 KB Output is correct
23 Incorrect 1194 ms 62132 KB Given structure is not connected: There is no path between vertices 0 and 1
24 Halted 0 ms 0 KB -