oj.uz

Submission #932667

# Submission time Handle Problem Language Result Execution time Memory
932667 2024-02-24T02:31:54 Z Programmer123 Fountain Parks (IOI21_parks) C++17
55 / 100
 3006 ms 85264 KB 
#include <bits/stdc++.h>
#include "parks.h"

std::unordered_map<int, int> map[200001];
int N;
std::vector<std::pair<int, int>> vld[200000];
std::pair<int, int> assigned[200000];
std::set<std::pair<int, int>> taken;
time_t stop;
std::default_random_engine Rand(std::random_device{}());

bool shuffle = false;
bool Shuffle = false;

bool backtrack(int n) {
    if (n == N - 1) return true;
    if (clock() > stop) return false;
//    if (shuffle && vld[n].size() == 2 && Rand() % 2) {
//        std::swap(vld[n][0], vld[n][1]);
//    }
    for (auto a: vld[n]) {
        if (taken.count(a)) continue;
        taken.insert(a);
        if (backtrack(n + 1)) {
            assigned[n] = a;
            return true;
        }
        taken.erase(a);
    }
    return false;
}

int construct_roads(std::vector<int> x, std::vector<int> y) {
    stop = clock() + 3 * CLOCKS_PER_SEC;
    N = (int) x.size();
    if (N == 1) {
        build({}, {}, {}, {});
        return 1;
    }
    int maxx = x[0];
    int minx = x[0];
    int maxy = y[0];
    int miny = y[0];
    for (int i = 0; i < N; ++i) {
        maxx = std::max(maxx, x[i]);
        minx = std::min(minx, x[i]);
        maxy = std::max(maxy, y[i]);
        miny = std::min(miny, y[i]);
    }
    for (int i = 0; i < N; ++i) {
        map[x[i]][y[i]] = i;
    }
    while (true) {
        std::vector<int> u, v, a, b;
        bool seen[N];
        for (int i = 0; i < N; ++i) {
            seen[i] = false;
        }
        std::queue<int> bfs;
        int start = 0;
        if (shuffle) start = Rand() % N;
        bfs.push(start);
        seen[start] = true;
        auto add = [&](int x, int y, std::vector<int> &data) {
            if (x < 0 || x > 200000) return;
            if (map[x].count(y)) data.push_back(map[x][y]);
        };
        auto edges = [&](int x, int y) {
            std::vector<int> result;
            add(x, y + 2, result);
            add(x, y - 2, result);
            add(x + 2, y, result);
            add(x - 2, y, result);
            if (Shuffle) {
                std::shuffle(result.begin(), result.end(), Rand);
            }
            return result;
        };
        int rem = N - 1;
        while (!bfs.empty()) {
            auto next = bfs.front();
            bfs.pop();
            for (auto n: edges(x[next], y[next])) {
                if (!seen[n]) {
                    seen[n] = true;
                    bfs.push(n);
                    rem--;
                    u.push_back(next);
                    v.push_back(n);
                }
            }
        }
        if (rem)
            return 0;

        std::function<std::vector<std::pair<int, int>>(int, int)> valid = [&x, &y, minx, maxx, miny, maxy](int u,
                                                                                                           int v) -> std::vector<std::pair<int, int>> {
            if (x[u] == x[v]) {
                int _y = (y[u] + y[v]) / 2;
                if (x[u] == minx) return {{minx - 1, _y}};
                if (x[u] == maxx) return {{maxx + 1, _y}};
                return {{x[u] + 1, _y},
                        {x[u] - 1, _y}};
            } else {
                int _x = (x[u] + x[v]) / 2;
                if (y[u] == miny) return {{_x, miny - 1}};
                if (y[u] == maxy) return {{_x, maxy + 1}};
                return {{_x, y[u] + 1},
                        {_x, y[u] - 1}};
            }
        };
        if (shuffle) {
            std::vector<std::pair<int, int>> Edges;
            for (int i = 0; i < N - 1; ++i) {
                Edges.emplace_back(u[i], v[i]);
            }
            std::sort(Edges.begin(), Edges.end(), [&](std::pair<int, int> a, std::pair<int, int> b) {
                int A = a.first;
                int B = b.first;
                if (x[A] == x[B]) return y[A] < y[B];
                return x[A] < x[B];
            });
            for (int i = 0; i < N - 1; ++i) {
                u[i] = Edges[i].first;
                v[i] = Edges[i].second;
            }
        }
        for (int i = 0; i < N - 1; ++i) {
            vld[i] = valid(u[i], v[i]);
            if (Shuffle && vld[i].size() == 2 && Rand() % 2) {
                std::swap(vld[i][0], vld[i][1]);
            }
        }
        if (backtrack(0)) {
            for (int i = 0; i < N - 1; ++i) {
                a.push_back(assigned[i].first);
                b.push_back(assigned[i].second);
            }
            build(u, v, a, b);
            return 1;
        }
        if (clock() > stop) break;
        Shuffle = shuffle;
        shuffle = true;
#ifdef LOCAL
        printf("Retrying...\n");
#endif
    }
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 17500 KB Output is correct
2 Correct 4 ms 17500 KB Output is correct
3 Correct 4 ms 17500 KB Output is correct
4 Correct 4 ms 17496 KB Output is correct
5 Correct 5 ms 17496 KB Output is correct
6 Correct 4 ms 17500 KB Output is correct
7 Correct 4 ms 17500 KB Output is correct
8 Correct 4 ms 17500 KB Output is correct
9 Correct 126 ms 49080 KB Output is correct
10 Correct 15 ms 20568 KB Output is correct
11 Correct 64 ms 34236 KB Output is correct
12 Correct 21 ms 22108 KB Output is correct
13 Correct 15 ms 20588 KB Output is correct
14 Correct 4 ms 17496 KB Output is correct
15 Correct 4 ms 17496 KB Output is correct
16 Correct 146 ms 48952 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 17500 KB Output is correct
2 Correct 4 ms 17500 KB Output is correct
3 Correct 4 ms 17500 KB Output is correct
4 Correct 4 ms 17496 KB Output is correct
5 Correct 5 ms 17496 KB Output is correct
6 Correct 4 ms 17500 KB Output is correct
7 Correct 4 ms 17500 KB Output is correct
8 Correct 4 ms 17500 KB Output is correct
9 Correct 126 ms 49080 KB Output is correct
10 Correct 15 ms 20568 KB Output is correct
11 Correct 64 ms 34236 KB Output is correct
12 Correct 21 ms 22108 KB Output is correct
13 Correct 15 ms 20588 KB Output is correct
14 Correct 4 ms 17496 KB Output is correct
15 Correct 4 ms 17496 KB Output is correct
16 Correct 146 ms 48952 KB Output is correct
17 Correct 4 ms 17496 KB Output is correct
18 Correct 4 ms 17500 KB Output is correct
19 Correct 5 ms 17496 KB Output is correct
20 Correct 5 ms 17500 KB Output is correct
21 Correct 5 ms 17500 KB Output is correct
22 Correct 4 ms 17500 KB Output is correct
23 Correct 274 ms 76944 KB Output is correct
24 Correct 5 ms 17496 KB Output is correct
25 Correct 7 ms 17756 KB Output is correct
26 Correct 5 ms 17500 KB Output is correct
27 Correct 5 ms 17500 KB Output is correct
28 Correct 107 ms 41084 KB Output is correct
29 Correct 161 ms 52852 KB Output is correct
30 Correct 215 ms 64412 KB Output is correct
31 Correct 290 ms 76984 KB Output is correct
32 Correct 4 ms 17500 KB Output is correct
33 Correct 5 ms 17500 KB Output is correct
34 Correct 4 ms 17500 KB Output is correct
35 Correct 4 ms 17496 KB Output is correct
36 Correct 4 ms 17500 KB Output is correct
37 Correct 4 ms 17496 KB Output is correct
38 Correct 4 ms 17500 KB Output is correct
39 Correct 4 ms 17496 KB Output is correct
40 Correct 4 ms 17752 KB Output is correct
41 Correct 5 ms 17496 KB Output is correct
42 Correct 5 ms 17500 KB Output is correct
43 Correct 4 ms 17500 KB Output is correct
44 Correct 5 ms 17696 KB Output is correct
45 Correct 137 ms 47272 KB Output is correct
46 Correct 229 ms 60072 KB Output is correct
47 Correct 221 ms 59964 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 17500 KB Output is correct
2 Correct 4 ms 17500 KB Output is correct
3 Correct 4 ms 17500 KB Output is correct
4 Correct 4 ms 17496 KB Output is correct
5 Correct 5 ms 17496 KB Output is correct
6 Correct 4 ms 17500 KB Output is correct
7 Correct 4 ms 17500 KB Output is correct
8 Correct 4 ms 17500 KB Output is correct
9 Correct 126 ms 49080 KB Output is correct
10 Correct 15 ms 20568 KB Output is correct
11 Correct 64 ms 34236 KB Output is correct
12 Correct 21 ms 22108 KB Output is correct
13 Correct 15 ms 20588 KB Output is correct
14 Correct 4 ms 17496 KB Output is correct
15 Correct 4 ms 17496 KB Output is correct
16 Correct 146 ms 48952 KB Output is correct
17 Correct 4 ms 17496 KB Output is correct
18 Correct 4 ms 17500 KB Output is correct
19 Correct 5 ms 17496 KB Output is correct
20 Correct 5 ms 17500 KB Output is correct
21 Correct 5 ms 17500 KB Output is correct
22 Correct 4 ms 17500 KB Output is correct
23 Correct 274 ms 76944 KB Output is correct
24 Correct 5 ms 17496 KB Output is correct
25 Correct 7 ms 17756 KB Output is correct
26 Correct 5 ms 17500 KB Output is correct
27 Correct 5 ms 17500 KB Output is correct
28 Correct 107 ms 41084 KB Output is correct
29 Correct 161 ms 52852 KB Output is correct
30 Correct 215 ms 64412 KB Output is correct
31 Correct 290 ms 76984 KB Output is correct
32 Correct 4 ms 17500 KB Output is correct
33 Correct 5 ms 17500 KB Output is correct
34 Correct 4 ms 17500 KB Output is correct
35 Correct 4 ms 17496 KB Output is correct
36 Correct 4 ms 17500 KB Output is correct
37 Correct 4 ms 17496 KB Output is correct
38 Correct 4 ms 17500 KB Output is correct
39 Correct 4 ms 17496 KB Output is correct
40 Correct 4 ms 17752 KB Output is correct
41 Correct 5 ms 17496 KB Output is correct
42 Correct 5 ms 17500 KB Output is correct
43 Correct 4 ms 17500 KB Output is correct
44 Correct 5 ms 17696 KB Output is correct
45 Correct 137 ms 47272 KB Output is correct
46 Correct 229 ms 60072 KB Output is correct
47 Correct 221 ms 59964 KB Output is correct
48 Correct 4 ms 17496 KB Output is correct
49 Correct 4 ms 17500 KB Output is correct
50 Correct 4 ms 17500 KB Output is correct
51 Correct 4 ms 17500 KB Output is correct
52 Correct 4 ms 17500 KB Output is correct
53 Correct 4 ms 17500 KB Output is correct
54 Correct 4 ms 17500 KB Output is correct
55 Correct 282 ms 76292 KB Output is correct
56 Correct 4 ms 17500 KB Output is correct
57 Correct 2893 ms 18036 KB Output is correct
58 Incorrect 3006 ms 18572 KB Solution announced impossible, but it is possible.
59 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 17500 KB Output is correct
2 Correct 4 ms 17500 KB Output is correct
3 Correct 4 ms 17500 KB Output is correct
4 Correct 4 ms 17496 KB Output is correct
5 Correct 5 ms 17496 KB Output is correct
6 Correct 4 ms 17500 KB Output is correct
7 Correct 4 ms 17500 KB Output is correct
8 Correct 4 ms 17500 KB Output is correct
9 Correct 126 ms 49080 KB Output is correct
10 Correct 15 ms 20568 KB Output is correct
11 Correct 64 ms 34236 KB Output is correct
12 Correct 21 ms 22108 KB Output is correct
13 Correct 15 ms 20588 KB Output is correct
14 Correct 4 ms 17496 KB Output is correct
15 Correct 4 ms 17496 KB Output is correct
16 Correct 146 ms 48952 KB Output is correct
17 Correct 4 ms 17500 KB Output is correct
18 Correct 5 ms 17500 KB Output is correct
19 Correct 4 ms 17500 KB Output is correct
20 Correct 322 ms 85264 KB Output is correct
21 Correct 363 ms 79848 KB Output is correct
22 Correct 311 ms 79596 KB Output is correct
23 Correct 317 ms 71836 KB Output is correct
24 Correct 61 ms 28752 KB Output is correct
25 Correct 61 ms 28752 KB Output is correct
26 Correct 61 ms 28792 KB Output is correct
27 Correct 338 ms 76012 KB Output is correct
28 Correct 331 ms 76064 KB Output is correct
29 Correct 333 ms 76508 KB Output is correct
30 Correct 374 ms 76720 KB Output is correct
31 Correct 4 ms 17500 KB Output is correct
32 Correct 23 ms 21908 KB Output is correct
33 Correct 58 ms 33108 KB Output is correct
34 Correct 322 ms 85192 KB Output is correct
35 Correct 8 ms 18008 KB Output is correct
36 Correct 24 ms 20572 KB Output is correct
37 Correct 34 ms 23652 KB Output is correct
38 Correct 134 ms 41328 KB Output is correct
39 Correct 190 ms 50116 KB Output is correct
40 Correct 253 ms 59112 KB Output is correct
41 Correct 323 ms 68076 KB Output is correct
42 Correct 454 ms 76648 KB Output is correct
43 Correct 4 ms 17500 KB Output is correct
44 Correct 4 ms 17500 KB Output is correct
45 Correct 4 ms 17500 KB Output is correct
46 Correct 4 ms 17500 KB Output is correct
47 Correct 5 ms 17496 KB Output is correct
48 Correct 4 ms 17500 KB Output is correct
49 Correct 4 ms 17500 KB Output is correct
50 Correct 4 ms 17496 KB Output is correct
51 Correct 5 ms 17496 KB Output is correct
52 Correct 4 ms 17496 KB Output is correct
53 Correct 4 ms 17500 KB Output is correct
54 Correct 4 ms 17500 KB Output is correct
55 Correct 5 ms 17496 KB Output is correct
56 Correct 130 ms 47424 KB Output is correct
57 Correct 187 ms 60056 KB Output is correct
58 Correct 198 ms 60056 KB Output is correct
59 Correct 4 ms 17496 KB Output is correct
60 Correct 4 ms 17496 KB Output is correct
61 Correct 4 ms 17500 KB Output is correct
62 Correct 263 ms 76988 KB Output is correct
63 Correct 272 ms 76944 KB Output is correct
64 Correct 260 ms 76728 KB Output is correct
65 Correct 5 ms 17756 KB Output is correct
66 Correct 7 ms 18012 KB Output is correct
67 Correct 142 ms 47036 KB Output is correct
68 Correct 235 ms 62204 KB Output is correct
69 Correct 320 ms 76196 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 17500 KB Output is correct
2 Correct 4 ms 17500 KB Output is correct
3 Correct 4 ms 17500 KB Output is correct
4 Correct 4 ms 17496 KB Output is correct
5 Correct 5 ms 17496 KB Output is correct
6 Correct 4 ms 17500 KB Output is correct
7 Correct 4 ms 17500 KB Output is correct
8 Correct 4 ms 17500 KB Output is correct
9 Correct 126 ms 49080 KB Output is correct
10 Correct 15 ms 20568 KB Output is correct
11 Correct 64 ms 34236 KB Output is correct
12 Correct 21 ms 22108 KB Output is correct
13 Correct 15 ms 20588 KB Output is correct
14 Correct 4 ms 17496 KB Output is correct
15 Correct 4 ms 17496 KB Output is correct
16 Correct 146 ms 48952 KB Output is correct
17 Correct 319 ms 81132 KB Output is correct
18 Correct 344 ms 81316 KB Output is correct
19 Correct 338 ms 79840 KB Output is correct
20 Correct 357 ms 74800 KB Output is correct
21 Correct 297 ms 69660 KB Output is correct
22 Correct 5 ms 17500 KB Output is correct
23 Correct 49 ms 27112 KB Output is correct
24 Correct 10 ms 18776 KB Output is correct
25 Correct 25 ms 21852 KB Output is correct
26 Correct 41 ms 24760 KB Output is correct
27 Correct 173 ms 47252 KB Output is correct
28 Correct 220 ms 54980 KB Output is correct
29 Correct 270 ms 61932 KB Output is correct
30 Correct 325 ms 69204 KB Output is correct
31 Correct 362 ms 76656 KB Output is correct
32 Correct 291 ms 76020 KB Output is correct
33 Correct 282 ms 76964 KB Output is correct
34 Correct 5 ms 17756 KB Output is correct
35 Correct 8 ms 18084 KB Output is correct
36 Correct 136 ms 46860 KB Output is correct
37 Correct 206 ms 62120 KB Output is correct
38 Correct 280 ms 76252 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 17500 KB Output is correct
2 Correct 4 ms 17500 KB Output is correct
3 Correct 4 ms 17500 KB Output is correct
4 Correct 4 ms 17496 KB Output is correct
5 Correct 5 ms 17496 KB Output is correct
6 Correct 4 ms 17500 KB Output is correct
7 Correct 4 ms 17500 KB Output is correct
8 Correct 4 ms 17500 KB Output is correct
9 Correct 126 ms 49080 KB Output is correct
10 Correct 15 ms 20568 KB Output is correct
11 Correct 64 ms 34236 KB Output is correct
12 Correct 21 ms 22108 KB Output is correct
13 Correct 15 ms 20588 KB Output is correct
14 Correct 4 ms 17496 KB Output is correct
15 Correct 4 ms 17496 KB Output is correct
16 Correct 146 ms 48952 KB Output is correct
17 Correct 4 ms 17496 KB Output is correct
18 Correct 4 ms 17500 KB Output is correct
19 Correct 5 ms 17496 KB Output is correct
20 Correct 5 ms 17500 KB Output is correct
21 Correct 5 ms 17500 KB Output is correct
22 Correct 4 ms 17500 KB Output is correct
23 Correct 274 ms 76944 KB Output is correct
24 Correct 5 ms 17496 KB Output is correct
25 Correct 7 ms 17756 KB Output is correct
26 Correct 5 ms 17500 KB Output is correct
27 Correct 5 ms 17500 KB Output is correct
28 Correct 107 ms 41084 KB Output is correct
29 Correct 161 ms 52852 KB Output is correct
30 Correct 215 ms 64412 KB Output is correct
31 Correct 290 ms 76984 KB Output is correct
32 Correct 4 ms 17500 KB Output is correct
33 Correct 5 ms 17500 KB Output is correct
34 Correct 4 ms 17500 KB Output is correct
35 Correct 4 ms 17496 KB Output is correct
36 Correct 4 ms 17500 KB Output is correct
37 Correct 4 ms 17496 KB Output is correct
38 Correct 4 ms 17500 KB Output is correct
39 Correct 4 ms 17496 KB Output is correct
40 Correct 4 ms 17752 KB Output is correct
41 Correct 5 ms 17496 KB Output is correct
42 Correct 5 ms 17500 KB Output is correct
43 Correct 4 ms 17500 KB Output is correct
44 Correct 5 ms 17696 KB Output is correct
45 Correct 137 ms 47272 KB Output is correct
46 Correct 229 ms 60072 KB Output is correct
47 Correct 221 ms 59964 KB Output is correct
48 Correct 4 ms 17496 KB Output is correct
49 Correct 4 ms 17500 KB Output is correct
50 Correct 4 ms 17500 KB Output is correct
51 Correct 4 ms 17500 KB Output is correct
52 Correct 4 ms 17500 KB Output is correct
53 Correct 4 ms 17500 KB Output is correct
54 Correct 4 ms 17500 KB Output is correct
55 Correct 282 ms 76292 KB Output is correct
56 Correct 4 ms 17500 KB Output is correct
57 Correct 2893 ms 18036 KB Output is correct
58 Incorrect 3006 ms 18572 KB Solution announced impossible, but it is possible.
59 Halted 0 ms 0 KB -