This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define int int64_t
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
const int MAXN = 100'009;
const int INF = 1e18;
int n;
pii tab[MAXN];
int dis[MAXN];
int dir[MAXN];
pii sdis[8][MAXN];
unordered_map<int, int> remap[4];
set<pii> S[8][MAXN];
int D(int x, int y) {
return max(abs(tab[x].st-tab[y].st), abs(tab[x].nd-tab[y].nd));
}
int id(int x, int i) {
if(i%4==0) {
return remap[i%4][tab[x].nd];
}
if(i%4==1) {
return remap[i%4][tab[x].st-tab[x].nd];
}
if(i%4==2) {
return remap[i%4][tab[x].st];
}
if(i%4==3) {
return remap[i%4][tab[x].st+tab[x].nd];
}
}
int f(int x, int i) {
int ret = 0;
if(i/2==0||i/2==2) {
ret = tab[x].st;
} else {
ret = tab[x].nd;
}
if(i>=4) ret*=-1;
return ret;
}
int opp(int x, int i) {
if(x==i) {
return (x+4)%8;
}
if((x+1)%8==i) {
return (x+6)%8;
}
return (x+2)%8;
}
priority_queue<pii, vector<pii>, greater<pii>> Q;
void push(int x) {
for(int i=0;i<8;i++) {
int num = id(x, i);
auto it = S[i][num].upper_bound({f(x, i), INF});
if(it!=S[i][num].end()) {
int nxt = (*it).nd;
int X = 2-i%2;
int ndis = sdis[i][x].st+D(x, nxt)/X;
if(ndis<sdis[i][nxt].st) {
sdis[i][nxt] = {ndis, sdis[i][x].nd};
}
if(ndis<dis[nxt]) {
dis[nxt] = ndis;
dir[nxt] = opp(sdis[i][x].nd, i);
Q.push({dis[nxt], nxt});
}
}
}
}
int dijkstra(int I) {
int ret = 0;
fill(dis, dis+n, INF);
fill(dir, dir+n, INF);
for(int i=0;i<8;i++) {
fill(sdis[i], sdis[i]+n, make_pair(INF, -1));
}
dis[0] = 0;
dir[0] = I;
Q.push({0, 0});
while(sz(Q)) {
auto [x_dis, x] = Q.top();
Q.pop();
if(x_dis!=dis[x]) continue;
ret++;
for(int i=0;i<8;i++) {
S[i][id(x, i)].erase(make_pair(f(x, i), x));
}
push(x);
int tmp = (dir[x]-1);
if(tmp<0) tmp += 8;
vector<int> v = {tmp, dir[x], (dir[x]+1)%8};
for(int i:v) {
int X = 2-i%2;
auto it = S[i][id(x, i)].lower_bound(make_pair(f(x, i)+dis[x]*X, -1));
if(it!=S[i][id(x, i)].end()) {
int y = (*it).nd;
int ndis = D(x, y)/X;
if(ndis<sdis[i][y].st) {
sdis[i][y] = {ndis, dir[x]};
}
if(ndis<dis[y]) {
dis[y] = ndis;
dir[y] = opp(dir[x], i);
Q.push({dis[y], y});
}
}
}
}
return ret;
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
vector<int> vals[4];
for(int i=0;i<n;i++) {
cin >> tab[i].st >> tab[i].nd;
tab[i].st*=2, tab[i].nd*=2;
swap(tab[i].st, tab[i].nd);
vals[0].pb(tab[i].nd), vals[2].pb(tab[i].st);
vals[1].pb(tab[i].st-tab[i].nd), vals[3].pb(tab[i].st+tab[i].nd);
}
for(int i=0;i<4;i++) {
sort(all(vals[i]));
vals[i].erase(unique(all(vals[i])), vals[i].end());
for(int j=0;j<sz(vals[i]);j++) {
remap[i][vals[i][j]] = j;
}
}
int ans = 0;
for(int I=0;I<2;I+=2) {
for(int i=0;i<n;i++) {
for(int j=0;j<8;j++) {
S[j][i].clear();
}
}
for(int i=0;i<n;i++) {
for(int j=0;j<8;j++) {
S[j][id(i, j)].insert(make_pair(f(i, j), i));
}
}
ans = max(ans, dijkstra(I));
}
cout << ans << "\n";
}
Compilation message (stderr)
fever.cpp: In function 'int64_t id(int64_t, int64_t)':
fever.cpp:41:1: warning: control reaches end of non-void function [-Wreturn-type]
41 | }
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |