Submission #1176579

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176579		trashaccount	IOI Fever (JOI21_fever)	C++20	37 / 100	5093 ms	5088 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

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;
vector <pii> arr;
pii d[NM+5];
stack <pii> pq;

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();
        for (int v = 0; v < N; v++){
            if (v == u) continue;
            if (arr[u].fi-arr[v].fi == arr[u].se-arr[v].se){
                if (arr[u].fi < arr[v].fi && (d[u].se == 1 || d[u].se == 2)) continue;
                if (arr[u].fi > arr[v].fi && (d[u].se == 0 || d[u].se == 3)) continue;
                int tmp = abs(arr[u].fi-arr[v].fi);
                if (tmp < d[u].fi) continue;
                if (tmp < d[v].fi){
                    d[v].fi = tmp;
                    d[v].se = f[d[u].se];
                    pq.push(mp(d[v].fi, v));
                }
                continue;
            }
            if (arr[u].fi+arr[u].se == arr[v].fi+arr[v].se){
                if (arr[u].fi < arr[v].fi && (d[u].se == 1 || d[u].se == 3)) continue;
                if (arr[u].fi > arr[v].fi && (d[u].se == 0 || d[u].se == 2)) continue;
                int tmp = abs(arr[u].fi-arr[v].fi);
                if (tmp < d[u].fi) continue;
                if (tmp < d[v].fi){
                    d[v].fi = tmp;
                    d[v].se = g[d[u].se];
                    pq.push(mp(d[v].fi, v));
                }
                continue;
            }
            if (arr[u].se == arr[v].se){
                if (arr[u].fi < arr[v].fi && d[u].se != 0) continue;
                if (arr[u].fi > arr[v].fi && d[u].se != 1) continue;
                int tmp = abs(arr[u].fi-arr[v].fi)/2;
                if (tmp < d[u].fi) continue;
                if (tmp < d[v].fi){
                    d[v].fi = tmp;
                    d[v].se = d[u].se^1;
                    pq.push(mp(d[v].fi, v));
                }
                continue;
            }
            if (arr[u].fi == arr[v].fi){
                if (arr[u].se < arr[v].se && d[u].se != 3) continue;
                if (arr[u].se > arr[v].se && d[u].se != 2) continue;
                int tmp = abs(arr[u].se-arr[v].se)/2;
                if (tmp < d[u].fi) continue;
                if (tmp < d[v].fi){
                    d[v].fi = tmp;
                    d[v].se = d[u].se^1;
                    pq.push(mp(d[v].fi, v));
                }
                continue;
            }
        }
    }
    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;
    arr.resize(N);
    for (int i = 0; i < N; i++){
        cin >> arr[i].fi >> arr[i].se;
        arr[i].fi *= 2;
        arr[i].se *= 2;
    }
    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: 0 / 32
• Subtask 7: 0 / 31