oj.uz

Submission #560478

# Submission time Handle Problem Language Result Execution time Memory
560478 2022-05-11T14:05:22 Z kartel Fountain Parks (IOI21_parks) C++17
45 / 100
 2431 ms 762424 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 = 4e6 + 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, used;
    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}) && !used[{i, mp[{cx, cy}]}] && f(i) != f(mp[{cx, cy}])) {
                int to = mp[{cx, cy}];
                link(i, to);
                r.pb({i, to});
                used[{to, i}] = 1;
                used[{i, to}] = 1;
            }
        }
    }
    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:116:13: warning: unused variable 'x' [-Wunused-variable]
  116 |         int x = p.F, y = p.S;
      |             ^
parks.cpp:116:22: warning: unused variable 'y' [-Wunused-variable]
  116 |         int x = p.F, y = p.S;
      |                      ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 313 ms 462316 KB Output is correct
2 Correct 309 ms 462272 KB Output is correct
3 Correct 191 ms 375964 KB Output is correct
4 Correct 306 ms 462300 KB Output is correct
5 Correct 329 ms 462288 KB Output is correct
6 Correct 192 ms 376048 KB Output is correct
7 Correct 184 ms 375980 KB Output is correct
8 Correct 199 ms 376068 KB Output is correct
9 Correct 969 ms 511724 KB Output is correct
10 Correct 363 ms 467232 KB Output is correct
11 Correct 565 ms 488992 KB Output is correct
12 Correct 373 ms 469684 KB Output is correct
13 Correct 284 ms 386140 KB Output is correct
14 Correct 180 ms 376268 KB Output is correct
15 Correct 189 ms 376676 KB Output is correct
16 Correct 966 ms 511748 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 313 ms 462316 KB Output is correct
2 Correct 309 ms 462272 KB Output is correct
3 Correct 191 ms 375964 KB Output is correct
4 Correct 306 ms 462300 KB Output is correct
5 Correct 329 ms 462288 KB Output is correct
6 Correct 192 ms 376048 KB Output is correct
7 Correct 184 ms 375980 KB Output is correct
8 Correct 199 ms 376068 KB Output is correct
9 Correct 969 ms 511724 KB Output is correct
10 Correct 363 ms 467232 KB Output is correct
11 Correct 565 ms 488992 KB Output is correct
12 Correct 373 ms 469684 KB Output is correct
13 Correct 284 ms 386140 KB Output is correct
14 Correct 180 ms 376268 KB Output is correct
15 Correct 189 ms 376676 KB Output is correct
16 Correct 966 ms 511748 KB Output is correct
17 Runtime error 470 ms 762424 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 313 ms 462316 KB Output is correct
2 Correct 309 ms 462272 KB Output is correct
3 Correct 191 ms 375964 KB Output is correct
4 Correct 306 ms 462300 KB Output is correct
5 Correct 329 ms 462288 KB Output is correct
6 Correct 192 ms 376048 KB Output is correct
7 Correct 184 ms 375980 KB Output is correct
8 Correct 199 ms 376068 KB Output is correct
9 Correct 969 ms 511724 KB Output is correct
10 Correct 363 ms 467232 KB Output is correct
11 Correct 565 ms 488992 KB Output is correct
12 Correct 373 ms 469684 KB Output is correct
13 Correct 284 ms 386140 KB Output is correct
14 Correct 180 ms 376268 KB Output is correct
15 Correct 189 ms 376676 KB Output is correct
16 Correct 966 ms 511748 KB Output is correct
17 Runtime error 470 ms 762424 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 313 ms 462316 KB Output is correct
2 Correct 309 ms 462272 KB Output is correct
3 Correct 191 ms 375964 KB Output is correct
4 Correct 306 ms 462300 KB Output is correct
5 Correct 329 ms 462288 KB Output is correct
6 Correct 192 ms 376048 KB Output is correct
7 Correct 184 ms 375980 KB Output is correct
8 Correct 199 ms 376068 KB Output is correct
9 Correct 969 ms 511724 KB Output is correct
10 Correct 363 ms 467232 KB Output is correct
11 Correct 565 ms 488992 KB Output is correct
12 Correct 373 ms 469684 KB Output is correct
13 Correct 284 ms 386140 KB Output is correct
14 Correct 180 ms 376268 KB Output is correct
15 Correct 189 ms 376676 KB Output is correct
16 Correct 966 ms 511748 KB Output is correct
17 Correct 321 ms 462268 KB Output is correct
18 Correct 323 ms 462316 KB Output is correct
19 Correct 168 ms 375980 KB Output is correct
20 Correct 1934 ms 570724 KB Output is correct
21 Correct 2117 ms 565876 KB Output is correct
22 Correct 2100 ms 566164 KB Output is correct
23 Correct 1507 ms 546136 KB Output is correct
24 Correct 605 ms 393812 KB Output is correct
25 Correct 1570 ms 420444 KB Output is correct
26 Correct 1345 ms 420476 KB Output is correct
27 Correct 1974 ms 560760 KB Output is correct
28 Correct 1924 ms 560716 KB Output is correct
29 Correct 2205 ms 560708 KB Output is correct
30 Correct 2081 ms 560692 KB Output is correct
31 Correct 309 ms 462284 KB Output is correct
32 Correct 393 ms 469676 KB Output is correct
33 Correct 323 ms 385104 KB Output is correct
34 Correct 1951 ms 569744 KB Output is correct
35 Correct 208 ms 378328 KB Output is correct
36 Correct 369 ms 387572 KB Output is correct
37 Correct 739 ms 398528 KB Output is correct
38 Correct 957 ms 503228 KB Output is correct
39 Correct 1382 ms 518324 KB Output is correct
40 Correct 1652 ms 533744 KB Output is correct
41 Correct 1881 ms 549192 KB Output is correct
42 Correct 2187 ms 564496 KB Output is correct
43 Correct 307 ms 462312 KB Output is correct
44 Correct 299 ms 462264 KB Output is correct
45 Correct 311 ms 462324 KB Output is correct
46 Correct 195 ms 376000 KB Output is correct
47 Correct 174 ms 376084 KB Output is correct
48 Correct 332 ms 462308 KB Output is correct
49 Correct 301 ms 462352 KB Output is correct
50 Correct 314 ms 462268 KB Output is correct
51 Correct 301 ms 462316 KB Output is correct
52 Correct 186 ms 376072 KB Output is correct
53 Correct 296 ms 462316 KB Output is correct
54 Correct 181 ms 376512 KB Output is correct
55 Correct 205 ms 376760 KB Output is correct
56 Correct 1029 ms 512560 KB Output is correct
57 Correct 1547 ms 534968 KB Output is correct
58 Correct 1519 ms 535028 KB Output is correct
59 Correct 174 ms 376064 KB Output is correct
60 Correct 319 ms 462468 KB Output is correct
61 Correct 176 ms 376076 KB Output is correct
62 Correct 2007 ms 560808 KB Output is correct
63 Correct 1856 ms 560772 KB Output is correct
64 Correct 1831 ms 560552 KB Output is correct
65 Correct 190 ms 376908 KB Output is correct
66 Correct 186 ms 377904 KB Output is correct
67 Correct 1066 ms 512668 KB Output is correct
68 Correct 1517 ms 537476 KB Output is correct
69 Correct 2161 ms 562860 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 313 ms 462316 KB Output is correct
2 Correct 309 ms 462272 KB Output is correct
3 Correct 191 ms 375964 KB Output is correct
4 Correct 306 ms 462300 KB Output is correct
5 Correct 329 ms 462288 KB Output is correct
6 Correct 192 ms 376048 KB Output is correct
7 Correct 184 ms 375980 KB Output is correct
8 Correct 199 ms 376068 KB Output is correct
9 Correct 969 ms 511724 KB Output is correct
10 Correct 363 ms 467232 KB Output is correct
11 Correct 565 ms 488992 KB Output is correct
12 Correct 373 ms 469684 KB Output is correct
13 Correct 284 ms 386140 KB Output is correct
14 Correct 180 ms 376268 KB Output is correct
15 Correct 189 ms 376676 KB Output is correct
16 Correct 966 ms 511748 KB Output is correct
17 Correct 1841 ms 560896 KB Output is correct
18 Correct 1871 ms 561076 KB Output is correct
19 Correct 2077 ms 569744 KB Output is correct
20 Correct 2431 ms 568696 KB Output is correct
21 Correct 1843 ms 551588 KB Output is correct
22 Correct 331 ms 462304 KB Output is correct
23 Correct 449 ms 479088 KB Output is correct
24 Correct 264 ms 381108 KB Output is correct
25 Correct 490 ms 393636 KB Output is correct
26 Correct 973 ms 405624 KB Output is correct
27 Correct 1247 ms 515572 KB Output is correct
28 Correct 1823 ms 529180 KB Output is correct
29 Correct 1885 ms 542620 KB Output is correct
30 Correct 2081 ms 555296 KB Output is correct
31 Correct 2255 ms 569480 KB Output is correct
32 Correct 2059 ms 567824 KB Output is correct
33 Correct 1814 ms 560756 KB Output is correct
34 Correct 220 ms 377248 KB Output is correct
35 Correct 225 ms 378308 KB Output is correct
36 Correct 1167 ms 513948 KB Output is correct
37 Correct 1793 ms 539488 KB Output is correct
38 Correct 2397 ms 565792 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 313 ms 462316 KB Output is correct
2 Correct 309 ms 462272 KB Output is correct
3 Correct 191 ms 375964 KB Output is correct
4 Correct 306 ms 462300 KB Output is correct
5 Correct 329 ms 462288 KB Output is correct
6 Correct 192 ms 376048 KB Output is correct
7 Correct 184 ms 375980 KB Output is correct
8 Correct 199 ms 376068 KB Output is correct
9 Correct 969 ms 511724 KB Output is correct
10 Correct 363 ms 467232 KB Output is correct
11 Correct 565 ms 488992 KB Output is correct
12 Correct 373 ms 469684 KB Output is correct
13 Correct 284 ms 386140 KB Output is correct
14 Correct 180 ms 376268 KB Output is correct
15 Correct 189 ms 376676 KB Output is correct
16 Correct 966 ms 511748 KB Output is correct
17 Runtime error 470 ms 762424 KB Execution killed with signal 6
18 Halted 0 ms 0 KB -