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()
ostream& operator<<(ostream &os, pair<auto, auto> x) {
os << "{" << x.nd/2 << ", " << x.st/2 << "}";
return os;
}
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 abs(tab[x].st-tab[y].st)+abs(tab[x].nd-tab[y].nd);
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});
cerr << "PUSH!!!\n";
}
}
}
}
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));
// sdis[i][0] = 0;
}
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;
cerr << "D: " << tab[x] << " " << dis[x] << "\n";
cerr << "Direction: " << dir[x] << "\n";
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) {
cerr << "dir: " << i << "\n";
int X = 2-i%2;
auto it = S[i][id(x, i)].lower_bound(make_pair(f(x, i)+dis[x]*X, -1));
cerr << "init: " << f(x, i) << "\n";
cerr << "lim: " << f(x, i)+dis[x]/X << "\n";
if(it!=S[i][id(x, i)].end()) {
cerr << "full find: " << (*it).st << " " << (*it).nd << "\n";
int y = (*it).nd;
// cerr << "cand: "<< tab[y] << "\n";
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;
}
}
// for(int i=0;i<n;i++) {
// // cerr << "NOW: " << i << "\n";
// for(int j=0;j<8;j++) {
// S[j][id(i, j)].insert(make_pair(f(i, j), i));
// // cerr << "id: " << id(i, j) << " : f: "<< f(i, j) << "\n";
// }
// }
int ans = 0;
// ans = dijkstra(2);
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++) {
cerr << "NOW: " << i << "\n";
for(int j=0;j<8;j++) {
S[j][id(i, j)].insert(make_pair(f(i, j), i));
cerr << "id: " << id(i, j) << " : f: "<< f(i, j) << "\n";
}
}
ans = max(ans, dijkstra(I));
}
cout << ans << "\n";
}
Compilation message (stderr)
fever.cpp:12:39: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
12 | ostream& operator<<(ostream &os, pair<auto, auto> x) {
| ^~~~
fever.cpp:12:45: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
12 | ostream& operator<<(ostream &os, pair<auto, auto> x) {
| ^~~~
fever.cpp: In function 'int64_t id(int64_t, int64_t)':
fever.cpp:47:1: warning: control reaches end of non-void function [-Wreturn-type]
47 | }
| ^
# | 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... |