oj.uz

Submission #560487

# Submission time Handle Problem Language Result Execution time Memory
560487 2022-05-11T14:10:00 Z kartel Fountain Parks (IOI21_parks) C++17
45 / 100
 2588 ms 952768 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 = 5e6 + 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 377 ms 577684 KB Output is correct
2 Correct 386 ms 577704 KB Output is correct
3 Correct 211 ms 469964 KB Output is correct
4 Correct 373 ms 577740 KB Output is correct
5 Correct 423 ms 577704 KB Output is correct
6 Correct 226 ms 469980 KB Output is correct
7 Correct 214 ms 469996 KB Output is correct
8 Correct 213 ms 469964 KB Output is correct
9 Correct 1012 ms 626660 KB Output is correct
10 Correct 414 ms 582836 KB Output is correct
11 Correct 605 ms 603980 KB Output is correct
12 Correct 433 ms 585104 KB Output is correct
13 Correct 337 ms 479680 KB Output is correct
14 Correct 213 ms 470228 KB Output is correct
15 Correct 221 ms 470384 KB Output is correct
16 Correct 955 ms 626752 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 377 ms 577684 KB Output is correct
2 Correct 386 ms 577704 KB Output is correct
3 Correct 211 ms 469964 KB Output is correct
4 Correct 373 ms 577740 KB Output is correct
5 Correct 423 ms 577704 KB Output is correct
6 Correct 226 ms 469980 KB Output is correct
7 Correct 214 ms 469996 KB Output is correct
8 Correct 213 ms 469964 KB Output is correct
9 Correct 1012 ms 626660 KB Output is correct
10 Correct 414 ms 582836 KB Output is correct
11 Correct 605 ms 603980 KB Output is correct
12 Correct 433 ms 585104 KB Output is correct
13 Correct 337 ms 479680 KB Output is correct
14 Correct 213 ms 470228 KB Output is correct
15 Correct 221 ms 470384 KB Output is correct
16 Correct 955 ms 626752 KB Output is correct
17 Runtime error 624 ms 952768 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 377 ms 577684 KB Output is correct
2 Correct 386 ms 577704 KB Output is correct
3 Correct 211 ms 469964 KB Output is correct
4 Correct 373 ms 577740 KB Output is correct
5 Correct 423 ms 577704 KB Output is correct
6 Correct 226 ms 469980 KB Output is correct
7 Correct 214 ms 469996 KB Output is correct
8 Correct 213 ms 469964 KB Output is correct
9 Correct 1012 ms 626660 KB Output is correct
10 Correct 414 ms 582836 KB Output is correct
11 Correct 605 ms 603980 KB Output is correct
12 Correct 433 ms 585104 KB Output is correct
13 Correct 337 ms 479680 KB Output is correct
14 Correct 213 ms 470228 KB Output is correct
15 Correct 221 ms 470384 KB Output is correct
16 Correct 955 ms 626752 KB Output is correct
17 Runtime error 624 ms 952768 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 377 ms 577684 KB Output is correct
2 Correct 386 ms 577704 KB Output is correct
3 Correct 211 ms 469964 KB Output is correct
4 Correct 373 ms 577740 KB Output is correct
5 Correct 423 ms 577704 KB Output is correct
6 Correct 226 ms 469980 KB Output is correct
7 Correct 214 ms 469996 KB Output is correct
8 Correct 213 ms 469964 KB Output is correct
9 Correct 1012 ms 626660 KB Output is correct
10 Correct 414 ms 582836 KB Output is correct
11 Correct 605 ms 603980 KB Output is correct
12 Correct 433 ms 585104 KB Output is correct
13 Correct 337 ms 479680 KB Output is correct
14 Correct 213 ms 470228 KB Output is correct
15 Correct 221 ms 470384 KB Output is correct
16 Correct 955 ms 626752 KB Output is correct
17 Correct 415 ms 577692 KB Output is correct
18 Correct 388 ms 577768 KB Output is correct
19 Correct 220 ms 469900 KB Output is correct
20 Correct 2130 ms 685440 KB Output is correct
21 Correct 2008 ms 681496 KB Output is correct
22 Correct 2041 ms 681404 KB Output is correct
23 Correct 1578 ms 661424 KB Output is correct
24 Correct 578 ms 487224 KB Output is correct
25 Correct 1416 ms 513860 KB Output is correct
26 Correct 1282 ms 513824 KB Output is correct
27 Correct 1881 ms 675724 KB Output is correct
28 Correct 1854 ms 675564 KB Output is correct
29 Correct 1988 ms 675680 KB Output is correct
30 Correct 1966 ms 675804 KB Output is correct
31 Correct 399 ms 577748 KB Output is correct
32 Correct 434 ms 584940 KB Output is correct
33 Correct 344 ms 478736 KB Output is correct
34 Correct 1930 ms 684444 KB Output is correct
35 Correct 240 ms 472152 KB Output is correct
36 Correct 390 ms 480964 KB Output is correct
37 Correct 703 ms 491968 KB Output is correct
38 Correct 945 ms 618168 KB Output is correct
39 Correct 1189 ms 633156 KB Output is correct
40 Correct 1493 ms 648668 KB Output is correct
41 Correct 1841 ms 663840 KB Output is correct
42 Correct 2140 ms 678908 KB Output is correct
43 Correct 382 ms 577724 KB Output is correct
44 Correct 400 ms 577744 KB Output is correct
45 Correct 379 ms 577700 KB Output is correct
46 Correct 211 ms 470000 KB Output is correct
47 Correct 214 ms 470016 KB Output is correct
48 Correct 371 ms 577788 KB Output is correct
49 Correct 380 ms 577776 KB Output is correct
50 Correct 368 ms 577804 KB Output is correct
51 Correct 393 ms 577740 KB Output is correct
52 Correct 214 ms 469940 KB Output is correct
53 Correct 371 ms 577740 KB Output is correct
54 Correct 219 ms 470440 KB Output is correct
55 Correct 212 ms 470664 KB Output is correct
56 Correct 1066 ms 627464 KB Output is correct
57 Correct 1470 ms 650072 KB Output is correct
58 Correct 1487 ms 650620 KB Output is correct
59 Correct 211 ms 469964 KB Output is correct
60 Correct 378 ms 577768 KB Output is correct
61 Correct 220 ms 469916 KB Output is correct
62 Correct 1830 ms 675720 KB Output is correct
63 Correct 1791 ms 675676 KB Output is correct
64 Correct 1809 ms 675384 KB Output is correct
65 Correct 219 ms 470812 KB Output is correct
66 Correct 233 ms 471756 KB Output is correct
67 Correct 1053 ms 627520 KB Output is correct
68 Correct 1598 ms 652692 KB Output is correct
69 Correct 2133 ms 677880 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 377 ms 577684 KB Output is correct
2 Correct 386 ms 577704 KB Output is correct
3 Correct 211 ms 469964 KB Output is correct
4 Correct 373 ms 577740 KB Output is correct
5 Correct 423 ms 577704 KB Output is correct
6 Correct 226 ms 469980 KB Output is correct
7 Correct 214 ms 469996 KB Output is correct
8 Correct 213 ms 469964 KB Output is correct
9 Correct 1012 ms 626660 KB Output is correct
10 Correct 414 ms 582836 KB Output is correct
11 Correct 605 ms 603980 KB Output is correct
12 Correct 433 ms 585104 KB Output is correct
13 Correct 337 ms 479680 KB Output is correct
14 Correct 213 ms 470228 KB Output is correct
15 Correct 221 ms 470384 KB Output is correct
16 Correct 955 ms 626752 KB Output is correct
17 Correct 1854 ms 675944 KB Output is correct
18 Correct 1843 ms 675712 KB Output is correct
19 Correct 1996 ms 685244 KB Output is correct
20 Correct 2223 ms 684064 KB Output is correct
21 Correct 1845 ms 666724 KB Output is correct
22 Correct 393 ms 577796 KB Output is correct
23 Correct 525 ms 594140 KB Output is correct
24 Correct 276 ms 474912 KB Output is correct
25 Correct 516 ms 486996 KB Output is correct
26 Correct 944 ms 499084 KB Output is correct
27 Correct 1118 ms 630528 KB Output is correct
28 Correct 1362 ms 644152 KB Output is correct
29 Correct 1792 ms 657300 KB Output is correct
30 Correct 2202 ms 670076 KB Output is correct
31 Correct 2588 ms 684096 KB Output is correct
32 Correct 2526 ms 682348 KB Output is correct
33 Correct 2186 ms 675616 KB Output is correct
34 Correct 234 ms 471124 KB Output is correct
35 Correct 247 ms 472080 KB Output is correct
36 Correct 1291 ms 628896 KB Output is correct
37 Correct 1834 ms 654464 KB Output is correct
38 Correct 2464 ms 679916 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 377 ms 577684 KB Output is correct
2 Correct 386 ms 577704 KB Output is correct
3 Correct 211 ms 469964 KB Output is correct
4 Correct 373 ms 577740 KB Output is correct
5 Correct 423 ms 577704 KB Output is correct
6 Correct 226 ms 469980 KB Output is correct
7 Correct 214 ms 469996 KB Output is correct
8 Correct 213 ms 469964 KB Output is correct
9 Correct 1012 ms 626660 KB Output is correct
10 Correct 414 ms 582836 KB Output is correct
11 Correct 605 ms 603980 KB Output is correct
12 Correct 433 ms 585104 KB Output is correct
13 Correct 337 ms 479680 KB Output is correct
14 Correct 213 ms 470228 KB Output is correct
15 Correct 221 ms 470384 KB Output is correct
16 Correct 955 ms 626752 KB Output is correct
17 Runtime error 624 ms 952768 KB Execution killed with signal 6
18 Halted 0 ms 0 KB -