oj.uz

Submission #932660

# Submission time Handle Problem Language Result Execution time Memory
932660 2024-02-24T02:22:14 Z Programmer123 Fountain Parks (IOI21_parks) C++17
55 / 100
 3078 ms 86884 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;

bool backtrack(int n) {
    if (n == N - 1) return true;
    if (clock() > stop) return false;
    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;
    }
    bool shuffle = false;
    std::default_random_engine Rand(std::random_device{}());
    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}};
            }
        };
        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 = 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 17492 KB Output is correct
3 Correct 4 ms 17500 KB Output is correct
4 Correct 4 ms 17500 KB Output is correct
5 Correct 4 ms 17500 KB Output is correct
6 Correct 4 ms 17504 KB Output is correct
7 Correct 4 ms 17500 KB Output is correct
8 Correct 4 ms 17500 KB Output is correct
9 Correct 125 ms 49472 KB Output is correct
10 Correct 15 ms 20572 KB Output is correct
11 Correct 63 ms 34748 KB Output is correct
12 Correct 21 ms 22352 KB Output is correct
13 Correct 15 ms 20844 KB Output is correct
14 Correct 4 ms 17496 KB Output is correct
15 Correct 5 ms 17496 KB Output is correct
16 Correct 129 ms 49716 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 17492 KB Output is correct
3 Correct 4 ms 17500 KB Output is correct
4 Correct 4 ms 17500 KB Output is correct
5 Correct 4 ms 17500 KB Output is correct
6 Correct 4 ms 17504 KB Output is correct
7 Correct 4 ms 17500 KB Output is correct
8 Correct 4 ms 17500 KB Output is correct
9 Correct 125 ms 49472 KB Output is correct
10 Correct 15 ms 20572 KB Output is correct
11 Correct 63 ms 34748 KB Output is correct
12 Correct 21 ms 22352 KB Output is correct
13 Correct 15 ms 20844 KB Output is correct
14 Correct 4 ms 17496 KB Output is correct
15 Correct 5 ms 17496 KB Output is correct
16 Correct 129 ms 49716 KB Output is correct
17 Correct 5 ms 17496 KB Output is correct
18 Correct 4 ms 17500 KB Output is correct
19 Correct 4 ms 17496 KB Output is correct
20 Correct 4 ms 17496 KB Output is correct
21 Correct 5 ms 17500 KB Output is correct
22 Correct 5 ms 17500 KB Output is correct
23 Correct 275 ms 78320 KB Output is correct
24 Correct 5 ms 18080 KB Output is correct
25 Correct 6 ms 17756 KB Output is correct
26 Correct 6 ms 17556 KB Output is correct
27 Correct 6 ms 17768 KB Output is correct
28 Correct 114 ms 41720 KB Output is correct
29 Correct 158 ms 53688 KB Output is correct
30 Correct 212 ms 65428 KB Output is correct
31 Correct 272 ms 78360 KB Output is correct
32 Correct 4 ms 17500 KB Output is correct
33 Correct 4 ms 17496 KB Output is correct
34 Correct 4 ms 17500 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 6 ms 17756 KB Output is correct
40 Correct 4 ms 17504 KB Output is correct
41 Correct 4 ms 17500 KB Output is correct
42 Correct 4 ms 17504 KB Output is correct
43 Correct 5 ms 17500 KB Output is correct
44 Correct 5 ms 17500 KB Output is correct
45 Correct 131 ms 47892 KB Output is correct
46 Correct 203 ms 61288 KB Output is correct
47 Correct 213 ms 61080 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 17492 KB Output is correct
3 Correct 4 ms 17500 KB Output is correct
4 Correct 4 ms 17500 KB Output is correct
5 Correct 4 ms 17500 KB Output is correct
6 Correct 4 ms 17504 KB Output is correct
7 Correct 4 ms 17500 KB Output is correct
8 Correct 4 ms 17500 KB Output is correct
9 Correct 125 ms 49472 KB Output is correct
10 Correct 15 ms 20572 KB Output is correct
11 Correct 63 ms 34748 KB Output is correct
12 Correct 21 ms 22352 KB Output is correct
13 Correct 15 ms 20844 KB Output is correct
14 Correct 4 ms 17496 KB Output is correct
15 Correct 5 ms 17496 KB Output is correct
16 Correct 129 ms 49716 KB Output is correct
17 Correct 5 ms 17496 KB Output is correct
18 Correct 4 ms 17500 KB Output is correct
19 Correct 4 ms 17496 KB Output is correct
20 Correct 4 ms 17496 KB Output is correct
21 Correct 5 ms 17500 KB Output is correct
22 Correct 5 ms 17500 KB Output is correct
23 Correct 275 ms 78320 KB Output is correct
24 Correct 5 ms 18080 KB Output is correct
25 Correct 6 ms 17756 KB Output is correct
26 Correct 6 ms 17556 KB Output is correct
27 Correct 6 ms 17768 KB Output is correct
28 Correct 114 ms 41720 KB Output is correct
29 Correct 158 ms 53688 KB Output is correct
30 Correct 212 ms 65428 KB Output is correct
31 Correct 272 ms 78360 KB Output is correct
32 Correct 4 ms 17500 KB Output is correct
33 Correct 4 ms 17496 KB Output is correct
34 Correct 4 ms 17500 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 6 ms 17756 KB Output is correct
40 Correct 4 ms 17504 KB Output is correct
41 Correct 4 ms 17500 KB Output is correct
42 Correct 4 ms 17504 KB Output is correct
43 Correct 5 ms 17500 KB Output is correct
44 Correct 5 ms 17500 KB Output is correct
45 Correct 131 ms 47892 KB Output is correct
46 Correct 203 ms 61288 KB Output is correct
47 Correct 213 ms 61080 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 287 ms 77260 KB Output is correct
56 Correct 4 ms 17500 KB Output is correct
57 Correct 2819 ms 18048 KB Output is correct
58 Correct 248 ms 19284 KB Output is correct
59 Correct 7 ms 18264 KB Output is correct
60 Correct 135 ms 47372 KB Output is correct
61 Correct 214 ms 60452 KB Output is correct
62 Correct 236 ms 67276 KB Output is correct
63 Incorrect 3078 ms 69268 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 17492 KB Output is correct
3 Correct 4 ms 17500 KB Output is correct
4 Correct 4 ms 17500 KB Output is correct
5 Correct 4 ms 17500 KB Output is correct
6 Correct 4 ms 17504 KB Output is correct
7 Correct 4 ms 17500 KB Output is correct
8 Correct 4 ms 17500 KB Output is correct
9 Correct 125 ms 49472 KB Output is correct
10 Correct 15 ms 20572 KB Output is correct
11 Correct 63 ms 34748 KB Output is correct
12 Correct 21 ms 22352 KB Output is correct
13 Correct 15 ms 20844 KB Output is correct
14 Correct 4 ms 17496 KB Output is correct
15 Correct 5 ms 17496 KB Output is correct
16 Correct 129 ms 49716 KB Output is correct
17 Correct 4 ms 17496 KB Output is correct
18 Correct 5 ms 17500 KB Output is correct
19 Correct 4 ms 17500 KB Output is correct
20 Correct 320 ms 86884 KB Output is correct
21 Correct 326 ms 81128 KB Output is correct
22 Correct 360 ms 81128 KB Output is correct
23 Correct 292 ms 72868 KB Output is correct
24 Correct 59 ms 29780 KB Output is correct
25 Correct 59 ms 29736 KB Output is correct
26 Correct 62 ms 29656 KB Output is correct
27 Correct 320 ms 77032 KB Output is correct
28 Correct 324 ms 76984 KB Output is correct
29 Correct 325 ms 77344 KB Output is correct
30 Correct 324 ms 77432 KB Output is correct
31 Correct 4 ms 17496 KB Output is correct
32 Correct 23 ms 22108 KB Output is correct
33 Correct 60 ms 33916 KB Output is correct
34 Correct 312 ms 86848 KB Output is correct
35 Correct 8 ms 18280 KB Output is correct
36 Correct 23 ms 21084 KB Output is correct
37 Correct 34 ms 24392 KB Output is correct
38 Correct 132 ms 41976 KB Output is correct
39 Correct 187 ms 51252 KB Output is correct
40 Correct 243 ms 60212 KB Output is correct
41 Correct 318 ms 69208 KB Output is correct
42 Correct 364 ms 78208 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 5 ms 17340 KB Output is correct
47 Correct 4 ms 17504 KB Output is correct
48 Correct 5 ms 17496 KB Output is correct
49 Correct 4 ms 17500 KB Output is correct
50 Correct 4 ms 17328 KB Output is correct
51 Correct 4 ms 17292 KB Output is correct
52 Correct 5 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 128 ms 48292 KB Output is correct
57 Correct 187 ms 60824 KB Output is correct
58 Correct 194 ms 60844 KB Output is correct
59 Correct 5 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 281 ms 77864 KB Output is correct
63 Correct 271 ms 77884 KB Output is correct
64 Correct 258 ms 77640 KB Output is correct
65 Correct 5 ms 17752 KB Output is correct
66 Correct 6 ms 18012 KB Output is correct
67 Correct 143 ms 47644 KB Output is correct
68 Correct 207 ms 62800 KB Output is correct
69 Correct 281 ms 77224 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 17492 KB Output is correct
3 Correct 4 ms 17500 KB Output is correct
4 Correct 4 ms 17500 KB Output is correct
5 Correct 4 ms 17500 KB Output is correct
6 Correct 4 ms 17504 KB Output is correct
7 Correct 4 ms 17500 KB Output is correct
8 Correct 4 ms 17500 KB Output is correct
9 Correct 125 ms 49472 KB Output is correct
10 Correct 15 ms 20572 KB Output is correct
11 Correct 63 ms 34748 KB Output is correct
12 Correct 21 ms 22352 KB Output is correct
13 Correct 15 ms 20844 KB Output is correct
14 Correct 4 ms 17496 KB Output is correct
15 Correct 5 ms 17496 KB Output is correct
16 Correct 129 ms 49716 KB Output is correct
17 Correct 332 ms 82612 KB Output is correct
18 Correct 318 ms 82796 KB Output is correct
19 Correct 333 ms 80984 KB Output is correct
20 Correct 327 ms 75692 KB Output is correct
21 Correct 295 ms 70680 KB Output is correct
22 Correct 4 ms 17500 KB Output is correct
23 Correct 48 ms 27644 KB Output is correct
24 Correct 10 ms 19036 KB Output is correct
25 Correct 25 ms 22380 KB Output is correct
26 Correct 40 ms 25852 KB Output is correct
27 Correct 164 ms 47944 KB Output is correct
28 Correct 213 ms 56004 KB Output is correct
29 Correct 288 ms 63208 KB Output is correct
30 Correct 314 ms 70636 KB Output is correct
31 Correct 349 ms 78052 KB Output is correct
32 Correct 269 ms 77048 KB Output is correct
33 Correct 273 ms 77968 KB Output is correct
34 Correct 5 ms 17756 KB Output is correct
35 Correct 8 ms 18100 KB Output is correct
36 Correct 134 ms 47680 KB Output is correct
37 Correct 225 ms 63468 KB Output is correct
38 Correct 317 ms 77224 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 17492 KB Output is correct
3 Correct 4 ms 17500 KB Output is correct
4 Correct 4 ms 17500 KB Output is correct
5 Correct 4 ms 17500 KB Output is correct
6 Correct 4 ms 17504 KB Output is correct
7 Correct 4 ms 17500 KB Output is correct
8 Correct 4 ms 17500 KB Output is correct
9 Correct 125 ms 49472 KB Output is correct
10 Correct 15 ms 20572 KB Output is correct
11 Correct 63 ms 34748 KB Output is correct
12 Correct 21 ms 22352 KB Output is correct
13 Correct 15 ms 20844 KB Output is correct
14 Correct 4 ms 17496 KB Output is correct
15 Correct 5 ms 17496 KB Output is correct
16 Correct 129 ms 49716 KB Output is correct
17 Correct 5 ms 17496 KB Output is correct
18 Correct 4 ms 17500 KB Output is correct
19 Correct 4 ms 17496 KB Output is correct
20 Correct 4 ms 17496 KB Output is correct
21 Correct 5 ms 17500 KB Output is correct
22 Correct 5 ms 17500 KB Output is correct
23 Correct 275 ms 78320 KB Output is correct
24 Correct 5 ms 18080 KB Output is correct
25 Correct 6 ms 17756 KB Output is correct
26 Correct 6 ms 17556 KB Output is correct
27 Correct 6 ms 17768 KB Output is correct
28 Correct 114 ms 41720 KB Output is correct
29 Correct 158 ms 53688 KB Output is correct
30 Correct 212 ms 65428 KB Output is correct
31 Correct 272 ms 78360 KB Output is correct
32 Correct 4 ms 17500 KB Output is correct
33 Correct 4 ms 17496 KB Output is correct
34 Correct 4 ms 17500 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 6 ms 17756 KB Output is correct
40 Correct 4 ms 17504 KB Output is correct
41 Correct 4 ms 17500 KB Output is correct
42 Correct 4 ms 17504 KB Output is correct
43 Correct 5 ms 17500 KB Output is correct
44 Correct 5 ms 17500 KB Output is correct
45 Correct 131 ms 47892 KB Output is correct
46 Correct 203 ms 61288 KB Output is correct
47 Correct 213 ms 61080 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 287 ms 77260 KB Output is correct
56 Correct 4 ms 17500 KB Output is correct
57 Correct 2819 ms 18048 KB Output is correct
58 Correct 248 ms 19284 KB Output is correct
59 Correct 7 ms 18264 KB Output is correct
60 Correct 135 ms 47372 KB Output is correct
61 Correct 214 ms 60452 KB Output is correct
62 Correct 236 ms 67276 KB Output is correct
63 Incorrect 3078 ms 69268 KB Solution announced impossible, but it is possible.
64 Halted 0 ms 0 KB -