제출 #397557

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
397557		phathnv	IOI Fever (JOI21_fever)	C++11	37 / 100	5056 ms	202180 KiB

fever

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

typedef long long ll;

const int N = 1e5 + 7;
const int INF = 1e9 + 7;

int n, x[N], y[N], curInd, ind[N][4], dist[N * 4];
vector<pair<int, int>> adj[N * 4];

int Calc(int s){
    for(int i = 1; i <= 4 * n; i++)
        dist[i] = INF;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    dist[s] = 0;
    pq.push({0, s});
    while (!pq.empty()){
        int u = pq.top().second;
        int d = pq.top().first;
        pq.pop();
        if (dist[u] != d)
            continue;
        for(auto e : adj[u]){
            int v = e.first;
            int w = e.second;
            if (dist[u] <= w && dist[v] > w){
                dist[v] = w;
                pq.push({dist[v], v});
            }
        }
    }
    int res = 0;
    for(int i = 1; i <= n * 4; i++)
        res += (dist[i] != INF);
    return res;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> x[i] >> y[i];
        x[i] *= 2;
        y[i] *= 2;
        for(int dir = 0; dir < 4; dir++)
            ind[i][dir] = ++curInd;
    }
    for(int a = 1; a <= n; a++)
        for(int b = a + 1; b <= n; b++){
            int dx = abs(x[a] - x[b]);
            int dy = abs(y[a] - y[b]);
            int dist = (dx + dy) / 2;
            if (!dx){
                if (y[a] < y[b]){
                    adj[ind[a][0]].push_back({ind[b][2], dist});
                    adj[ind[b][2]].push_back({ind[a][0], dist});
                } else {
                    adj[ind[a][2]].push_back({ind[b][0], dist});
                    adj[ind[b][0]].push_back({ind[a][2], dist});
                }
            } else if (!dy){
                if (x[a] < x[b]){
                    adj[ind[a][1]].push_back({ind[b][3], dist});
                    adj[ind[b][3]].push_back({ind[a][1], dist});
                } else {
                    adj[ind[a][3]].push_back({ind[b][1], dist});
                    adj[ind[b][1]].push_back({ind[a][3], dist});
                }
            } else if (dx == dy){
                int dirA, dirB;
                dirA = (y[a] < y[b]? 0 : 2);
                dirB = (x[b] < x[a]? 1 : 3);
                adj[ind[a][dirA]].push_back({ind[b][dirB], dist});
                adj[ind[b][dirB]].push_back({ind[a][dirA], dist});
                swap(dirA, dirB);
                dirA = (dirA + 2) % 4;
                dirB = (dirB + 2) % 4;
                adj[ind[a][dirA]].push_back({ind[b][dirB], dist});
                adj[ind[b][dirB]].push_back({ind[a][dirA], dist});
            }
        }
    int res = 0;
    for(int dir = 0; dir < 4; dir++)
        res = max(res, Calc(ind[1][dir]));
    cout << res;
    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