oj.uz

Submission #932668

# Submission time Handle Problem Language Result Execution time Memory
932668 2024-02-24T02:33:54 Z Programmer123 Fountain Parks (IOI21_parks) C++17
55 / 100
 3480 ms 85188 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.4 * 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 5 ms 17652 KB Output is correct
5 Correct 4 ms 17500 KB Output is correct
6 Correct 6 ms 17500 KB Output is correct
7 Correct 4 ms 17328 KB Output is correct
8 Correct 4 ms 17500 KB Output is correct
9 Correct 131 ms 49016 KB Output is correct
10 Correct 15 ms 20648 KB Output is correct
11 Correct 65 ms 34232 KB Output is correct
12 Correct 21 ms 22108 KB Output is correct
13 Correct 15 ms 20840 KB Output is correct
14 Correct 5 ms 17500 KB Output is correct
15 Correct 5 ms 17500 KB Output is correct
16 Correct 132 ms 49000 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 5 ms 17652 KB Output is correct
5 Correct 4 ms 17500 KB Output is correct
6 Correct 6 ms 17500 KB Output is correct
7 Correct 4 ms 17328 KB Output is correct
8 Correct 4 ms 17500 KB Output is correct
9 Correct 131 ms 49016 KB Output is correct
10 Correct 15 ms 20648 KB Output is correct
11 Correct 65 ms 34232 KB Output is correct
12 Correct 21 ms 22108 KB Output is correct
13 Correct 15 ms 20840 KB Output is correct
14 Correct 5 ms 17500 KB Output is correct
15 Correct 5 ms 17500 KB Output is correct
16 Correct 132 ms 49000 KB Output is correct
17 Correct 4 ms 17696 KB Output is correct
18 Correct 4 ms 17500 KB Output is correct
19 Correct 4 ms 17500 KB Output is correct
20 Correct 4 ms 17500 KB Output is correct
21 Correct 4 ms 17500 KB Output is correct
22 Correct 5 ms 17500 KB Output is correct
23 Correct 275 ms 76944 KB Output is correct
24 Correct 4 ms 17496 KB Output is correct
25 Correct 6 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 108 ms 40968 KB Output is correct
29 Correct 166 ms 53076 KB Output is correct
30 Correct 216 ms 64368 KB Output is correct
31 Correct 309 ms 76920 KB Output is correct
32 Correct 4 ms 17496 KB Output is correct
33 Correct 4 ms 17496 KB Output is correct
34 Correct 4 ms 17496 KB Output is correct
35 Correct 4 ms 17500 KB Output is correct
36 Correct 5 ms 17500 KB Output is correct
37 Correct 4 ms 17500 KB Output is correct
38 Correct 4 ms 17496 KB Output is correct
39 Correct 5 ms 17500 KB Output is correct
40 Correct 4 ms 17500 KB Output is correct
41 Correct 5 ms 17500 KB Output is correct
42 Correct 4 ms 17500 KB Output is correct
43 Correct 5 ms 17608 KB Output is correct
44 Correct 5 ms 17500 KB Output is correct
45 Correct 134 ms 47476 KB Output is correct
46 Correct 194 ms 60056 KB Output is correct
47 Correct 200 ms 60108 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 5 ms 17652 KB Output is correct
5 Correct 4 ms 17500 KB Output is correct
6 Correct 6 ms 17500 KB Output is correct
7 Correct 4 ms 17328 KB Output is correct
8 Correct 4 ms 17500 KB Output is correct
9 Correct 131 ms 49016 KB Output is correct
10 Correct 15 ms 20648 KB Output is correct
11 Correct 65 ms 34232 KB Output is correct
12 Correct 21 ms 22108 KB Output is correct
13 Correct 15 ms 20840 KB Output is correct
14 Correct 5 ms 17500 KB Output is correct
15 Correct 5 ms 17500 KB Output is correct
16 Correct 132 ms 49000 KB Output is correct
17 Correct 4 ms 17696 KB Output is correct
18 Correct 4 ms 17500 KB Output is correct
19 Correct 4 ms 17500 KB Output is correct
20 Correct 4 ms 17500 KB Output is correct
21 Correct 4 ms 17500 KB Output is correct
22 Correct 5 ms 17500 KB Output is correct
23 Correct 275 ms 76944 KB Output is correct
24 Correct 4 ms 17496 KB Output is correct
25 Correct 6 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 108 ms 40968 KB Output is correct
29 Correct 166 ms 53076 KB Output is correct
30 Correct 216 ms 64368 KB Output is correct
31 Correct 309 ms 76920 KB Output is correct
32 Correct 4 ms 17496 KB Output is correct
33 Correct 4 ms 17496 KB Output is correct
34 Correct 4 ms 17496 KB Output is correct
35 Correct 4 ms 17500 KB Output is correct
36 Correct 5 ms 17500 KB Output is correct
37 Correct 4 ms 17500 KB Output is correct
38 Correct 4 ms 17496 KB Output is correct
39 Correct 5 ms 17500 KB Output is correct
40 Correct 4 ms 17500 KB Output is correct
41 Correct 5 ms 17500 KB Output is correct
42 Correct 4 ms 17500 KB Output is correct
43 Correct 5 ms 17608 KB Output is correct
44 Correct 5 ms 17500 KB Output is correct
45 Correct 134 ms 47476 KB Output is correct
46 Correct 194 ms 60056 KB Output is correct
47 Correct 200 ms 60108 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 4 ms 17488 KB Output is correct
52 Correct 5 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 289 ms 76200 KB Output is correct
56 Correct 4 ms 17500 KB Output is correct
57 Correct 2869 ms 18036 KB Output is correct
58 Correct 12 ms 19292 KB Output is correct
59 Correct 7 ms 18012 KB Output is correct
60 Correct 136 ms 46960 KB Output is correct
61 Correct 245 ms 59708 KB Output is correct
62 Correct 238 ms 66472 KB Output is correct
63 Incorrect 3480 ms 68224 KB Solution announced impossible, but it is possible.
64 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 5 ms 17652 KB Output is correct
5 Correct 4 ms 17500 KB Output is correct
6 Correct 6 ms 17500 KB Output is correct
7 Correct 4 ms 17328 KB Output is correct
8 Correct 4 ms 17500 KB Output is correct
9 Correct 131 ms 49016 KB Output is correct
10 Correct 15 ms 20648 KB Output is correct
11 Correct 65 ms 34232 KB Output is correct
12 Correct 21 ms 22108 KB Output is correct
13 Correct 15 ms 20840 KB Output is correct
14 Correct 5 ms 17500 KB Output is correct
15 Correct 5 ms 17500 KB Output is correct
16 Correct 132 ms 49000 KB Output is correct
17 Correct 4 ms 17500 KB Output is correct
18 Correct 4 ms 17496 KB Output is correct
19 Correct 4 ms 17340 KB Output is correct
20 Correct 370 ms 85188 KB Output is correct
21 Correct 311 ms 79712 KB Output is correct
22 Correct 339 ms 79620 KB Output is correct
23 Correct 291 ms 71832 KB Output is correct
24 Correct 61 ms 28752 KB Output is correct
25 Correct 62 ms 28752 KB Output is correct
26 Correct 61 ms 28804 KB Output is correct
27 Correct 313 ms 76060 KB Output is correct
28 Correct 332 ms 76060 KB Output is correct
29 Correct 342 ms 76500 KB Output is correct
30 Correct 373 ms 76520 KB Output is correct
31 Correct 4 ms 17500 KB Output is correct
32 Correct 23 ms 22108 KB Output is correct
33 Correct 69 ms 33364 KB Output is correct
34 Correct 334 ms 85148 KB Output is correct
35 Correct 7 ms 18008 KB Output is correct
36 Correct 20 ms 20644 KB Output is correct
37 Correct 35 ms 23644 KB Output is correct
38 Correct 134 ms 41344 KB Output is correct
39 Correct 193 ms 50116 KB Output is correct
40 Correct 255 ms 59124 KB Output is correct
41 Correct 312 ms 67816 KB Output is correct
42 Correct 417 ms 76624 KB Output is correct
43 Correct 4 ms 17496 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 4 ms 17500 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 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 5 ms 17500 KB Output is correct
55 Correct 5 ms 17500 KB Output is correct
56 Correct 132 ms 47476 KB Output is correct
57 Correct 192 ms 60324 KB Output is correct
58 Correct 194 ms 60056 KB Output is correct
59 Correct 4 ms 17500 KB Output is correct
60 Correct 4 ms 17500 KB Output is correct
61 Correct 4 ms 17500 KB Output is correct
62 Correct 282 ms 77384 KB Output is correct
63 Correct 266 ms 76940 KB Output is correct
64 Correct 272 ms 76560 KB Output is correct
65 Correct 5 ms 17756 KB Output is correct
66 Correct 6 ms 18004 KB Output is correct
67 Correct 154 ms 46928 KB Output is correct
68 Correct 209 ms 62068 KB Output is correct
69 Correct 305 ms 76156 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 5 ms 17652 KB Output is correct
5 Correct 4 ms 17500 KB Output is correct
6 Correct 6 ms 17500 KB Output is correct
7 Correct 4 ms 17328 KB Output is correct
8 Correct 4 ms 17500 KB Output is correct
9 Correct 131 ms 49016 KB Output is correct
10 Correct 15 ms 20648 KB Output is correct
11 Correct 65 ms 34232 KB Output is correct
12 Correct 21 ms 22108 KB Output is correct
13 Correct 15 ms 20840 KB Output is correct
14 Correct 5 ms 17500 KB Output is correct
15 Correct 5 ms 17500 KB Output is correct
16 Correct 132 ms 49000 KB Output is correct
17 Correct 339 ms 81308 KB Output is correct
18 Correct 324 ms 81184 KB Output is correct
19 Correct 323 ms 79848 KB Output is correct
20 Correct 346 ms 74828 KB Output is correct
21 Correct 312 ms 69660 KB Output is correct
22 Correct 4 ms 17500 KB Output is correct
23 Correct 51 ms 27080 KB Output is correct
24 Correct 11 ms 18776 KB Output is correct
25 Correct 26 ms 21852 KB Output is correct
26 Correct 40 ms 24660 KB Output is correct
27 Correct 169 ms 47108 KB Output is correct
28 Correct 223 ms 54980 KB Output is correct
29 Correct 268 ms 61932 KB Output is correct
30 Correct 316 ms 69352 KB Output is correct
31 Correct 400 ms 76768 KB Output is correct
32 Correct 291 ms 76024 KB Output is correct
33 Correct 277 ms 76940 KB Output is correct
34 Correct 6 ms 17756 KB Output is correct
35 Correct 7 ms 18108 KB Output is correct
36 Correct 141 ms 46860 KB Output is correct
37 Correct 213 ms 62052 KB Output is correct
38 Correct 287 ms 76312 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 5 ms 17652 KB Output is correct
5 Correct 4 ms 17500 KB Output is correct
6 Correct 6 ms 17500 KB Output is correct
7 Correct 4 ms 17328 KB Output is correct
8 Correct 4 ms 17500 KB Output is correct
9 Correct 131 ms 49016 KB Output is correct
10 Correct 15 ms 20648 KB Output is correct
11 Correct 65 ms 34232 KB Output is correct
12 Correct 21 ms 22108 KB Output is correct
13 Correct 15 ms 20840 KB Output is correct
14 Correct 5 ms 17500 KB Output is correct
15 Correct 5 ms 17500 KB Output is correct
16 Correct 132 ms 49000 KB Output is correct
17 Correct 4 ms 17696 KB Output is correct
18 Correct 4 ms 17500 KB Output is correct
19 Correct 4 ms 17500 KB Output is correct
20 Correct 4 ms 17500 KB Output is correct
21 Correct 4 ms 17500 KB Output is correct
22 Correct 5 ms 17500 KB Output is correct
23 Correct 275 ms 76944 KB Output is correct
24 Correct 4 ms 17496 KB Output is correct
25 Correct 6 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 108 ms 40968 KB Output is correct
29 Correct 166 ms 53076 KB Output is correct
30 Correct 216 ms 64368 KB Output is correct
31 Correct 309 ms 76920 KB Output is correct
32 Correct 4 ms 17496 KB Output is correct
33 Correct 4 ms 17496 KB Output is correct
34 Correct 4 ms 17496 KB Output is correct
35 Correct 4 ms 17500 KB Output is correct
36 Correct 5 ms 17500 KB Output is correct
37 Correct 4 ms 17500 KB Output is correct
38 Correct 4 ms 17496 KB Output is correct
39 Correct 5 ms 17500 KB Output is correct
40 Correct 4 ms 17500 KB Output is correct
41 Correct 5 ms 17500 KB Output is correct
42 Correct 4 ms 17500 KB Output is correct
43 Correct 5 ms 17608 KB Output is correct
44 Correct 5 ms 17500 KB Output is correct
45 Correct 134 ms 47476 KB Output is correct
46 Correct 194 ms 60056 KB Output is correct
47 Correct 200 ms 60108 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 4 ms 17488 KB Output is correct
52 Correct 5 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 289 ms 76200 KB Output is correct
56 Correct 4 ms 17500 KB Output is correct
57 Correct 2869 ms 18036 KB Output is correct
58 Correct 12 ms 19292 KB Output is correct
59 Correct 7 ms 18012 KB Output is correct
60 Correct 136 ms 46960 KB Output is correct
61 Correct 245 ms 59708 KB Output is correct
62 Correct 238 ms 66472 KB Output is correct
63 Incorrect 3480 ms 68224 KB Solution announced impossible, but it is possible.
64 Halted 0 ms 0 KB -