Submission #973948

#	Time	Username	Problem	Language	Result	Execution time	Memory
973948		alextodoran	IOI Fever (JOI21_fever)	C++17	19 / 100	1 ms	600 KiB

fever

/**
 _  _   __  _ _ _  _  _ _
 |a  ||t  ||o    d | |o  |
| __    _| | _ | __|  _ |
| __ |/_  | __  /__\ / _\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 100000;

const int UP = 0, LEFT = 1, DOWN = 2, RIGHT = 3;

int N;
int X[N_MAX + 2], Y[N_MAX + 2];
int order[N_MAX + 2];

unordered_map <int, vector <int>> D[4];

int dir[N_MAX + 2];

int min_len[N_MAX + 2];
bool seen[N_MAX + 2];
priority_queue <pair <int, int>> q;

/*
   1\ 0 /0
     \|/
    1-x-3
     /|\
   2/ 2 \3
*/

void go (int i) {
    if (dir[i] == UP || dir[i] == RIGHT) {
        int d = X[i] - Y[i];
        while (D[0][d].empty() == false) {
            int j = D[0][d].back();
            if (seen[j] == true) {
                D[0][d].pop_back();
            } else if (min_len[i] <= X[j] - X[i] && X[j] - X[i] < min_len[j]) {
                D[0][d].pop_back();
                min_len[j] = X[j] - X[i];
                q.push({-min_len[j], j});
            } else {
                break;
            }
        }
    }
    if (dir[i] == LEFT || dir[i] == UP) {
        int d = X[i] + Y[i];
        while (D[1][d].empty() == false) {
            int j = D[1][d].back();
            if (seen[j] == true) {
                D[1][d].pop_back();
            } else if (min_len[i] <= X[i] - X[j] && X[i] - X[j] < min_len[j]) {
                D[1][d].pop_back();
                min_len[j] = X[i] - X[j];
                q.push({-min_len[j], j});
            } else {
                break;
            }
        }
    }
    if (dir[i] == DOWN || dir[i] == LEFT) {
        int d = X[i] - Y[i];
        while (D[2][d].empty() == false) {
            int j = D[2][d].back();
            if (seen[j] == true) {
                D[2][d].pop_back();
            } else if (min_len[i] <= X[i] - X[j] && X[i] - X[j] < min_len[j]) {
                D[2][d].pop_back();
                min_len[j] = X[i] - X[j];
                q.push({-min_len[j], j});
            } else {
                break;
            }
        }
    }
    if (dir[i] == RIGHT || dir[i] == DOWN) {
        int d = X[i] + Y[i];
        while (D[3][d].empty() == false) {
            int j = D[3][d].back();
            if (seen[j] == true) {
                D[3][d].pop_back();
            } else if (min_len[i] <= X[j] - X[i] && X[j] - X[i] < min_len[j]) {
                D[3][d].pop_back();
                min_len[j] = X[j] - X[i];
                q.push({-min_len[j], j});
            } else {
                break;
            }
        }
    }
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> X[i] >> Y[i];
    }
    iota(order + 1, order + N + 1, 1);
    sort(order + 1, order + N + 1, [&] (const int &i, const int &j) {
        return X[i] < X[j];
    });
    int answer = 0;
    for (int d1 : {UP, LEFT, DOWN, RIGHT}) {
        for (int k = 1; k <= N; k++) {
            int i = order[k];
            D[0][X[i] - Y[i]].push_back(i);
            D[3][X[i] + Y[i]].push_back(i);
        }
        for (int k = N; k >= 1; k--) {
            int i = order[k];
            D[2][X[i] - Y[i]].push_back(i);
            D[1][X[i] + Y[i]].push_back(i);
        }
        dir[1] = d1;
        for (int i = 2; i <= N; i++) {
            if (abs(X[i] - X[1]) > abs(Y[i] - Y[1])) {
                dir[i] = (X[i] < X[1] ? RIGHT : LEFT);
            } else if (abs(Y[i] - Y[1]) > abs(X[i] - X[1])) {
                dir[i] = (Y[i] < Y[1] ? UP : DOWN);
            } else {
                if (d1 == UP) {
                    if (Y[i] < Y[1]) {
                        dir[i] = UP;
                    } else {
                        dir[i] = (X[i] < X[1] ? RIGHT : LEFT);
                    }
                }
                if (d1 == LEFT) {
                    if (X[i] > X[1]) {
                        dir[i] = LEFT;
                    } else {
                        dir[i] = (Y[i] < Y[1] ? UP : DOWN);
                    }
                }
                if (d1 == DOWN) {
                    if (Y[i] > Y[1]) {
                        dir[i] = DOWN;
                    } else {
                        dir[i] = (X[i] < X[1] ? RIGHT : LEFT);
                    }
                }
                if (d1 == RIGHT) {
                    if (X[i] < X[1]) {
                        dir[i] = RIGHT;
                    } else {
                        dir[i] = (Y[i] < Y[1] ? UP : DOWN);
                    }
                }
            }
        }
        fill(min_len + 1, min_len + N + 1, INT_MAX);
        fill(seen + 1, seen + N + 1, false);
        min_len[1] = 0; q.push({0, 1});
        int cnt = 0;
        while (q.empty() == false) {
            int i = q.top().second;
            q.pop();
            if (seen[i] == true) {
                continue;
            }
            seen[i] = true;
            cnt++;
            go(i);
        }
        answer = max(answer, cnt);
        for (int d : {0, 1, 2, 3}) {
            D[d].clear();
        }
    }
    cout << answer << "\n";

    return 0;
}

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