제출 #595944

#제출 시각아이디문제언어결과실행 시간메모리
595944Cross_RatioIOI 바이러스 (JOI21_fever)C++14
0 / 100
1 ms340 KiB
#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[100005]; map<int,set<P>> M1, M2; int simulate(int dir2, int N) { //cout << "Direction : "<< dir2 << '\n'; int i, j; for(i=0;i<N;i++) { for(j=0;j<4;j++) dis[i][j] = INF; } for(i=0;i<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/4]) continue; vis[k.second/4] = true; int id = k.second / 4; int dir = k.second % 4; M1[X[id]+Y[id]].erase(P(X[id],id)); M2[X[id]-Y[id]].erase(P(X[id],id)); //cout << id << ' ' << dir << '\n'; for(auto it = M1[X[id]+Y[id]].begin();it!=M1[X[id]+Y[id]].end();it++) { if(X[id]- (*it).first<dis[id][dir]) break; i = (*it).second; if(i==id) continue; if(vis[i]) 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==2) { 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==1) { 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)); } } } } for(auto it = M1[X[id]+Y[id]].rbegin();it!=M1[X[id]+Y[id]].rend();it++) { if((*it).first-X[id]<dis[id][dir]) break; i = (*it).second; if(i==id) continue; if(vis[i]) 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==2) { 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==1) { 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)); } } } } for(auto it = M2[X[id]-Y[id]].begin();it!=M2[X[id]-Y[id]].end();it++) { if(X[id]-(*it).first<dis[id][dir]) break; i = (*it).second; if(i==id) continue; if(vis[i]) 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>=2) { 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==0) { 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)); } } } } for(auto it = M2[X[id]-Y[id]].rbegin();it!=M2[X[id]-Y[id]].rend();it++) { if((*it).first-X[id]<dis[id][dir]) break; i = (*it).second; if(i==id) continue; if(vis[i]) 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>=2) { 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==0) { 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)); } } } } for(i=0;i<N;i++) { if(i==id) continue; if(vis[i]) continue; if(dir==0) { if(X[id]<X[i]&&Y[i]==Y[id]) { int d = (abs(X[i]-X[id])+abs(Y[i]-Y[id]))/2; if(dis[i][(dir+2)%4]>d&&dis[id][dir]<=d) { dis[i][(dir+2)%4] = d; 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 d = (abs(X[i]-X[id])+abs(Y[i]-Y[id]))/2; if(dis[i][(dir+2)%4]>d&&dis[id][dir]<=d) { dis[i][(dir+2)%4] = d; 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 d = (abs(X[i]-X[id])+abs(Y[i]-Y[id]))/2; if(dis[i][(dir+2)%4]>d&&dis[id][dir]<=d) { dis[i][(dir+2)%4] = d; 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 d = (abs(X[i]-X[id])+abs(Y[i]-Y[id]))/2; if(dis[i][(dir+2)%4]>d&&dis[id][dir]<=d) { dis[i][(dir+2)%4] = d; 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; } signed main() { cin.sync_with_stdio(false); cin.tie(0); cout.tie(0); int N; cin >> N; int i, j; clock_t st = clock(); //for(i=0;i<N;i++) cin >> X[i] >> Y[i]; for(i=0;i<N;i++) X[i] = Y[i] = i; for(i=0;i<N;i++) { X[i] *= 2; Y[i] *= 2; } int ma = 0; for(i=0;i<4;i++) { M1.clear(); M2.clear(); for(j=0;j<N;j++) M1[X[j]+Y[j]].insert(P(X[j],j)); for(j=0;j<N;j++) M2[X[j]-Y[j]].insert(P(X[j],j)); ma = max(ma, simulate(i, N)); } cout <<ma; cout << '\n' << clock() - st << "ms"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...