oj.uz

답안 #560485

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
560485 2022-05-11T14:08:31 Z kartel 분수 공원 (IOI21_parks) C++17
25 / 100
 3500 ms 166284 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 = 5e5 + 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]) {
            if (sd) {
                while(1);
            }
            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

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 58192 KB Output is correct
2 Correct 56 ms 58220 KB Output is correct
3 Correct 23 ms 47316 KB Output is correct
4 Correct 41 ms 58216 KB Output is correct
5 Correct 43 ms 58120 KB Output is correct
6 Correct 23 ms 47316 KB Output is correct
7 Correct 48 ms 47308 KB Output is correct
8 Correct 23 ms 47316 KB Output is correct
9 Correct 726 ms 107076 KB Output is correct
10 Correct 79 ms 62952 KB Output is correct
11 Correct 291 ms 84408 KB Output is correct
12 Correct 99 ms 65540 KB Output is correct
13 Correct 164 ms 56968 KB Output is correct
14 Correct 24 ms 47448 KB Output is correct
15 Correct 27 ms 47700 KB Output is correct
16 Correct 804 ms 107196 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 58192 KB Output is correct
2 Correct 56 ms 58220 KB Output is correct
3 Correct 23 ms 47316 KB Output is correct
4 Correct 41 ms 58216 KB Output is correct
5 Correct 43 ms 58120 KB Output is correct
6 Correct 23 ms 47316 KB Output is correct
7 Correct 48 ms 47308 KB Output is correct
8 Correct 23 ms 47316 KB Output is correct
9 Correct 726 ms 107076 KB Output is correct
10 Correct 79 ms 62952 KB Output is correct
11 Correct 291 ms 84408 KB Output is correct
12 Correct 99 ms 65540 KB Output is correct
13 Correct 164 ms 56968 KB Output is correct
14 Correct 24 ms 47448 KB Output is correct
15 Correct 27 ms 47700 KB Output is correct
16 Correct 804 ms 107196 KB Output is correct
17 Runtime error 81 ms 95732 KB Execution killed with signal 6
18 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 58192 KB Output is correct
2 Correct 56 ms 58220 KB Output is correct
3 Correct 23 ms 47316 KB Output is correct
4 Correct 41 ms 58216 KB Output is correct
5 Correct 43 ms 58120 KB Output is correct
6 Correct 23 ms 47316 KB Output is correct
7 Correct 48 ms 47308 KB Output is correct
8 Correct 23 ms 47316 KB Output is correct
9 Correct 726 ms 107076 KB Output is correct
10 Correct 79 ms 62952 KB Output is correct
11 Correct 291 ms 84408 KB Output is correct
12 Correct 99 ms 65540 KB Output is correct
13 Correct 164 ms 56968 KB Output is correct
14 Correct 24 ms 47448 KB Output is correct
15 Correct 27 ms 47700 KB Output is correct
16 Correct 804 ms 107196 KB Output is correct
17 Runtime error 81 ms 95732 KB Execution killed with signal 6
18 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 58192 KB Output is correct
2 Correct 56 ms 58220 KB Output is correct
3 Correct 23 ms 47316 KB Output is correct
4 Correct 41 ms 58216 KB Output is correct
5 Correct 43 ms 58120 KB Output is correct
6 Correct 23 ms 47316 KB Output is correct
7 Correct 48 ms 47308 KB Output is correct
8 Correct 23 ms 47316 KB Output is correct
9 Correct 726 ms 107076 KB Output is correct
10 Correct 79 ms 62952 KB Output is correct
11 Correct 291 ms 84408 KB Output is correct
12 Correct 99 ms 65540 KB Output is correct
13 Correct 164 ms 56968 KB Output is correct
14 Correct 24 ms 47448 KB Output is correct
15 Correct 27 ms 47700 KB Output is correct
16 Correct 804 ms 107196 KB Output is correct
17 Correct 51 ms 58120 KB Output is correct
18 Correct 48 ms 58228 KB Output is correct
19 Correct 30 ms 47316 KB Output is correct
20 Correct 1869 ms 166284 KB Output is correct
21 Correct 2071 ms 162456 KB Output is correct
22 Correct 2017 ms 161872 KB Output is correct
23 Correct 1579 ms 141372 KB Output is correct
24 Correct 538 ms 64560 KB Output is correct
25 Correct 1614 ms 91052 KB Output is correct
26 Correct 1408 ms 91072 KB Output is correct
27 Correct 1916 ms 156108 KB Output is correct
28 Correct 2037 ms 156068 KB Output is correct
29 Correct 1941 ms 156096 KB Output is correct
30 Correct 1892 ms 156088 KB Output is correct
31 Correct 44 ms 58168 KB Output is correct
32 Correct 107 ms 65328 KB Output is correct
33 Correct 202 ms 55948 KB Output is correct
34 Correct 1799 ms 166088 KB Output is correct
35 Correct 50 ms 49456 KB Output is correct
36 Correct 252 ms 58180 KB Output is correct
37 Correct 589 ms 69236 KB Output is correct
38 Correct 731 ms 98564 KB Output is correct
39 Correct 1031 ms 113576 KB Output is correct
40 Correct 1359 ms 128880 KB Output is correct
41 Correct 1735 ms 143980 KB Output is correct
42 Correct 2151 ms 159644 KB Output is correct
43 Correct 49 ms 58168 KB Output is correct
44 Correct 43 ms 58152 KB Output is correct
45 Correct 43 ms 58196 KB Output is correct
46 Correct 27 ms 47316 KB Output is correct
47 Correct 30 ms 47316 KB Output is correct
48 Execution timed out 3585 ms 47256 KB Time limit exceeded
49 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 58192 KB Output is correct
2 Correct 56 ms 58220 KB Output is correct
3 Correct 23 ms 47316 KB Output is correct
4 Correct 41 ms 58216 KB Output is correct
5 Correct 43 ms 58120 KB Output is correct
6 Correct 23 ms 47316 KB Output is correct
7 Correct 48 ms 47308 KB Output is correct
8 Correct 23 ms 47316 KB Output is correct
9 Correct 726 ms 107076 KB Output is correct
10 Correct 79 ms 62952 KB Output is correct
11 Correct 291 ms 84408 KB Output is correct
12 Correct 99 ms 65540 KB Output is correct
13 Correct 164 ms 56968 KB Output is correct
14 Correct 24 ms 47448 KB Output is correct
15 Correct 27 ms 47700 KB Output is correct
16 Correct 804 ms 107196 KB Output is correct
17 Correct 1732 ms 156392 KB Output is correct
18 Correct 1693 ms 156724 KB Output is correct
19 Correct 1961 ms 165436 KB Output is correct
20 Correct 2056 ms 165000 KB Output is correct
21 Correct 1567 ms 147036 KB Output is correct
22 Correct 43 ms 58116 KB Output is correct
23 Correct 191 ms 74464 KB Output is correct
24 Correct 87 ms 52088 KB Output is correct
25 Correct 359 ms 64224 KB Output is correct
26 Correct 696 ms 76376 KB Output is correct
27 Correct 834 ms 111008 KB Output is correct
28 Correct 1063 ms 124360 KB Output is correct
29 Correct 1337 ms 138104 KB Output is correct
30 Correct 1715 ms 150656 KB Output is correct
31 Correct 2020 ms 164676 KB Output is correct
32 Correct 1782 ms 162840 KB Output is correct
33 Correct 1497 ms 156304 KB Output is correct
34 Correct 35 ms 48428 KB Output is correct
35 Correct 46 ms 49368 KB Output is correct
36 Correct 749 ms 109104 KB Output is correct
37 Correct 1257 ms 134912 KB Output is correct
38 Correct 1784 ms 160444 KB Output is correct

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 58192 KB Output is correct
2 Correct 56 ms 58220 KB Output is correct
3 Correct 23 ms 47316 KB Output is correct
4 Correct 41 ms 58216 KB Output is correct
5 Correct 43 ms 58120 KB Output is correct
6 Correct 23 ms 47316 KB Output is correct
7 Correct 48 ms 47308 KB Output is correct
8 Correct 23 ms 47316 KB Output is correct
9 Correct 726 ms 107076 KB Output is correct
10 Correct 79 ms 62952 KB Output is correct
11 Correct 291 ms 84408 KB Output is correct
12 Correct 99 ms 65540 KB Output is correct
13 Correct 164 ms 56968 KB Output is correct
14 Correct 24 ms 47448 KB Output is correct
15 Correct 27 ms 47700 KB Output is correct
16 Correct 804 ms 107196 KB Output is correct
17 Runtime error 81 ms 95732 KB Execution killed with signal 6
18 Halted 0 ms 0 KB -