Submission #1176760

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176760		daoquanglinh2007	IOI Fever (JOI21_fever)	C++20	69 / 100	2281 ms	63064 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, LIM = 1024;
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 <pii, int> cnt_X, cnt_Y, cnt_diff, cnt_sum;
map <int, vector <pii> >::iterator it;
pii d[NM+5];

int dijkstra(int k){
    cnt_X.clear(), cnt_Y.clear(), cnt_diff.clear(), cnt_sum.clear();

    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];
        if (cnt_diff[mp(t, d[u].se)] < LIM){
            for (pii p : arr_diff[t]){
                if (p.fi == X[u]) continue;
                if ((d[u].se == 0 || d[u].se == 3) && p.fi < X[u]) continue;
                if ((d[u].se == 1 || d[u].se == 2) && p.fi > X[u]) continue;
                int c = abs(p.fi-X[u]);
                if (c < d[u].fi) continue;
                int v = p.se;
                if (c < d[v].fi){
                    d[v].fi = c;
                    d[v].se = f[d[u].se];
                    pq.push(mp(d[v].fi, v));
                }
            }
            cnt_diff[mp(t, d[u].se)]++;
        }

        t = X[u]+Y[u];
        if (cnt_sum[mp(t, d[u].se)] < LIM){
            for (pii p : arr_sum[t]){
                if (p.fi == X[u]) continue;
                if ((d[u].se == 0 || d[u].se == 2) && p.fi < X[u]) continue;
                if ((d[u].se == 1 || d[u].se == 3) && p.fi > X[u]) continue;
                int c = abs(p.fi-X[u]);
                if (c < d[u].fi) continue;
                int v = p.se;
                if (c < d[v].fi){
                    d[v].fi = c;
                    d[v].se = g[d[u].se];
                    pq.push(mp(d[v].fi, v));
                }
            }
            cnt_sum[mp(t, d[u].se)]++;
        }

        t = X[u];
        if (cnt_X[mp(t, d[u].se)] < LIM && (d[u].se == 2 || d[u].se == 3)){
            for (pii p : arr_X[t]){
                if (p.fi == Y[u]) continue;
                if (d[u].se == 3 && p.fi < Y[u]) continue;
                if (d[u].se == 2 && p.fi > Y[u]) continue;
                int c = abs(p.fi-Y[u])/2;
                if (c < d[u].fi) continue;
                int v = p.se;
                if (c < d[v].fi){
                    d[v].fi = c;
                    d[v].se = d[u].se^1;
                    pq.push(mp(d[v].fi, v));
                }
            }
            cnt_X[mp(t, d[u].se)]++;
        }

        t = Y[u];
        if (cnt_Y[mp(t, d[u].se)] < LIM && (d[u].se == 0 || d[u].se == 1)){
            for (pii p : arr_Y[t]){
                if (p.fi == X[u]) continue;
                if (d[u].se == 0 && p.fi < X[u]) continue;
                if (d[u].se == 1 && p.fi > X[u]) continue;
                int c = abs(p.fi-X[u])/2;
                if (c < d[u].fi) continue;
                int v = p.se;
                if (c < d[v].fi){
                    d[v].fi = c;
                    d[v].se = d[u].se^1;
                    pq.push(mp(d[v].fi, v));
                }
            }
            cnt_Y[mp(t, d[u].se)]++;
        }
    }
    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_diff[X[i]-Y[i]].push_back(mp(X[i], i));
        arr_sum[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_diff.begin(); it != arr_diff.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());

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

• 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: 0 / 31