Submission #1176628

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176628		trashaccount	IOI Fever (JOI21_fever)	C++20	25 / 100	5095 ms	47380 KiB

fever

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pii pair <int, int>
#define fi first
#define se second
#define mp make_pair
#define isz(a) (int)(a).size()

const int NM = 1e5, dx[] = {1, -1, 0, 0}, dy[] = {0, 0, -1, 1}, inf = 1e18;
const int f[] = {2, 3, 0, 1}, g[] = {3, 2, 1, 0};

int N, X[NM+5], Y[NM+5];
priority_queue <pii, vector <pii>, greater <pii> > pq;
map <int, vector <pii> > arr_X, arr_Y, arr_diff, arr_sum;
map <int, vector <pii> >::iterator it;
pii d[NM+5];

int dijkstra(int k){
    for (int i = 0; i < N; i++) d[i].fi = +inf, d[i].se = -1;
    d[0].fi = 0, d[0].se = k;

    while (!pq.empty()) pq.pop();
    pq.push(mp(0, 0));
    
    while (!pq.empty()){
        int u = pq.top().se;
        if (d[u].fi != pq.top().fi){
            pq.pop();
            continue;
        }
        pq.pop();
        int t = X[u]-Y[u], sz = isz(arr_diff[t]);
        if (d[u].se == 0 || d[u].se == 3){
            for (int i = sz-1; i >= 0; i--){
                int c = arr_diff[t][i].fi-X[u];
                if (c < d[u].fi) break;
                int v = arr_diff[t][i].se;
                if (c < d[v].fi){
                    d[v].fi = c;
                    d[v].se = f[d[u].se];
                    pq.push(mp(d[v].fi, v));
                }
            }
        }
        else{
            for (int i = 0; i < sz; i++){
                int c = X[u]-arr_diff[t][i].fi;
                if (c < d[u].fi) break;
                int v = arr_diff[t][i].se;
                if (c < d[v].fi){
                    d[v].fi = c;
                    d[v].se = f[d[u].se];
                    pq.push(mp(d[v].fi, v));
                }
            }
        }

        t = X[u]+Y[u], sz = isz(arr_sum[t]);
        if (d[u].se == 0 || d[u].se == 2){
            for (int i = sz-1; i >= 0; i--){
                int c = arr_sum[t][i].fi-X[u];
                if (c < d[u].fi) break;
                int v = arr_sum[t][i].se;
                if (c < d[v].fi){
                    d[v].fi = c;
                    d[v].se = g[d[u].se];
                    pq.push(mp(d[v].fi, v));
                }
            }
        }
        else{
            for (int i = 0; i < sz; i++){
                int c = X[u]-arr_sum[t][i].fi;
                if (c < d[u].fi) break;
                int v = arr_sum[t][i].se;
                if (c < d[v].fi){
                    d[v].fi = c;
                    d[v].se = g[d[u].se];
                    pq.push(mp(d[v].fi, v));
                }
            }
        }

        // t = X[u], sz = isz(arr_X[t]);
        // if (d[u].se == 3){
        //     for (int i = sz-1; i >= 0; i--){
        //         int c = (arr_X[t][i].fi-Y[u])/2;
        //         if (c < d[u].fi) break;
        //         int v = arr_X[t][i].se;
        //         if (c < d[v].fi){
        //             d[v].fi = c;
        //             d[v].se = d[u].se^1;
        //             pq.push(mp(d[v].fi, v));
        //         }
        //     }
        // }
        // else if (d[u].se == 2){
        //     for (int i = 0; i < sz; i++){
        //         int c = (Y[u]-arr_X[t][i].fi)/2;
        //         if (c < d[u].fi) break;
        //         int v = arr_X[t][i].se;
        //         if (c < d[v].fi){
        //             d[v].fi = c;
        //             d[v].se = d[u].se^1;
        //             pq.push(mp(d[v].fi, v));
        //         }
        //     }
        // }

        // t = Y[u], sz = isz(arr_Y[t]);
        // if (d[u].se == 0){
        //     for (int i = sz-1; i >= 0; i--){
        //         int c = (arr_Y[t][i].fi-X[u])/2;
        //         if (c < d[u].fi) break;
        //         int v = arr_Y[t][i].se;
        //         if (c < d[v].fi){
        //             d[v].fi = c;
        //             d[v].se = d[u].se^1;
        //             pq.push(mp(d[v].fi, v));
        //         }
        //     }
        // }
        // else if (d[u].se == 1){
        //     for (int i = 0; i < sz; i++){
        //         int c = (X[u]-arr_Y[t][i].fi)/2;
        //         if (c < d[u].fi) break;
        //         int v = arr_Y[t][i].se;
        //         if (c < d[v].fi){
        //             d[v].fi = c;
        //             d[v].se = d[u].se^1;
        //             pq.push(mp(d[v].fi, v));
        //         }
        //     }
        // }
    }
    int res = 0;
    for (int i = 0; i < N; i++) res += (d[i].se != -1);
    return res;
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N;
    for (int i = 0; i < N; i++){
        cin >> X[i] >> Y[i];
        X[i] *= 2;
        Y[i] *= 2;
        arr_X[X[i]].push_back(mp(Y[i], i));
        arr_Y[Y[i]].push_back(mp(X[i], i));
        arr_sum[X[i]+Y[i]].push_back(mp(X[i], i));
        arr_diff[X[i]-Y[i]].push_back(mp(X[i], i));
    }
    for (it = arr_X.begin(); it != arr_X.end(); it++) sort(it->se.begin(), it->se.end());
    for (it = arr_Y.begin(); it != arr_Y.end(); it++) sort(it->se.begin(), it->se.end());
    for (it = arr_sum.begin(); it != arr_sum.end(); it++) sort(it->se.begin(), it->se.end());
    for (it = arr_diff.begin(); it != arr_diff.end(); it++) sort(it->se.begin(), it->se.end());

    int ans = 0;
    for (int k = 0; k < 4; k++) ans = max(ans, dijkstra(k));
    ans = max(ans, dijkstra(0));
    cout << ans;
    return 0;
}

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