제출 #595789

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
595789		Cross_Ratio	IOI Fever (JOI21_fever)	C++14	6 / 100	1 ms	340 KiB

fever

#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> P;
const int INF = 1e18;
int X[100005];
int Y[100005];
int dis[100005][4];
bool vis[400005];
int simulate(int dir2, int N) {
    int i, j;
    for(i=0;i<N;i++) {
        for(j=0;j<4;j++) dis[i][j] = INF;
    }
    for(i=0;i<4*N;i++) vis[i] = false;
    dis[0][dir2] = 0;
    priority_queue<P,vector<P>,greater<P>> PQ;
    PQ.push(P(0,dir2));
    while(!PQ.empty()) {
        P k = PQ.top();
        PQ.pop();
        if(vis[k.second]) continue;
        int id = k.second / 4;
        int dir = k.second % 4;
        for(i=0;i<N;i++) {
            if(i==id) continue;
            if(abs(X[i]-X[id])!=abs(Y[i]-Y[id])) continue;
            int d = abs(X[i] - X[id]);
            for(j=0;j<4;j++) {
                int val = 2* (X[i] < X[id]) + (Y[i] < Y[id]);
                if(val==3) {
                    if(dir<=1) {
                        if(dis[i][3-dir]>d && dis[id][dir]<=d) {
                            dis[i][3-dir] = dis[id][dir] + d;
                            PQ.push(P(dis[i][3-dir],4*i+3-dir));
                        }
                    }
                }
                if(val==2) {
                    if(dir==0||dir==3) {
                        if(dis[i][(5-dir)%4]>d&&dis[id][dir]<=d) {
                            dis[i][(5-dir)%4] = dis[id][dir] + d;
                            PQ.push(P(dis[i][(5-dir)%4],4*i+(5-dir)%4));
                        }
                    }
                }
                if(val==1) {
                    if(dir==1||dir==2) {
                        if(dis[i][(5-dir)%4]>d&&dis[id][dir]<=d) {
                            dis[i][(5-dir)%4] = dis[id][dir] + d;
                            PQ.push(P(dis[i][(5-dir)%4],4*i+(5-dir)%4));
                        }
                    }
                }
                if(val==0) {
                    if(dir==2||dir==3) {
                        if(dis[i][3-dir]>d&&dis[id][dir]<=d) {
                            dis[i][3-dir] = dis[id][dir] + d;
                            PQ.push(P(dis[i][3-dir],4*i+3-dir));
                        }
                    }
                }
            }
        }
    }
    int ans = 0;
    for(i=0;i<N;i++) {
        int mi = INF;
        for(j=0;j<4;j++) mi = min(mi, dis[i][j]);
        if(mi != INF) ans++;
    }
    return ans;
}
signed main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int N;
    cin >> N;
    int i, j;
    for(i=0;i<N;i++) cin >> X[i] >> Y[i];
    int ma = 0;
    for(i=0;i<4;i++) ma = max(ma, simulate(i, N));
    cout <<ma;
}

컴파일 시 표준 에러 (stderr) 메시지

fever.cpp: In function 'int main()':
fever.cpp:80:12: warning: unused variable 'j' [-Wunused-variable]
   80 |     int i, j;
      |            ^

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