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>
#define fi first
#define se second
#define all(x) x.begin(), x.end()
using namespace std;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
const int INF = 1 << 30;
const int N = 1e5 + 11;
const int B = 5;
struct point{
int x, y, d, id;
};
vector<point> P;
vector<pair<int, int>> G[N * B];
int collide(int a, int b){
if(P[a].d == P[b].d) return INF;
if((P[a].d ^ P[b].d) == 1){
switch(P[a].d){
case 0: return P[a].y == P[b].y && P[a].x < P[b].x ? (P[b].x - P[a].x) / 2 : INF;
case 1: return P[a].y == P[b].y && P[b].x < P[a].x ? (P[a].x - P[b].x) / 2 : INF;
case 2: return P[a].x == P[b].x && P[a].y < P[b].y ? (P[b].y - P[a].y) / 2 : INF;
case 3: return P[a].x == P[b].x && P[b].y < P[a].y ? (P[a].y - P[b].y) / 2 : INF;
}
return INF;
}
if(abs(P[a].x - P[b].x) != abs(P[a].y - P[b].y)) return INF;
int D = abs(P[a].x - P[b].x);
if(P[a].x + P[a].y == P[b].x + P[b].y){
if(P[a].x > P[b].x) swap(a, b);
if((P[a].d == 0 && P[b].d == 2) || (P[a].d == 3 && P[b].d == 1)) return D;
return INF;
}else{
if(P[a].x > P[b].x) swap(a, b);
if((P[a].d == 0 && P[b].d == 3) || (P[a].d == 2 && P[b].d == 1)) return D;
return INF;
}
}
int ID(int x, int y = 0){
return x * B + y;
}
int calc(){
int n = P.size();
vector<int> T(n * B, INF);
for(int i = 0; i < n * B; i++) G[i].clear();
for(int i = 0; i < n; i++){
for(int j = 1; j < B; j++){
G[i * B + j].push_back({i * B, 0});
}
}
map<int, vector<pair<int, int>>> X, Y, A[4], M[4];
for(auto p : P){
X[p.x].push_back({p.y, p.id});
Y[p.y].push_back({p.x, p.id});
A[p.d][p.x + p.y].push_back({p.x, p.id});
M[p.d][p.x - p.y].push_back({p.x, p.id});
}
for(int i = 0; i < 4; i++){
for(auto& a : A[i]){
vector<pair<int, int>>& r = a.second;
sort(r.begin(), r.end());
if(i == 0 || i == 3){
for(int k = 0; k < (int) r.size() - 1; k++){
G[ID(r[k + 1].second, 1)].push_back({ID(r[k].second, 1), abs(r[k].first - r[k + 1].first)});
}
}else{
for(int k = 0; k < (int) r.size() - 1; k++){
G[ID(r[k].second, 1)].push_back({ID(r[k + 1].second, 1), abs(r[k].first - r[k + 1].first)});
}
}
}
for(auto& m : M[i]){
vector<pair<int, int>>& r = m.second;
sort(r.begin(), r.end());
if(i == 0 || i == 2){
for(int k = 0; k < (int) r.size() - 1; k++){
G[ID(r[k + 1].second, 2)].push_back({ID(r[k].second, 2), abs(r[k].first - r[k + 1].first)});
}
}else{
for(int k = 0; k < (int) r.size() - 1; k++){
G[ID(r[k].second, 2)].push_back({ID(r[k + 1].second, 2), abs(r[k].first - r[k + 1].first)});
}
}
}
}
// Part A
for(auto& a : A[0]){
vector<pair<int, int>>& r = a.second;
auto& r2 = A[2][a.first];
if(r2.empty()) continue;
for(auto [x, id] : r){
auto ptr = lower_bound(all(r2), pair<int, int>{x, -1}); if(ptr == r2.end()) continue;
G[ID(id)].push_back({ID(ptr->se, 1), abs(x - ptr->fi)});
}
}
for(auto& a : A[2]){
vector<pair<int, int>>& r = a.second;
auto& r2 = A[0][a.first];
if(r2.empty()) continue;
for(auto [x, id] : r){
auto ptr = lower_bound(all(r2), pair<int, int>{x, -1}); if(ptr == r2.begin()) continue;
G[ID(id)].push_back({ID(prev(ptr)->se, 1), abs(x - prev(ptr)->fi)});
}
}
for(auto& a : A[1]){
vector<pair<int, int>>& r = a.second;
auto& r2 = A[3][a.first];
if(r2.empty()) continue;
for(auto [x, id] : r){
auto ptr = lower_bound(all(r2), pair<int, int>{x, -1}); if(ptr == r2.begin()) continue;
G[ID(id)].push_back({ID(prev(ptr)->se, 1), abs(x - prev(ptr)->fi)});
}
}
for(auto& a : A[3]){
vector<pair<int, int>>& r = a.second;
auto& r2 = A[1][a.first];
if(r2.empty()) continue;
for(auto [x, id] : r){
auto ptr = lower_bound(all(r2), pair<int, int>{x, -1}); if(ptr == r2.end()) continue;
G[ID(id)].push_back({ID(ptr->se, 1), abs(x - ptr->fi)});
}
}
// Part M
for(auto& a : M[0]){
vector<pair<int, int>>& r = a.second;
auto& r2 = M[3][a.first];
if(r2.empty()) continue;
for(auto [x, id] : r){
auto ptr = lower_bound(all(r2), pair<int, int>{x, -1}); if(ptr == r2.end()) continue;
G[ID(id)].push_back({ID(ptr->se, 2), abs(x - ptr->fi)});
}
}
for(auto& a : M[3]){
vector<pair<int, int>>& r = a.second;
auto& r2 = M[0][a.first];
if(r2.empty()) continue;
for(auto [x, id] : r){
auto ptr = lower_bound(all(r2), pair<int, int>{x, -1}); if(ptr == r2.begin()) continue;
G[ID(id)].push_back({ID(prev(ptr)->se, 2), abs(x - prev(ptr)->fi)});
}
}
for(auto& a : M[1]){
vector<pair<int, int>>& r = a.second;
auto& r2 = M[2][a.first];
if(r2.empty()) continue;
for(auto [x, id] : r){
auto ptr = lower_bound(all(r2), pair<int, int>{x, -1}); if(ptr == r2.begin()) continue;
G[ID(id)].push_back({ID(prev(ptr)->se, 2), abs(x - prev(ptr)->fi)});
}
}
for(auto& a : M[2]){
vector<pair<int, int>>& r = a.second;
auto& r2 = M[1][a.first];
if(r2.empty()) continue;
for(auto [x, id] : r){
auto ptr = lower_bound(all(r2), pair<int, int>{x, -1}); if(ptr == r2.end()) continue;
G[ID(id)].push_back({ID(ptr->se, 2), abs(x - ptr->fi)});
}
}
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; pq.push({0, 0}); T[0] = 0;
while(!pq.empty()){
auto [t, u] = pq.top(); pq.pop();
if(T[u] != t) continue;
for(auto [v, w] : G[u]) {
if(v % B != 0 && u % B == 0){
if(T[u] <= w && w < T[v]){
T[v] = w;
pq.push({T[v], v});
}
}else{
if(T[u] + w < T[v]){
T[v] = T[u] + w;
pq.push({T[v], v});
}
}
}
}
set<int> S;
for(int i = 0; i < n * B; i++){
if(T[i] != INF) S.insert(i / B);
}
int ans = S.size();
return ans;
}
int32_t main(){
int n; cin >> n;
for(int i = 0; i < n; i++){
int x, y; cin >> x >> y; x *= 2, y *= 2;
P.push_back({x, y, 0, i});
}
int ans = 0;
for(int d0 = 0; d0 < 4; d0++){
P[0].d = d0;
for(int i = 1; i < n; i++){
P[i].d = -1;
int dx = P[i].x - P[0].x;
int dy = P[i].y - P[0].y;
if(dx == 0){
P[i].d = 2 ^ (dy > 0);
}else if(dy == 0){
P[i].d = 0 ^ (dx > 0);
}else{
if(abs(dx) < abs(dy)){
P[i].d = 2 ^ (dy > 0);
}else if(abs(dy) < abs(dx)){
P[i].d = 0 ^ (dx > 0);
}else{
if(P[0].d == 0 || P[0].d == 1) {
if((P[0].d == 0) == (dx > 0)) P[i].d = 2 ^ (dy > 0);
else P[i].d = P[0].d;
}
if(P[0].d == 2 || P[0].d == 3) {
if((P[0].d == 2) == (dy > 0)) P[i].d = 0 ^ (dx > 0);
else P[i].d = P[0].d;
}
}
}
assert(P[i].d != -1);
}
ans = max(ans, calc());
}
cout << ans << endl;
}
Compilation message (stderr)
fever.cpp: In function 'int calc()':
fever.cpp:100:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
100 | for(auto [x, id] : r){
| ^
fever.cpp:110:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
110 | for(auto [x, id] : r){
| ^
fever.cpp:120:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
120 | for(auto [x, id] : r){
| ^
fever.cpp:130:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
130 | for(auto [x, id] : r){
| ^
fever.cpp:141:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
141 | for(auto [x, id] : r){
| ^
fever.cpp:151:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
151 | for(auto [x, id] : r){
| ^
fever.cpp:161:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
161 | for(auto [x, id] : r){
| ^
fever.cpp:171:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
171 | for(auto [x, id] : r){
| ^
fever.cpp:179:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
179 | auto [t, u] = pq.top(); pq.pop();
| ^
fever.cpp:181:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
181 | for(auto [v, w] : G[u]) {
| ^
# | 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... |