Submission #410361

#	Time	Username	Problem	Language	Result	Execution time	Memory
410361		jhwest2	IOI Fever (JOI21_fever)	C++14	100 / 100	2345 ms	28992 KiB

fever

#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;

        // Using adjacent edges
        for (auto [e, y] : G[x][p]) {
            Q.emplace(d + e, pint(y, p));
        }
        // 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(x, *it) / 2, pint(*it, j));
        }
    }
    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++) {
        solve();
        // Rotate 90 degrees
        for (int j = 2; j <= n; j++) {
            swap(X[j], Y[j]); Y[j] = -Y[j];
        }
    }
    cout << ans << '\n';
}

Compilation message (stderr)

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:82:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   82 |         for (auto [e, y] : G[x][p]) {
      |                   ^

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 6 / 6
• Subtask 4: 6 / 6
• Subtask 5: 12 / 12
• Subtask 6: 32 / 32
• Subtask 7: 31 / 31