Submission #595823

#	Time	Username	Problem	Language	Result	Execution time	Memory
595823		Cross_Ratio	IOI Fever (JOI21_fever)	C++14	25 / 100	5038 ms	29576 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];
vector<vector<int>> adj;
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(int 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]);
            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] = 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] = 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] = 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] = d;
                        PQ.push(P(dis[i][3-dir],4*i+3-dir));
                    }
                }
            }
        }
        for(i=0;i<N;i++) {
            if(i==id) continue;
            if(dir==0) {
                if(X[id]<X[i]&&Y[i]==Y[id]) {
                    int c = abs(X[i]-X[id])+abs(Y[i]-Y[id]);
                    int d, d2;
                    if(c%2==0) {
                        d = c/2;
                        d2 = c/2;
                    }
                    else {
                        d=(c-1)/2;
                        d2=(c+1)/2;
                    }
                    if(dis[i][(dir+2)%4]>d2&&dis[id][dir]<=d) {
                        dis[i][(dir+2)%4] = d2;
                        PQ.push(P(dis[i][(dir+2)%4],4*i+(dir+2)%4));
                    }
                }
            }
            if(dir==2) {
                if(X[id]>X[i]&&Y[i]==Y[id]) {
                    int c = abs(X[i]-X[id])+abs(Y[i]-Y[id]);
                    int d, d2;
                    if(c%2==0) {
                        d = c/2;
                        d2 = c/2;
                    }
                    else {
                        d=(c-1)/2;
                        d2=(c+1)/2;
                    }
                    if(dis[i][(dir+2)%4]>d2&&dis[id][dir]<=d) {
                        dis[i][(dir+2)%4] = d2;
                        PQ.push(P(dis[i][(dir+2)%4],4*i+(dir+2)%4));
                    }
                }
            }
            if(dir==1) {
                if(X[id]==X[i]&&Y[id]<Y[i]) {
                    int c = abs(X[i]-X[id])+abs(Y[i]-Y[id]);
                    int d, d2;
                    if(c%2==0) {
                        d = c/2;
                        d2 = c/2;
                    }
                    else {
                        d=(c-1)/2;
                        d2=(c+1)/2;
                    }
                    if(dis[i][(dir+2)%4]>d2&&dis[id][dir]<=d) {
                        dis[i][(dir+2)%4] = d2;
                        PQ.push(P(dis[i][(dir+2)%4],4*i+(dir+2)%4));
                    }
                }
            }
            if(dir==3) {
                if(X[id]==X[i]&&Y[id]>Y[i]) {
                    int c = abs(X[i]-X[id])+abs(Y[i]-Y[id]);
                    int d, d2;
                    if(c%2==0) {
                        d = c/2;
                        d2 = c/2;
                    }
                    else {
                        d=(c-1)/2;
                        d2=(c+1)/2;
                    }
                    if(dis[i][(dir+2)%4]>d2&&dis[id][dir]<=d) {
                        dis[i][(dir+2)%4] = d2;
                        PQ.push(P(dis[i][(dir+2)%4],4*i+(dir+2)%4));
                    }
                }
            }
        }
    }
    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;
}
map<int,vector<int>> M1, M2;
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];
    adj.resize(N);
    for(i=0;i<N;i++) M1[X[i]+Y[i]].push_back(i);
    for(i=0;i<N;i++) M2[X[i]-Y[i]].push_back(i);
    for(auto it = M1.begin();it!=M1.end();it++) {
        sort(it->second.begin(),it->second.end(),[&](int x, int y) {
             return X[x] < X[y];
             });
    }
    for(auto it = M2.begin();it!=M2.end();it++) {
        sort(it->second.begin(),it->second.end(),[&](int x, int y) {
             return X[x] < X[y];
             });
    }
    int ma = 0;
    for(i=0;i<4;i++) ma = max(ma, simulate(i, N));
    cout <<ma;
}

Compilation message (stderr)

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

• 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