oj.uz

Submission #932670

# Submission time Handle Problem Language Result Execution time Memory
932670 2024-02-24T02:41:26 Z Programmer123 Fountain Parks (IOI21_parks) C++17
55 / 100
 3406 ms 117016 KB 
#include <bits/stdc++.h>
#include "parks.h"

std::unordered_map<int, int> map[200001];
int N;
std::map<std::pair<int, int>, std::vector<int>> rely;
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 doomed(int x) {
    for (auto a: vld[x]) if (!taken.count(a)) return false;
    return true;
}

bool cantake(std::pair<int, int> a, int n) {
    for (auto x: rely[a]) if (x > n && doomed(x)) return false;
    return true;
}

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 (!cantake(a, n)) {
            taken.erase(a);
            continue;
        }
        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]);
            }
        }
        for (int i = 0; i < N - 1; ++i) {
            for (auto n: vld[i]) {
                rely[n].push_back(i);
            }
        }
        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;
        }
        rely.clear();
        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 6 ms 17500 KB Output is correct
2 Correct 4 ms 17500 KB Output is correct
3 Correct 5 ms 17500 KB Output is correct
4 Correct 6 ms 17500 KB Output is correct
5 Correct 5 ms 17500 KB Output is correct
6 Correct 4 ms 17500 KB Output is correct
7 Correct 4 ms 17500 KB Output is correct
8 Correct 5 ms 17508 KB Output is correct
9 Correct 159 ms 58384 KB Output is correct
10 Correct 17 ms 21596 KB Output is correct
11 Correct 85 ms 39356 KB Output is correct
12 Correct 24 ms 23588 KB Output is correct
13 Correct 15 ms 20584 KB Output is correct
14 Correct 4 ms 17500 KB Output is correct
15 Correct 7 ms 17500 KB Output is correct
16 Correct 166 ms 58504 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 17500 KB Output is correct
2 Correct 4 ms 17500 KB Output is correct
3 Correct 5 ms 17500 KB Output is correct
4 Correct 6 ms 17500 KB Output is correct
5 Correct 5 ms 17500 KB Output is correct
6 Correct 4 ms 17500 KB Output is correct
7 Correct 4 ms 17500 KB Output is correct
8 Correct 5 ms 17508 KB Output is correct
9 Correct 159 ms 58384 KB Output is correct
10 Correct 17 ms 21596 KB Output is correct
11 Correct 85 ms 39356 KB Output is correct
12 Correct 24 ms 23588 KB Output is correct
13 Correct 15 ms 20584 KB Output is correct
14 Correct 4 ms 17500 KB Output is correct
15 Correct 7 ms 17500 KB Output is correct
16 Correct 166 ms 58504 KB Output is correct
17 Correct 5 ms 17500 KB Output is correct
18 Correct 4 ms 17500 KB Output is correct
19 Correct 5 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 4 ms 17500 KB Output is correct
23 Correct 368 ms 95688 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 17556 KB Output is correct
27 Correct 5 ms 17496 KB Output is correct
28 Correct 139 ms 48584 KB Output is correct
29 Correct 237 ms 64264 KB Output is correct
30 Correct 313 ms 79228 KB Output is correct
31 Correct 397 ms 95628 KB Output is correct
32 Correct 4 ms 17500 KB Output is correct
33 Correct 5 ms 17500 KB Output is correct
34 Correct 5 ms 17496 KB Output is correct
35 Correct 5 ms 17500 KB Output is correct
36 Correct 4 ms 17500 KB Output is correct
37 Correct 4 ms 17500 KB Output is correct
38 Correct 4 ms 17500 KB Output is correct
39 Correct 5 ms 17500 KB Output is correct
40 Correct 4 ms 17500 KB Output is correct
41 Correct 4 ms 17500 KB Output is correct
42 Correct 4 ms 17500 KB Output is correct
43 Correct 5 ms 17500 KB Output is correct
44 Correct 5 ms 17500 KB Output is correct
45 Correct 185 ms 60268 KB Output is correct
46 Correct 259 ms 78492 KB Output is correct
47 Correct 271 ms 78608 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 17500 KB Output is correct
2 Correct 4 ms 17500 KB Output is correct
3 Correct 5 ms 17500 KB Output is correct
4 Correct 6 ms 17500 KB Output is correct
5 Correct 5 ms 17500 KB Output is correct
6 Correct 4 ms 17500 KB Output is correct
7 Correct 4 ms 17500 KB Output is correct
8 Correct 5 ms 17508 KB Output is correct
9 Correct 159 ms 58384 KB Output is correct
10 Correct 17 ms 21596 KB Output is correct
11 Correct 85 ms 39356 KB Output is correct
12 Correct 24 ms 23588 KB Output is correct
13 Correct 15 ms 20584 KB Output is correct
14 Correct 4 ms 17500 KB Output is correct
15 Correct 7 ms 17500 KB Output is correct
16 Correct 166 ms 58504 KB Output is correct
17 Correct 5 ms 17500 KB Output is correct
18 Correct 4 ms 17500 KB Output is correct
19 Correct 5 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 4 ms 17500 KB Output is correct
23 Correct 368 ms 95688 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 17556 KB Output is correct
27 Correct 5 ms 17496 KB Output is correct
28 Correct 139 ms 48584 KB Output is correct
29 Correct 237 ms 64264 KB Output is correct
30 Correct 313 ms 79228 KB Output is correct
31 Correct 397 ms 95628 KB Output is correct
32 Correct 4 ms 17500 KB Output is correct
33 Correct 5 ms 17500 KB Output is correct
34 Correct 5 ms 17496 KB Output is correct
35 Correct 5 ms 17500 KB Output is correct
36 Correct 4 ms 17500 KB Output is correct
37 Correct 4 ms 17500 KB Output is correct
38 Correct 4 ms 17500 KB Output is correct
39 Correct 5 ms 17500 KB Output is correct
40 Correct 4 ms 17500 KB Output is correct
41 Correct 4 ms 17500 KB Output is correct
42 Correct 4 ms 17500 KB Output is correct
43 Correct 5 ms 17500 KB Output is correct
44 Correct 5 ms 17500 KB Output is correct
45 Correct 185 ms 60268 KB Output is correct
46 Correct 259 ms 78492 KB Output is correct
47 Correct 271 ms 78608 KB Output is correct
48 Correct 5 ms 17500 KB Output is correct
49 Correct 4 ms 17500 KB Output is correct
50 Correct 4 ms 17472 KB Output is correct
51 Correct 4 ms 17908 KB Output is correct
52 Correct 4 ms 17496 KB Output is correct
53 Correct 4 ms 17500 KB Output is correct
54 Correct 5 ms 17496 KB Output is correct
55 Correct 418 ms 95052 KB Output is correct
56 Correct 4 ms 17500 KB Output is correct
57 Incorrect 3406 ms 17960 KB Solution announced impossible, but it is possible.
58 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 17500 KB Output is correct
2 Correct 4 ms 17500 KB Output is correct
3 Correct 5 ms 17500 KB Output is correct
4 Correct 6 ms 17500 KB Output is correct
5 Correct 5 ms 17500 KB Output is correct
6 Correct 4 ms 17500 KB Output is correct
7 Correct 4 ms 17500 KB Output is correct
8 Correct 5 ms 17508 KB Output is correct
9 Correct 159 ms 58384 KB Output is correct
10 Correct 17 ms 21596 KB Output is correct
11 Correct 85 ms 39356 KB Output is correct
12 Correct 24 ms 23588 KB Output is correct
13 Correct 15 ms 20584 KB Output is correct
14 Correct 4 ms 17500 KB Output is correct
15 Correct 7 ms 17500 KB Output is correct
16 Correct 166 ms 58504 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 446 ms 103920 KB Output is correct
21 Correct 410 ms 98640 KB Output is correct
22 Correct 501 ms 98580 KB Output is correct
23 Correct 358 ms 92168 KB Output is correct
24 Correct 58 ms 28752 KB Output is correct
25 Correct 57 ms 28580 KB Output is correct
26 Correct 57 ms 28756 KB Output is correct
27 Correct 616 ms 116760 KB Output is correct
28 Correct 638 ms 116492 KB Output is correct
29 Correct 620 ms 116896 KB Output is correct
30 Correct 635 ms 117016 KB Output is correct
31 Correct 4 ms 17500 KB Output is correct
32 Correct 30 ms 23876 KB Output is correct
33 Correct 48 ms 33116 KB Output is correct
34 Correct 454 ms 104044 KB Output is correct
35 Correct 7 ms 18008 KB Output is correct
36 Correct 18 ms 20572 KB Output is correct
37 Correct 34 ms 23676 KB Output is correct
38 Correct 218 ms 50524 KB Output is correct
39 Correct 314 ms 62664 KB Output is correct
40 Correct 437 ms 75000 KB Output is correct
41 Correct 533 ms 87616 KB Output is correct
42 Correct 626 ms 99644 KB Output is correct
43 Correct 5 ms 17500 KB Output is correct
44 Correct 5 ms 17344 KB Output is correct
45 Correct 4 ms 17340 KB Output is correct
46 Correct 4 ms 17496 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 5 ms 17500 KB Output is correct
51 Correct 5 ms 17500 KB Output is correct
52 Correct 4 ms 17500 KB Output is correct
53 Correct 5 ms 17500 KB Output is correct
54 Correct 5 ms 17500 KB Output is correct
55 Correct 6 ms 17500 KB Output is correct
56 Correct 192 ms 60316 KB Output is correct
57 Correct 261 ms 78656 KB Output is correct
58 Correct 264 ms 78672 KB Output is correct
59 Correct 4 ms 17500 KB Output is correct
60 Correct 5 ms 17340 KB Output is correct
61 Correct 4 ms 17500 KB Output is correct
62 Correct 351 ms 95864 KB Output is correct
63 Correct 349 ms 95812 KB Output is correct
64 Correct 338 ms 95372 KB Output is correct
65 Correct 5 ms 17756 KB Output is correct
66 Correct 6 ms 18012 KB Output is correct
67 Correct 201 ms 58860 KB Output is correct
68 Correct 291 ms 79704 KB Output is correct
69 Correct 415 ms 99752 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 17500 KB Output is correct
2 Correct 4 ms 17500 KB Output is correct
3 Correct 5 ms 17500 KB Output is correct
4 Correct 6 ms 17500 KB Output is correct
5 Correct 5 ms 17500 KB Output is correct
6 Correct 4 ms 17500 KB Output is correct
7 Correct 4 ms 17500 KB Output is correct
8 Correct 5 ms 17508 KB Output is correct
9 Correct 159 ms 58384 KB Output is correct
10 Correct 17 ms 21596 KB Output is correct
11 Correct 85 ms 39356 KB Output is correct
12 Correct 24 ms 23588 KB Output is correct
13 Correct 15 ms 20584 KB Output is correct
14 Correct 4 ms 17500 KB Output is correct
15 Correct 7 ms 17500 KB Output is correct
16 Correct 166 ms 58504 KB Output is correct
17 Correct 394 ms 99740 KB Output is correct
18 Correct 465 ms 111004 KB Output is correct
19 Correct 439 ms 98796 KB Output is correct
20 Correct 570 ms 100516 KB Output is correct
21 Correct 568 ms 101088 KB Output is correct
22 Correct 4 ms 17496 KB Output is correct
23 Correct 67 ms 31416 KB Output is correct
24 Correct 11 ms 18780 KB Output is correct
25 Correct 24 ms 21728 KB Output is correct
26 Correct 38 ms 24660 KB Output is correct
27 Correct 284 ms 59592 KB Output is correct
28 Correct 362 ms 70648 KB Output is correct
29 Correct 457 ms 80672 KB Output is correct
30 Correct 540 ms 91100 KB Output is correct
31 Correct 608 ms 101352 KB Output is correct
32 Correct 393 ms 103588 KB Output is correct
33 Correct 361 ms 95720 KB Output is correct
34 Correct 5 ms 17756 KB Output is correct
35 Correct 7 ms 18012 KB Output is correct
36 Correct 189 ms 58632 KB Output is correct
37 Correct 287 ms 79528 KB Output is correct
38 Correct 394 ms 99500 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 17500 KB Output is correct
2 Correct 4 ms 17500 KB Output is correct
3 Correct 5 ms 17500 KB Output is correct
4 Correct 6 ms 17500 KB Output is correct
5 Correct 5 ms 17500 KB Output is correct
6 Correct 4 ms 17500 KB Output is correct
7 Correct 4 ms 17500 KB Output is correct
8 Correct 5 ms 17508 KB Output is correct
9 Correct 159 ms 58384 KB Output is correct
10 Correct 17 ms 21596 KB Output is correct
11 Correct 85 ms 39356 KB Output is correct
12 Correct 24 ms 23588 KB Output is correct
13 Correct 15 ms 20584 KB Output is correct
14 Correct 4 ms 17500 KB Output is correct
15 Correct 7 ms 17500 KB Output is correct
16 Correct 166 ms 58504 KB Output is correct
17 Correct 5 ms 17500 KB Output is correct
18 Correct 4 ms 17500 KB Output is correct
19 Correct 5 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 4 ms 17500 KB Output is correct
23 Correct 368 ms 95688 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 17556 KB Output is correct
27 Correct 5 ms 17496 KB Output is correct
28 Correct 139 ms 48584 KB Output is correct
29 Correct 237 ms 64264 KB Output is correct
30 Correct 313 ms 79228 KB Output is correct
31 Correct 397 ms 95628 KB Output is correct
32 Correct 4 ms 17500 KB Output is correct
33 Correct 5 ms 17500 KB Output is correct
34 Correct 5 ms 17496 KB Output is correct
35 Correct 5 ms 17500 KB Output is correct
36 Correct 4 ms 17500 KB Output is correct
37 Correct 4 ms 17500 KB Output is correct
38 Correct 4 ms 17500 KB Output is correct
39 Correct 5 ms 17500 KB Output is correct
40 Correct 4 ms 17500 KB Output is correct
41 Correct 4 ms 17500 KB Output is correct
42 Correct 4 ms 17500 KB Output is correct
43 Correct 5 ms 17500 KB Output is correct
44 Correct 5 ms 17500 KB Output is correct
45 Correct 185 ms 60268 KB Output is correct
46 Correct 259 ms 78492 KB Output is correct
47 Correct 271 ms 78608 KB Output is correct
48 Correct 5 ms 17500 KB Output is correct
49 Correct 4 ms 17500 KB Output is correct
50 Correct 4 ms 17472 KB Output is correct
51 Correct 4 ms 17908 KB Output is correct
52 Correct 4 ms 17496 KB Output is correct
53 Correct 4 ms 17500 KB Output is correct
54 Correct 5 ms 17496 KB Output is correct
55 Correct 418 ms 95052 KB Output is correct
56 Correct 4 ms 17500 KB Output is correct
57 Incorrect 3406 ms 17960 KB Solution announced impossible, but it is possible.
58 Halted 0 ms 0 KB -