oj.uz

Submission #933829

# Submission time Handle Problem Language Result Execution time Memory
933829 2024-02-26T11:29:08 Z Pannda IOI Fever (JOI21_fever) C++17
6 / 100
 1 ms 420 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<array<int, 2>> a(n);
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        x *= 2;
        y *= 2;
        a[i] = {x, y};
    }

    // directions are 0.up 1.down 2.left 3.right
    auto solve = [](int n, vector<array<int, 2>> a, int dir0) -> int {
        map<int, set<array<int, 2>>> mp_hor, mp_ver, mp_up, mp_down;
        for (int i = 1; i < n; i++) {
            auto [x, y] = a[i];
            mp_up[y - x].insert({x, i});
            mp_down[y + x].insert({x, i});
            mp_hor[y].insert({x, i});
            mp_ver[x].insert({y, i});
        }
        queue<array<int, 3>> que;
        vector<bool> vis(n, false);
        que.push({0, dir0, 0});
        vis[0] = true;
        while (!que.empty()) {
            auto [i, dir, d] = que.front();
            auto [x, y] = a[i];
//            cout << x / 2 << ' ' << y / 2 << ' ' << dir << ' ' << d << '\n';
            que.pop();

            if (dir == 0) {
                {
                    auto it = mp_ver.find(x);
                    if (it != mp_ver.end()) {
                        while (!it->second.empty()) {
                            auto [yy, ii] = *prev(it->second.end());
                            if (vis[ii]) {
                                it->second.erase(prev(it->second.end()));
                                continue;
                            }
                            if (yy >= y + 2 * d) {
                                it->second.erase(prev(it->second.end()));
                                vis[ii] = true;
                                que.push({ii, 1, abs(y - yy) / 2});
                                continue;
                            }
                            break;
                        }
                        if (it->second.empty()) mp_ver.erase(it);
                    }
                }
                {
                    auto it = mp_up.find(y - x);
                    if (it != mp_up.end()) {
                        while (!it->second.empty()) {
                            auto [xx, ii] = *prev(it->second.end());
                            if (vis[ii]) {
                                it->second.erase(prev(it->second.end()));
                                continue;
                            }
                            if (xx >= x + d) {
                                it->second.erase(prev(it->second.end()));
                                vis[ii] = true;
                                que.push({ii, 2, abs(x - xx)});
                                continue;
                            }
                            break;
                        }
                        if (it->second.empty()) mp_up.erase(it);
                    }
                }
                {
                    auto it = mp_down.find(y + x);
                    if (it != mp_down.end()) {
                        while (!it->second.empty()) {
                            auto [xx, ii] = *(it->second.begin());
                            if (vis[ii]) {
                                it->second.erase(it->second.begin());
                                continue;
                            }
                            if (xx <= x - d) {
                                it->second.erase(it->second.begin());
                                vis[ii] = true;
                                que.push({ii, 3, abs(x - xx)});
                                continue;
                            }
                            break;
                        }
                        if (it->second.empty()) mp_down.erase(it);
                    }
                }
            }

            if (dir == 1) {
                {
                    auto it = mp_ver.find(x);
                    if (it != mp_ver.end()) {
                        while (!it->second.empty()) {
                            auto [yy, ii] = *(it->second.begin());
                            if (vis[ii]) {
                                it->second.erase(it->second.begin());
                                continue;
                            }
                            if (yy <= y - 2 * d) {
                                it->second.erase(it->second.begin());
                                vis[ii] = true;
                                que.push({ii, 0, abs(y - yy) / 2});
                                continue;
                            }
                            break;
                        }
                        if (it->second.empty()) mp_ver.erase(it);
                    }
                }
                {
                    auto it = mp_up.find(y - x);
                    if (it != mp_up.end()) {
                        while (!it->second.empty()) {
                            auto [xx, ii] = *(it->second.begin());
                            if (vis[ii]) {
                                it->second.erase(it->second.begin());
                                continue;
                            }
                            if (xx <= x - d) {
                                it->second.erase(it->second.begin());
                                vis[ii] = true;
                                que.push({ii, 3, abs(x - xx)});
                                continue;
                            }
                            break;
                        }
                        if (it->second.empty()) mp_up.erase(it);
                    }
                }
                {
                    auto it = mp_down.find(y + x);
                    if (it != mp_down.end()) {
                        while (!it->second.empty()) {
                            auto [xx, ii] = *prev(it->second.end());
                            if (vis[ii]) {
                                it->second.erase(prev(it->second.end()));
                                continue;
                            }
                            if (xx >= x + d) {
                                it->second.erase(prev(it->second.end()));
                                vis[ii] = true;
                                que.push({ii, 2, abs(x - xx)});
                                continue;
                            }
                            break;
                        }
                        if (it->second.empty()) mp_down.erase(it);
                    }
                }
            }

            if (dir == 2) {
                {
                    auto it = mp_hor.find(y);
                    if (it != mp_hor.end()) {
                        while (!it->second.empty()) {
                            auto [xx, ii] = *(it->second.begin());
                            if (vis[ii]) {
                                it->second.erase(it->second.begin());
                                continue;
                            }
                            if (xx <= x - 2 * d) {
                                it->second.erase(it->second.begin());
                                vis[ii] = true;
                                que.push({ii, 3, abs(x - xx) / 2});
                                continue;
                            }
                            break;
                        }
                        if (it->second.empty()) mp_hor.erase(it);
                    }
                }
                {
                    auto it = mp_up.find(y - x);
                    if (it != mp_up.end()) {
                        while (!it->second.empty()) {
                            auto [xx, ii] = *(it->second.begin());
                            if (vis[ii]) {
                                it->second.erase(it->second.begin());
                                continue;
                            }
                            if (xx <= x - d) {
                                it->second.erase(it->second.begin());
                                vis[ii] = true;
                                que.push({ii, 0, abs(x - xx)});
                                continue;
                            }
                            break;
                        }
                        if (it->second.empty()) mp_up.erase(it);
                    }
                }
                {
                    auto it = mp_down.find(y + x);
                    if (it != mp_down.end()) {
                        while (!it->second.empty()) {
                            auto [xx, ii] = *(it->second.begin());
                            if (vis[ii]) {
                                it->second.erase(it->second.begin());
                                continue;
                            }
                            if (xx <= x - d) {
                                it->second.erase(it->second.begin());
                                vis[ii] = true;
                                que.push({ii, 1, abs(x - xx)});
                                continue;
                            }
                            break;
                        }
                        if (it->second.empty()) mp_down.erase(it);
                    }
                }
            }

            if (dir == 3) {
                {
                    auto it = mp_hor.find(y);
                    if (it != mp_hor.end()) {
                        while (!it->second.empty()) {
                            auto [xx, ii] = *prev(it->second.end());
                            if (vis[ii]) {
                                it->second.erase(prev(it->second.end()));
                                continue;
                            }
                            if (xx >= x + 2 * d) {
                                it->second.erase(prev(it->second.end()));
                                vis[ii] = true;
                                que.push({ii, 2, abs(x - xx) / 2});
                                continue;
                            }
                            break;
                        }
                        if (it->second.empty()) mp_hor.erase(it);
                    }
                }
                {
                    auto it = mp_up.find(y - x);
                    if (it != mp_up.end()) {
                        while (!it->second.empty()) {
                            auto [xx, ii] = *prev(it->second.end());
                            if (vis[ii]) {
                                it->second.erase(prev(it->second.end()));
                                continue;
                            }
                            if (xx >= x + d) {
                                it->second.erase(prev(it->second.end()));
                                vis[ii] = true;
                                que.push({ii, 1, abs(x - xx)});
                                continue;
                            }
                            break;
                        }
                        if (it->second.empty()) mp_up.erase(it);
                    }
                }
                {
                    auto it = mp_down.find(y + x);
                    if (it != mp_down.end()) {
                        while (!it->second.empty()) {
                            auto [xx, ii] = *prev(it->second.end());
                            if (vis[ii]) {
                                it->second.erase(prev(it->second.end()));
                                continue;
                            }
                            if (xx >= x + d) {
                                it->second.erase(prev(it->second.end()));
                                vis[ii] = true;
                                que.push({ii, 0, abs(x - xx)});
                                continue;
                            }
                            break;
                        }
                        if (it->second.empty()) mp_down.erase(it);
                    }
                }
            }
        }
        return count(vis.begin(), vis.end(), true);
    };

    cout << max({solve(n, a, 0), solve(n, a, 1), solve(n, a, 2), solve(n, a, 3)}) << '\n';
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 408 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 0 ms 344 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 420 KB Output is correct
29 Correct 0 ms 344 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Incorrect 0 ms 348 KB Output isn't correct
33 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 408 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 0 ms 344 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 420 KB Output is correct
29 Correct 0 ms 344 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Incorrect 0 ms 348 KB Output isn't correct
33 Halted 0 ms 0 KB -

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 408 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 0 ms 344 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 420 KB Output is correct
29 Correct 0 ms 344 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Incorrect 0 ms 348 KB Output isn't correct
33 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 408 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 0 ms 344 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 420 KB Output is correct
29 Correct 0 ms 344 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Incorrect 0 ms 348 KB Output isn't correct
33 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 408 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 0 ms 344 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 420 KB Output is correct
29 Correct 0 ms 344 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Incorrect 0 ms 348 KB Output isn't correct
33 Halted 0 ms 0 KB -

Subtask #7
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 408 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 0 ms 344 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 420 KB Output is correct
29 Correct 0 ms 344 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Incorrect 0 ms 348 KB Output isn't correct
33 Halted 0 ms 0 KB -