oj.uz

Submission #410356

# Submission time Handle Problem Language Result Execution time Memory
410356 2021-05-22T14:59:33 Z jhwest2 IOI Fever (JOI21_fever) C++14
11 / 100
 10 ms 11724 KB 
#include <bits/stdc++.h>
#define va first
#define vb second
using namespace std;
typedef long long lint;
typedef pair<int, int> pint;
typedef pair<int, pint> pip;

const int M = 1e5 + 10;
const int Dx[8] = { 2, 1, 0, -1, -2, -1, 0, 1 };
const int Dy[8] = { 0, 1, 2, 1, 0, -1, -2, -1 };

int n, ans, X[M], Y[M], Dir[M], Dist[M][4], Chk[M];
vector<int> V[8][3];
vector<pint> G[M][4];

int dist(int a, int b) {
    return abs(X[a] - X[b]) + abs(Y[a] - Y[b]);
}
int get_x(int a, int axis) {
    return X[a] * Dx[axis] + Y[a] * Dy[axis];
}
void solve() {
    // 0 = Right, 2 = Up, 4 = Left, 6 = Down;
    // 1 = Right-Up, 3 = Left-Up, 5 = Left-Down, 7 = Right-Down
    for (int i = 2; i <= n; i++) {
        if (Y[i] >= X[i] && Y[i] <= -X[i]) Dir[i] = 0;
        if (Y[i] < X[i] && Y[i] <= -X[i]) Dir[i] = 2;
        if (Y[i] < X[i] && Y[i] > -X[i]) Dir[i] = 4;
        if (Y[i] >= X[i] && Y[i] > -X[i]) Dir[i] = 6;
    }
    // V[i][j] : Vertices with direction j, when we set direction i as right
    // 0 : y = x, 1 : y = 0, 2 : y = -x;
    for (int j = 0; j < 3; j++) {
        for (int i = 0; i < 8; i += 2) V[i][j].clear();
    }
    for (int i = 1; i <= n; i++) {
        V[(Dir[i] + 2) % 8][0].push_back(i);
        V[(Dir[i] + 4) % 8][1].push_back(i);
        V[(Dir[i] + 6) % 8][2].push_back(i);
    }
    for (int i = 0; i < 8; i += 2) {
        for (int j = 0; j < 3; j++) {
            // Direction of x-axis, y-axis
            int dx = (i - j + 7) % 8, dy = (i - j + 9) % 8;
            sort(V[i][j].begin(), V[i][j].end(), [&](int a, int b) {
                pint u = { get_x(a, dx), get_x(a, dy) };
                pint v = { get_x(b, dx), get_x(b, dy) };
                return u < v;
                });
        }
    }
    // Add edges between adjacent vertices
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < 3; j++) G[i][j].clear();
    }
    for (int i = 0; i < 8; i += 2) for (int j = 0; j < 3; j++) {
        int dx = (i - j + 7) % 8;
        for (int k = 0; k + 1 < V[i][j].size(); k++) {
            int u = V[i][j][k], v = V[i][j][k + 1];
            if (get_x(u, dx) != get_x(v, dx)) continue;
            G[u][j].emplace_back(dist(u, v) / 2, v);
        }
    }
    /* for (int i = 1; i <= n; i++) {
        cout << i << "!\n";
        for (auto [d, x] : G[i]) {
            cout << d << ' ' << x << '\n';
        }
    } */
    // Run Dijkstra
    priority_queue<pip, vector<pip>, greater<pip>> Q;
    Q.emplace(0, pint(1, 3));
    memset(Dist, -1, sizeof Dist); memset(Chk, 0, sizeof Chk);
    int cnt = 0;
    while (!Q.empty()) {
        auto [d, t] = Q.top(); auto [x, p] = t; Q.pop();
        if (Dist[x][p] != -1) continue; Dist[x][p] = d;
        if (!Chk[x]) ++cnt; Chk[x] = 1;
        // cout << x << '\n';

        // Using adjacent edges
        for (auto [e, y] : G[x][p]) {
            Q.emplace(d + e, pint(y, p));
            //cout << x << " -> " << y << ": " << d + e << '\n';
        }
        // Transfer state
        int i = Dir[x];
        for (int j = 0; j < 3; j++) {
            int dx = (i - j + 7) % 8, dy = (i - j + 9) % 8;
            X[0] = X[x] + Dx[dy] * d;
            Y[0] = Y[x] + Dy[dy] * d;
            auto it = lower_bound(V[i][j].begin(), V[i][j].end(), 0, [&](int a, int b) {
                pint u = { get_x(a, dx), get_x(a, dy) };
                pint v = { get_x(b, dx), get_x(b, dy) };
                return u == v ? a < b : u < v;
                });

            if (it == V[i][j].end() || get_x(0, dx) != get_x(*it, dx)) continue;

            Q.emplace(dist(0, *it) / 2, pint(*it, j));
            //cout << x << ' ' << "in Direction " << j << ": " << *it << '\n';
           // cout << Dist[x][p] << ' ' << X[x] << ' ' << Y[x] << ' ' << X[0] << ' ' << Y[0] << '\n';
        }
    }
    ans = max(ans, cnt);
}
int main() {
    //cin.tie(0); ios_base::sync_with_stdio(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> X[i] >> Y[i];
        X[i] *= 2; Y[i] *= 2;
        if (i >= 2) X[i] -= X[1], Y[i] -= Y[1];
    }
    X[1] = Y[1] = 0;

    for (int i = 0; i < 4; i++) {
        // cout << i << "!\n";
        solve();
        // Rotate 90 degrees
        for (int j = 2; j <= n; j++) {
            swap(X[j], Y[j]); Y[j] = -Y[j];
        }
    }
    cout << ans;
}

Compilation message

fever.cpp: In function 'void solve()':
fever.cpp:59:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |         for (int k = 0; k + 1 < V[i][j].size(); k++) {
      |                         ~~~~~~^~~~~~~~~~~~~~~~
fever.cpp:77:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   77 |         auto [d, t] = Q.top(); auto [x, p] = t; Q.pop();
      |              ^
fever.cpp:77:37: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   77 |         auto [d, t] = Q.top(); auto [x, p] = t; Q.pop();
      |                                     ^
fever.cpp:78:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   78 |         if (Dist[x][p] != -1) continue; Dist[x][p] = d;
      |         ^~
fever.cpp:78:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   78 |         if (Dist[x][p] != -1) continue; Dist[x][p] = d;
      |                                         ^~~~
fever.cpp:79:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   79 |         if (!Chk[x]) ++cnt; Chk[x] = 1;
      |         ^~
fever.cpp:79:29: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   79 |         if (!Chk[x]) ++cnt; Chk[x] = 1;
      |                             ^~~
fever.cpp:83:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   83 |         for (auto [e, y] : G[x][p]) {
      |                   ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11596 KB Output is correct
2 Correct 8 ms 11652 KB Output is correct
3 Correct 8 ms 11596 KB Output is correct
4 Correct 8 ms 11552 KB Output is correct
5 Correct 8 ms 11664 KB Output is correct
6 Correct 8 ms 11612 KB Output is correct
7 Correct 8 ms 11548 KB Output is correct
8 Correct 8 ms 11612 KB Output is correct
9 Correct 8 ms 11596 KB Output is correct
10 Correct 8 ms 11596 KB Output is correct
11 Correct 8 ms 11608 KB Output is correct
12 Correct 8 ms 11596 KB Output is correct
13 Correct 8 ms 11724 KB Output is correct
14 Correct 8 ms 11616 KB Output is correct
15 Correct 8 ms 11596 KB Output is correct
16 Correct 8 ms 11596 KB Output is correct
17 Correct 8 ms 11596 KB Output is correct
18 Correct 8 ms 11596 KB Output is correct
19 Correct 8 ms 11596 KB Output is correct
20 Correct 8 ms 11596 KB Output is correct
21 Correct 8 ms 11596 KB Output is correct
22 Correct 8 ms 11616 KB Output is correct
23 Correct 8 ms 11612 KB Output is correct
24 Correct 8 ms 11576 KB Output is correct
25 Correct 8 ms 11620 KB Output is correct
26 Correct 8 ms 11596 KB Output is correct
27 Correct 8 ms 11596 KB Output is correct
28 Correct 8 ms 11596 KB Output is correct
29 Correct 8 ms 11596 KB Output is correct
30 Correct 8 ms 11596 KB Output is correct
31 Correct 8 ms 11596 KB Output is correct
32 Correct 8 ms 11616 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11596 KB Output is correct
2 Correct 8 ms 11652 KB Output is correct
3 Correct 8 ms 11596 KB Output is correct
4 Correct 8 ms 11552 KB Output is correct
5 Correct 8 ms 11664 KB Output is correct
6 Correct 8 ms 11612 KB Output is correct
7 Correct 8 ms 11548 KB Output is correct
8 Correct 8 ms 11612 KB Output is correct
9 Correct 8 ms 11596 KB Output is correct
10 Correct 8 ms 11596 KB Output is correct
11 Correct 8 ms 11608 KB Output is correct
12 Correct 8 ms 11596 KB Output is correct
13 Correct 8 ms 11724 KB Output is correct
14 Correct 8 ms 11616 KB Output is correct
15 Correct 8 ms 11596 KB Output is correct
16 Correct 8 ms 11596 KB Output is correct
17 Correct 8 ms 11596 KB Output is correct
18 Correct 8 ms 11596 KB Output is correct
19 Correct 8 ms 11596 KB Output is correct
20 Correct 8 ms 11596 KB Output is correct
21 Correct 8 ms 11596 KB Output is correct
22 Correct 8 ms 11616 KB Output is correct
23 Correct 8 ms 11612 KB Output is correct
24 Correct 8 ms 11576 KB Output is correct
25 Correct 8 ms 11620 KB Output is correct
26 Correct 8 ms 11596 KB Output is correct
27 Correct 8 ms 11596 KB Output is correct
28 Correct 8 ms 11596 KB Output is correct
29 Correct 8 ms 11596 KB Output is correct
30 Correct 8 ms 11596 KB Output is correct
31 Correct 8 ms 11596 KB Output is correct
32 Correct 8 ms 11616 KB Output is correct
33 Correct 8 ms 11596 KB Output is correct
34 Correct 8 ms 11616 KB Output is correct
35 Correct 8 ms 11596 KB Output is correct
36 Correct 8 ms 11640 KB Output is correct
37 Correct 8 ms 11596 KB Output is correct
38 Correct 8 ms 11596 KB Output is correct
39 Correct 8 ms 11596 KB Output is correct
40 Correct 8 ms 11596 KB Output is correct
41 Correct 8 ms 11596 KB Output is correct
42 Correct 8 ms 11624 KB Output is correct
43 Correct 8 ms 11596 KB Output is correct
44 Correct 8 ms 11588 KB Output is correct
45 Incorrect 9 ms 11616 KB Output isn't correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11596 KB Output is correct
2 Correct 8 ms 11596 KB Output is correct
3 Correct 8 ms 11648 KB Output is correct
4 Correct 8 ms 11596 KB Output is correct
5 Correct 10 ms 11596 KB Output is correct
6 Correct 8 ms 11600 KB Output is correct
7 Correct 8 ms 11596 KB Output is correct
8 Correct 8 ms 11632 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11596 KB Output is correct
2 Correct 8 ms 11652 KB Output is correct
3 Correct 8 ms 11596 KB Output is correct
4 Correct 8 ms 11552 KB Output is correct
5 Correct 8 ms 11664 KB Output is correct
6 Correct 8 ms 11612 KB Output is correct
7 Correct 8 ms 11548 KB Output is correct
8 Correct 8 ms 11612 KB Output is correct
9 Correct 8 ms 11596 KB Output is correct
10 Correct 8 ms 11596 KB Output is correct
11 Correct 8 ms 11608 KB Output is correct
12 Correct 8 ms 11596 KB Output is correct
13 Correct 8 ms 11724 KB Output is correct
14 Correct 8 ms 11616 KB Output is correct
15 Correct 8 ms 11596 KB Output is correct
16 Correct 8 ms 11596 KB Output is correct
17 Correct 8 ms 11596 KB Output is correct
18 Correct 8 ms 11596 KB Output is correct
19 Correct 8 ms 11596 KB Output is correct
20 Correct 8 ms 11596 KB Output is correct
21 Correct 8 ms 11596 KB Output is correct
22 Correct 8 ms 11616 KB Output is correct
23 Correct 8 ms 11612 KB Output is correct
24 Correct 8 ms 11576 KB Output is correct
25 Correct 8 ms 11620 KB Output is correct
26 Correct 8 ms 11596 KB Output is correct
27 Correct 8 ms 11596 KB Output is correct
28 Correct 8 ms 11596 KB Output is correct
29 Correct 8 ms 11596 KB Output is correct
30 Correct 8 ms 11596 KB Output is correct
31 Correct 8 ms 11596 KB Output is correct
32 Correct 8 ms 11616 KB Output is correct
33 Correct 8 ms 11596 KB Output is correct
34 Correct 8 ms 11616 KB Output is correct
35 Correct 8 ms 11596 KB Output is correct
36 Correct 8 ms 11640 KB Output is correct
37 Correct 8 ms 11596 KB Output is correct
38 Correct 8 ms 11596 KB Output is correct
39 Correct 8 ms 11596 KB Output is correct
40 Correct 8 ms 11596 KB Output is correct
41 Correct 8 ms 11596 KB Output is correct
42 Correct 8 ms 11624 KB Output is correct
43 Correct 8 ms 11596 KB Output is correct
44 Correct 8 ms 11588 KB Output is correct
45 Incorrect 9 ms 11616 KB Output isn't correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11596 KB Output is correct
2 Correct 8 ms 11652 KB Output is correct
3 Correct 8 ms 11596 KB Output is correct
4 Correct 8 ms 11552 KB Output is correct
5 Correct 8 ms 11664 KB Output is correct
6 Correct 8 ms 11612 KB Output is correct
7 Correct 8 ms 11548 KB Output is correct
8 Correct 8 ms 11612 KB Output is correct
9 Correct 8 ms 11596 KB Output is correct
10 Correct 8 ms 11596 KB Output is correct
11 Correct 8 ms 11608 KB Output is correct
12 Correct 8 ms 11596 KB Output is correct
13 Correct 8 ms 11724 KB Output is correct
14 Correct 8 ms 11616 KB Output is correct
15 Correct 8 ms 11596 KB Output is correct
16 Correct 8 ms 11596 KB Output is correct
17 Correct 8 ms 11596 KB Output is correct
18 Correct 8 ms 11596 KB Output is correct
19 Correct 8 ms 11596 KB Output is correct
20 Correct 8 ms 11596 KB Output is correct
21 Correct 8 ms 11596 KB Output is correct
22 Correct 8 ms 11616 KB Output is correct
23 Correct 8 ms 11612 KB Output is correct
24 Correct 8 ms 11576 KB Output is correct
25 Correct 8 ms 11620 KB Output is correct
26 Correct 8 ms 11596 KB Output is correct
27 Correct 8 ms 11596 KB Output is correct
28 Correct 8 ms 11596 KB Output is correct
29 Correct 8 ms 11596 KB Output is correct
30 Correct 8 ms 11596 KB Output is correct
31 Correct 8 ms 11596 KB Output is correct
32 Correct 8 ms 11616 KB Output is correct
33 Correct 8 ms 11596 KB Output is correct
34 Correct 8 ms 11616 KB Output is correct
35 Correct 8 ms 11596 KB Output is correct
36 Correct 8 ms 11640 KB Output is correct
37 Correct 8 ms 11596 KB Output is correct
38 Correct 8 ms 11596 KB Output is correct
39 Correct 8 ms 11596 KB Output is correct
40 Correct 8 ms 11596 KB Output is correct
41 Correct 8 ms 11596 KB Output is correct
42 Correct 8 ms 11624 KB Output is correct
43 Correct 8 ms 11596 KB Output is correct
44 Correct 8 ms 11588 KB Output is correct
45 Incorrect 9 ms 11616 KB Output isn't correct

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11596 KB Output is correct
2 Correct 8 ms 11652 KB Output is correct
3 Correct 8 ms 11596 KB Output is correct
4 Correct 8 ms 11552 KB Output is correct
5 Correct 8 ms 11664 KB Output is correct
6 Correct 8 ms 11612 KB Output is correct
7 Correct 8 ms 11548 KB Output is correct
8 Correct 8 ms 11612 KB Output is correct
9 Correct 8 ms 11596 KB Output is correct
10 Correct 8 ms 11596 KB Output is correct
11 Correct 8 ms 11608 KB Output is correct
12 Correct 8 ms 11596 KB Output is correct
13 Correct 8 ms 11724 KB Output is correct
14 Correct 8 ms 11616 KB Output is correct
15 Correct 8 ms 11596 KB Output is correct
16 Correct 8 ms 11596 KB Output is correct
17 Correct 8 ms 11596 KB Output is correct
18 Correct 8 ms 11596 KB Output is correct
19 Correct 8 ms 11596 KB Output is correct
20 Correct 8 ms 11596 KB Output is correct
21 Correct 8 ms 11596 KB Output is correct
22 Correct 8 ms 11616 KB Output is correct
23 Correct 8 ms 11612 KB Output is correct
24 Correct 8 ms 11576 KB Output is correct
25 Correct 8 ms 11620 KB Output is correct
26 Correct 8 ms 11596 KB Output is correct
27 Correct 8 ms 11596 KB Output is correct
28 Correct 8 ms 11596 KB Output is correct
29 Correct 8 ms 11596 KB Output is correct
30 Correct 8 ms 11596 KB Output is correct
31 Correct 8 ms 11596 KB Output is correct
32 Correct 8 ms 11616 KB Output is correct
33 Correct 8 ms 11596 KB Output is correct
34 Correct 8 ms 11616 KB Output is correct
35 Correct 8 ms 11596 KB Output is correct
36 Correct 8 ms 11640 KB Output is correct
37 Correct 8 ms 11596 KB Output is correct
38 Correct 8 ms 11596 KB Output is correct
39 Correct 8 ms 11596 KB Output is correct
40 Correct 8 ms 11596 KB Output is correct
41 Correct 8 ms 11596 KB Output is correct
42 Correct 8 ms 11624 KB Output is correct
43 Correct 8 ms 11596 KB Output is correct
44 Correct 8 ms 11588 KB Output is correct
45 Incorrect 9 ms 11616 KB Output isn't correct

Subtask #7
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11596 KB Output is correct
2 Correct 8 ms 11652 KB Output is correct
3 Correct 8 ms 11596 KB Output is correct
4 Correct 8 ms 11552 KB Output is correct
5 Correct 8 ms 11664 KB Output is correct
6 Correct 8 ms 11612 KB Output is correct
7 Correct 8 ms 11548 KB Output is correct
8 Correct 8 ms 11612 KB Output is correct
9 Correct 8 ms 11596 KB Output is correct
10 Correct 8 ms 11596 KB Output is correct
11 Correct 8 ms 11608 KB Output is correct
12 Correct 8 ms 11596 KB Output is correct
13 Correct 8 ms 11724 KB Output is correct
14 Correct 8 ms 11616 KB Output is correct
15 Correct 8 ms 11596 KB Output is correct
16 Correct 8 ms 11596 KB Output is correct
17 Correct 8 ms 11596 KB Output is correct
18 Correct 8 ms 11596 KB Output is correct
19 Correct 8 ms 11596 KB Output is correct
20 Correct 8 ms 11596 KB Output is correct
21 Correct 8 ms 11596 KB Output is correct
22 Correct 8 ms 11616 KB Output is correct
23 Correct 8 ms 11612 KB Output is correct
24 Correct 8 ms 11576 KB Output is correct
25 Correct 8 ms 11620 KB Output is correct
26 Correct 8 ms 11596 KB Output is correct
27 Correct 8 ms 11596 KB Output is correct
28 Correct 8 ms 11596 KB Output is correct
29 Correct 8 ms 11596 KB Output is correct
30 Correct 8 ms 11596 KB Output is correct
31 Correct 8 ms 11596 KB Output is correct
32 Correct 8 ms 11616 KB Output is correct
33 Correct 8 ms 11596 KB Output is correct
34 Correct 8 ms 11616 KB Output is correct
35 Correct 8 ms 11596 KB Output is correct
36 Correct 8 ms 11640 KB Output is correct
37 Correct 8 ms 11596 KB Output is correct
38 Correct 8 ms 11596 KB Output is correct
39 Correct 8 ms 11596 KB Output is correct
40 Correct 8 ms 11596 KB Output is correct
41 Correct 8 ms 11596 KB Output is correct
42 Correct 8 ms 11624 KB Output is correct
43 Correct 8 ms 11596 KB Output is correct
44 Correct 8 ms 11588 KB Output is correct
45 Incorrect 9 ms 11616 KB Output isn't correct