Submission #802058

#	Time	Username	Problem	Language	Result	Execution time	Memory
802058		puppy	IOI Fever (JOI21_fever)	C++17	0 / 100	31 ms	59872 KiB

fever

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <functional>
#define all(v) (v).begin(), (v).end()
using namespace std;
struct Dot
{
    int x, y;
};
int N;
Dot dot[100005];
int dir[100005];
int dis[100005][8];
const int inf = 1e9;
vector<pair<int, int>> line[4][100005][4];
vector<pair<int, int>> minor[100005][8];
int id[100005][4];
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("sample-05-in.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> dot[i].x >> dot[i].y;
        if (i >= 2) {
            dot[i].x -= dot[1].x;
            dot[i].y -= dot[1].y;
        }
    }
    dot[1] = {0, 0};
    int ans = 0;
    for (int k = 0; k < 4; k++) {
        for (int i = 2; i <= N; i++) {
            if (dot[i].y < dot[i].x && -dot[i].x < dot[i].y) {
                dir[i] = 2;
            }
            else if (dot[i].y >= dot[i].x && dot[i].y > -dot[i].x) {
                dir[i] = 3;
            }
            else if (dot[i].y < dot[i].x && dot[i].y <= -dot[i].x) {
                dir[i] = 1;
            }
            else {
                dir[i] = 0;
            }
        }
        vector<int> cpx[4];
        for (int i = 1; i <= N; i++) {
            cpx[0].push_back(dot[i].y - dot[i].x);
            cpx[1].push_back(dot[i].x + dot[i].y);
            cpx[2].push_back(dot[i].y);
            cpx[3].push_back(dot[i].x);
        }
        for (int k = 0; k < 4; k++) {
            sort(all(cpx[k]));
            cpx[k].erase(unique(all(cpx[k])), cpx[k].end());
        }
        auto lb = [&](int k, int i)
        {
            return lower_bound(all(cpx[k]), i) - cpx[k].begin();
        };
        for (int k = 0; k < 4; k++) {
            for (int i = 0; i < (int)cpx[k].size(); i++) {
                for (int j = 0; j < 4; j++) {
                    line[k][i][j].clear();
                }
            }
        }
        for (int i = 1; i <= N; i++) {
            for (int j = 0; j < 8; j++) {
                minor[i][j].clear();
            }
        }
        for (int i = 1; i <= N; i++) {
            id[i][0] = lb(0, dot[i].y - dot[i].x);
            id[i][1] = lb(1, dot[i].y + dot[i].x);
            id[i][2] = lb(2, dot[i].y);
            id[i][3] = lb(3, dot[i].x);
            line[0][id[i][0]][dir[i]].push_back(make_pair(dot[i].x, i));
            line[1][id[i][1]][dir[i]].push_back(make_pair(dot[i].x, i));
            line[2][id[i][2]][dir[i]].push_back(make_pair(dot[i].x, i));
            line[3][id[i][3]][dir[i]].push_back(make_pair(dot[i].y, i));
        }
        for (int k = 0; k < 4; k++) {
            for (int i = 0; i < (int)cpx[k].size(); i++) {
                for (int j = 0; j < 4; j++) {
                    sort(all(line[k][i][j]));
                    for (int l = 0; l < (int)line[k][i][j].size() - 1; l++) {
                        if (k < 2) {
                            minor[line[k][i][j][l].second][2*k].push_back(make_pair(2 * (line[k][i][j][l+1].first - line[k][i][j][l].first), line[k][i][j][l+1].second));
                            minor[line[k][i][j][l+1].second][2*k+1].push_back(make_pair(2 * (line[k][i][j][l+1].first - line[k][i][j][l].first), line[k][i][j][l].second));
                        }
                        else {
                            minor[line[k][i][j][l].second][2*k].push_back(make_pair(line[k][i][j][l+1].first - line[k][i][j][l].first, line[k][i][j][l+1].second));
                            minor[line[k][i][j][l+1].second][2*k+1].push_back(make_pair(line[k][i][j][l+1].first - line[k][i][j][l].first, line[k][i][j][l].second));
                        }
                    }
                }
            }
        }
        fill(&dis[0][0], &dis[100004][8], inf);
        priority_queue<pair<int, pair<int, int>>> pq; pq.push(make_pair(0, make_pair(1, -1)));
        while (!pq.empty()) {
            int ver = pq.top().second.first, state = pq.top().second.second, now = -pq.top().first;
            pq.pop();
            if (state != -1) {
                for (pair<int, int> p: minor[ver][state]) {
                    int nxt = p.second, newdis = now + p.first;
                    if (dis[nxt][state] > newdis) {
                        dis[nxt][state] = newdis;
                        pq.push(make_pair(-newdis, make_pair(nxt, state)));
                    }
                }
            }
            if (dir[ver] == 0) {
                auto it = lower_bound(all(line[0][id[ver][0]][3]), make_pair(dot[ver].x + (now + 1) / 2, -1));
                if (it != line[0][id[ver][0]][3].end() && dis[(*it).second][0] > 2 * ((*it).first - dot[ver].x)) {
                    dis[(*it).second][0] = 2 * ((*it).first - dot[ver].x);
                    pq.push(make_pair(-dis[(*it).second][0], make_pair((*it).second, 0)));
                }
                auto it2 = lower_bound(all(line[1][id[ver][1]][1]), make_pair(dot[ver].x + (now + 1) / 2, -1));
                if (it2 != line[1][id[ver][1]][1].end() && dis[(*it2).second][2] > 2 * ((*it2).first - dot[ver].x)) {
                    dis[(*it2).second][2] = 2 * ((*it2).first - dot[ver].x);
                    pq.push(make_pair(-dis[(*it2).second][2], make_pair((*it2).second, 2)));
                }
                auto it3 = lower_bound(all(line[2][id[ver][2]][2]), make_pair(dot[ver].x + now, -1));
                if (it3 != line[2][id[ver][2]][2].end() && dis[(*it3).second][4] > (*it3).first - dot[ver].x) {
                    dis[(*it3).second][4] = (*it3).first - dot[ver].x;
                    pq.push(make_pair(-dis[(*it3).second][4], make_pair((*it3).second, 4)));
                }
            }
            else if (dir[ver] == 1) {
                auto it = lower_bound(all(line[0][id[ver][0]][2]), make_pair(dot[ver].x + (now + 1) / 2, -1));
                if (it != line[0][id[ver][0]][2].end() && dis[(*it).second][0] > 2 * ((*it).first - dot[ver].x)) {
                    dis[(*it).second][0] = 2 * ((*it).first - dot[ver].x);
                    pq.push(make_pair(-dis[(*it).second][0], make_pair((*it).second, 0)));
                }
                auto it2 = lower_bound(all(line[1][id[ver][1]][0]), make_pair(dot[ver].x - (now + 1) / 2 + 1, -1));
                if (it2 != line[1][id[ver][1]][0].begin()) {
                    --it2;
                    if (dis[(*it2).second][3] > 2 * (dot[ver].x - (*it2).first)) {
                        dis[(*it2).second][3] = 2 * (dot[ver].x - (*it2).first);
                        pq.push(make_pair(-dis[(*it2).second][3], make_pair((*it2).second, 3)));
                    }
                }
                auto it3 = lower_bound(all(line[3][id[ver][3]][3]), make_pair(dot[ver].y + now, -1));
                if (it3 != line[3][id[ver][3]][3].end() && dis[(*it3).second][6] > (*it3).first - dot[ver].y) {
                    dis[(*it3).second][6] = (*it3).first - dot[ver].y;
                    pq.push(make_pair(-dis[(*it3).second][6], make_pair((*it3).second, 6)));
                }
            }
            else if (dir[ver] == 2) {
                auto it = lower_bound(all(line[0][id[ver][0]][1]), make_pair(dot[ver].x - (now + 1) / 2 + 1, -1));
                if (it != line[0][id[ver][0]][1].begin()) {
                    --it;
                    if (dis[(*it).second][1] > 2 * (dot[ver].x - (*it).first)) {
                        dis[(*it).second][1] = 2 * (dot[ver].x - (*it).first);
                        pq.push(make_pair(-dis[(*it).second][1], make_pair((*it).second, 1)));
                    }
                }
                auto it2 = lower_bound(all(line[1][id[ver][1]][3]), make_pair(dot[ver].x - (now + 1) / 2 + 1, -1));
                if (it2 != line[1][id[ver][1]][3].begin()) {
                    --it2;
                    if (dis[(*it2).second][3] > 2 * (dot[ver].x - (*it2).first)) {
                        dis[(*it2).second][3] = 2 * (dot[ver].x - (*it2).first);
                        pq.push(make_pair(-dis[(*it2).second][3], make_pair((*it2).second, 3)));
                    }
                }
                auto it3 = lower_bound(all(line[2][id[ver][2]][0]), make_pair(dot[ver].x - now + 1, -1));
                if (it3 != line[2][id[ver][2]][0].begin()) {
                    --it3;
                    if (dis[(*it3).second][5] > dot[ver].x - (*it3).first) {
                        dis[(*it3).second][5] = dot[ver].x - (*it3).first;
                        pq.push(make_pair(-dis[(*it3).second][5], make_pair((*it3).second, 5)));
                    }
                }
            }
            else {
                auto it = lower_bound(all(line[0][id[ver][0]][0]), make_pair(dot[ver].x - (now + 1) / 2 + 1, -1));
                if (it != line[0][id[ver][0]][0].begin()) {
                    --it;
                    if (dis[(*it).second][1] > 2 * (dot[ver].x - (*it).first)) {
                        dis[(*it).second][1] = 2 * (dot[ver].x - (*it).first);
                        pq.push(make_pair(-dis[(*it).second][1], make_pair((*it).second, 1)));
                    }
                }
                auto it2 = lower_bound(all(line[1][id[ver][1]][2]), make_pair(dot[ver].x + (now + 1) / 2, -1));
                if (it2 != line[1][id[ver][1]][2].end() && dis[(*it2).second][2] > 2 * ((*it2).first - dot[ver].x)) {
                    dis[(*it2).second][2] = 2 * ((*it).first - dot[ver].x);
                    pq.push(make_pair(-dis[(*it2).second][2], make_pair((*it2).second, 2)));
                }
                auto it3 = lower_bound(all(line[3][id[ver][3]][1]), make_pair(dot[ver].x - now + 1, -1));
                if (it3 != line[3][id[ver][3]][1].begin()) {
                    --it3;
                    if (dis[(*it3).second][7] > dot[ver].y - (*it3).first) {
                        dis[(*it3).second][7] = dot[ver].y - (*it3).first;
                        pq.push(make_pair(-dis[(*it3).second][7], make_pair((*it3).second, 7)));
                    }
                }
            }
        }
        int res = 1;
        for (int i = 2; i <= N; i++) {
            bool flag = false;
            for (int j = 0; j < 8; j++) flag |= dis[i][j] != inf;
            res += flag;
        }
        ans = max(ans, res);
        for (int i = 2; i <= N; i++) {
            int tmp = dot[i].y;
            dot[i].y = dot[i].x;
            dot[i].x = -tmp;
        }
        dir[1] = 0;
    }
    cout << ans << '\n';
}

Compilation message (stderr)

fever.cpp: In function 'int main()':
fever.cpp:24:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |     freopen("sample-05-in.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fever.cpp:25:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |     freopen("output.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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