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 <iostream>
#include <vector>
#include <tuple>
#include <queue>
#include <cmath>
#include <algorithm>
#include <functional>
using namespace std;
#pragma warning (disable: 4996)
// 入力など
long long N;
long long X[1 << 17], Y[1 << 17];
long long dir[1 << 19];
// 座標圧縮
vector<long long> GX, GY, GPLUS, GMINS;
vector<tuple<long long, long long, int>> PX[100009][4];
vector<tuple<long long, long long, int>> PY[100009][4];
vector<tuple<long long, long long, int>> PPLUS[100009][4];
vector<tuple<long long, long long, int>> PMINS[100009][4];
long long PLUS[1 << 17], MINS[1 << 17];
// シミュレーション
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> Q;
vector<pair<long long, int>> G[1 << 19];
long long dist[1 << 19], final_dst[1 << 19];
bool used[1 << 19];
bool used2[1 << 19];
// その他
int dx[8] = { 1, 1, 0, -1, -1, -1, 0, 1 };
int dy[8] = { 0, 1, 1, 1, 0, -1, -1, -1 };
void init() {
GX.clear(); GY.clear(); GPLUS.clear(); GMINS.clear();
for (int i = 0; i < 100009; i++) {
PLUS[i] = 0; MINS[i] = 0;
for (int j = 0; j < 4; j++) {
PX[i][j].clear(); PY[i][j].clear();
PPLUS[i][j].clear(); PMINS[i][j].clear();
}
}
for (int i = 0; i < (1 << 19); i++) {
G[i].clear(); dist[i] = 0;
used[i] = false; used2[i] = false;
}
}
long long dst(int p1, int p2) {
return abs(GX[X[p1]] - GX[X[p2]]) + abs(GY[Y[p1]] - GY[Y[p2]]);
}
void henhari(vector<tuple<long long, long long, int>> v, vector<int> t1, vector<int> t2) {
int pre1 = -1, pre2 = -1;
for (int i = 0; i < v.size(); i++) {
int idx = get<2>(v[i]);
if (t1[dir[idx]] == 1) {
if (pre1 != -1) G[pre1 * 3 + t2[dir[idx]]].push_back(make_pair(idx * 3 + t2[dir[idx]], dst(pre1, idx) / 2));
pre1 = idx;
}
if (t1[dir[idx]] == 2) {
if (pre2 != -1) G[idx * 3 + t2[dir[idx]]].push_back(make_pair(pre2 * 3 + t2[dir[idx]], dst(pre2, idx) / 2));
pre2 = idx;
}
}
}
void adds(long long tm, int pos, int ty) {
long long ux = GX[X[pos]];
long long uy = GY[Y[pos]];
long long vx = GX[X[pos]] + tm * dx[dir[pos]] * 2LL;
long long vy = GY[Y[pos]] + tm * dy[dir[pos]] * 2LL;
if (ty == -1) {
int nex = -1;
if (dir[pos] == 0) {
int pos1 = lower_bound(PMINS[MINS[pos]][3].begin(), PMINS[MINS[pos]][3].end(), make_tuple(ux + tm, 0, 0)) - PMINS[MINS[pos]][3].begin();
if (pos1 < PMINS[MINS[pos]][3].size()) nex = get<2>(PMINS[MINS[pos]][3][pos1]);
}
if (dir[pos] == 2) {
int pos1 = lower_bound(PPLUS[PLUS[pos]][0].begin(), PPLUS[PLUS[pos]][0].end(), make_tuple(ux - tm, (1 << 30), (1 << 30))) - PPLUS[PLUS[pos]][0].begin(); pos1--;
if (pos1 >= 0) nex = get<2>(PPLUS[PLUS[pos]][0][pos1]);
}
if (dir[pos] == 4) {
int pos1 = lower_bound(PMINS[MINS[pos]][1].begin(), PMINS[MINS[pos]][1].end(), make_tuple(ux - tm, (1 << 30), (1 << 30))) - PMINS[MINS[pos]][1].begin(); pos1--;
if (pos1 >= 0) nex = get<2>(PMINS[MINS[pos]][1][pos1]);
}
if (dir[pos] == 6) {
int pos1 = lower_bound(PPLUS[PLUS[pos]][2].begin(), PPLUS[PLUS[pos]][2].end(), make_tuple(ux + tm, 0, 0)) - PPLUS[PLUS[pos]][2].begin();
if (pos1 < PPLUS[PLUS[pos]][2].size()) nex = get<2>(PPLUS[PLUS[pos]][2][pos1]);
}
if (nex != -1) {
long long dsts = dst(pos, nex) / 2LL;
if (dist[nex * 3 + 2] > dsts) {
dist[nex * 3 + 2] = dsts;
Q.push(make_pair(dist[nex * 3 + 2], nex * 3 + 2));
}
}
}
if (ty == 0) {
int nex = -1;
if (dir[pos] == 0) {
int pos1 = lower_bound(PY[Y[pos]][2].begin(), PY[Y[pos]][2].end(), make_tuple(vx, vy, 0)) - PY[Y[pos]][2].begin();
if (pos1 < PY[Y[pos]][2].size()) nex = get<2>(PY[Y[pos]][2][pos1]);
}
if (dir[pos] == 2) {
int pos1 = lower_bound(PX[X[pos]][3].begin(), PX[X[pos]][3].end(), make_tuple(vx, vy, 0)) - PX[X[pos]][3].begin();
if (pos1 < PX[X[pos]][3].size()) nex = get<2>(PX[X[pos]][3][pos1]);
}
if (dir[pos] == 4) {
int pos1 = lower_bound(PY[Y[pos]][0].begin(), PY[Y[pos]][0].end(), make_tuple(vx, vy, (1 << 30))) - PY[Y[pos]][0].begin(); pos1--;
if (pos1 >= 0) nex = get<2>(PY[Y[pos]][0][pos1]);
}
if (dir[pos] == 6) {
int pos1 = lower_bound(PX[X[pos]][1].begin(), PX[X[pos]][1].end(), make_tuple(vx, vy, (1 << 30))) - PX[X[pos]][1].begin(); pos1--;
if (pos1 >= 0) nex = get<2>(PX[X[pos]][1][pos1]);
}
if (nex != -1) {
long long dsts = dst(pos, nex) / 2LL;
if (dist[nex * 3 + 1] > dsts) {
dist[nex * 3 + 1] = dsts;
Q.push(make_pair(dist[nex * 3 + 1], nex * 3 + 1));
}
}
}
if (ty == 1) {
int nex = -1;
if (dir[pos] == 0) {
int pos1 = lower_bound(PPLUS[PLUS[pos]][1].begin(), PPLUS[PLUS[pos]][1].end(), make_tuple(ux + tm, 0, 0)) - PPLUS[PLUS[pos]][1].begin();
if (pos1 < PPLUS[PLUS[pos]][1].size()) nex = get<2>(PPLUS[PLUS[pos]][1][pos1]);
}
if (dir[pos] == 2) {
int pos1 = lower_bound(PMINS[MINS[pos]][2].begin(), PMINS[MINS[pos]][2].end(), make_tuple(ux + tm, 0, 0)) - PMINS[MINS[pos]][2].begin();
if (pos1 < PMINS[MINS[pos]][2].size()) nex = get<2>(PMINS[MINS[pos]][2][pos1]);
}
if (dir[pos] == 4) {
int pos1 = lower_bound(PPLUS[PLUS[pos]][3].begin(), PPLUS[PLUS[pos]][3].end(), make_tuple(ux - tm, (1 << 30), (1 << 30))) - PPLUS[PLUS[pos]][3].begin(); pos1--;
if (pos1 >= 0) nex = get<2>(PPLUS[PLUS[pos]][3][pos1]);
}
if (dir[pos] == 6) {
int pos1 = lower_bound(PMINS[MINS[pos]][0].begin(), PMINS[MINS[pos]][0].end(), make_tuple(ux - tm, (1 << 30), (1 << 30))) - PMINS[MINS[pos]][0].begin(); pos1--;
if (pos1 >= 0) nex = get<2>(PMINS[MINS[pos]][0][pos1]);
}
if (nex != -1) {
long long dsts = dst(pos, nex) / 2LL;
if (dist[nex * 3 + 0] > dsts) {
dist[nex * 3 + 0] = dsts;
Q.push(make_pair(dist[nex * 3 + 0], nex * 3 + 0));
}
}
}
}
long long solve() {
init();
// Step A. 向きを決める
dir[0] = 0;
for (int i = 1; i < N; i++) {
if (X[i] > X[0] && abs(X[i] - X[0]) > abs(Y[i] - Y[0])) dir[i] = 4;
else if (X[i] < X[0] && abs(X[i] - X[0]) >= abs(Y[i] - Y[0])) dir[i] = 0;
else if (Y[i] > Y[0]) dir[i] = 6;
else dir[i] = 2;
}
// Step B. 座標圧縮する
for (int i = 0; i < N; i++) PLUS[i] = X[i] + Y[i];
for (int i = 0; i < N; i++) MINS[i] = X[i] - Y[i];
for (int i = 0; i < N; i++) GX.push_back(X[i]);
for (int i = 0; i < N; i++) GY.push_back(Y[i]);
for (int i = 0; i < N; i++) GPLUS.push_back(X[i] + Y[i]);
for (int i = 0; i < N; i++) GMINS.push_back(X[i] - Y[i]);
sort(GX.begin(), GX.end()); GX.erase(unique(GX.begin(), GX.end()), GX.end());
sort(GY.begin(), GY.end()); GY.erase(unique(GY.begin(), GY.end()), GY.end());
sort(GPLUS.begin(), GPLUS.end()); GPLUS.erase(unique(GPLUS.begin(), GPLUS.end()), GPLUS.end());
sort(GMINS.begin(), GMINS.end()); GMINS.erase(unique(GMINS.begin(), GMINS.end()), GMINS.end());
for (int i = 0; i < N; i++) X[i] = lower_bound(GX.begin(), GX.end(), X[i]) - GX.begin();
for (int i = 0; i < N; i++) Y[i] = lower_bound(GY.begin(), GY.end(), Y[i]) - GY.begin();
for (int i = 0; i < N; i++) PLUS[i] = lower_bound(GPLUS.begin(), GPLUS.end(), PLUS[i]) - GPLUS.begin();
for (int i = 0; i < N; i++) MINS[i] = lower_bound(GMINS.begin(), GMINS.end(), MINS[i]) - GMINS.begin();
// Step C. 辺を貼る前準備
for (int i = 0; i < N; i++) PX[X[i]][dir[i] / 2].push_back(make_tuple(GX[X[i]], GY[Y[i]], i));
for (int i = 0; i < N; i++) PY[Y[i]][dir[i] / 2].push_back(make_tuple(GX[X[i]], GY[Y[i]], i));
for (int i = 0; i < N; i++) PPLUS[PLUS[i]][dir[i] / 2].push_back(make_tuple(GX[X[i]], GY[Y[i]], i));
for (int i = 0; i < N; i++) PMINS[MINS[i]][dir[i] / 2].push_back(make_tuple(GX[X[i]], GY[Y[i]], i));
for (int t = 0; t < 4; t++) {
for (int i = 0; i < GX.size(); i++) sort(PX[i][t].begin(), PX[i][t].end());
for (int i = 0; i < GY.size(); i++) sort(PY[i][t].begin(), PY[i][t].end());
for (int i = 0; i < GPLUS.size(); i++) sort(PPLUS[i][t].begin(), PPLUS[i][t].end());
for (int i = 0; i < GMINS.size(); i++) sort(PMINS[i][t].begin(), PMINS[i][t].end());
}
// Step D. 辺を貼る
for (int t = 0; t < 4; t++) {
for (int i = 0; i < GX.size(); i++) henhari(PX[i][t], vector<int>{0, 0, 2, 0, 0, 0, 1, 0}, vector<int>{1, 1, 1, 1, 1, 1, 1, 1});
for (int i = 0; i < GY.size(); i++) henhari(PY[i][t], vector<int>{2, 0, 0, 0, 1, 0, 0, 0}, vector<int>{1, 1, 1, 1, 1, 1, 1, 1});
for (int i = 0; i < GPLUS.size(); i++) henhari(PPLUS[i][t], vector<int>{2, 0, 1, 0, 1, 0, 2, 0}, vector<int>{2, 1, 0, 1, 2, 1, 0, 1});
for (int i = 0; i < GMINS.size(); i++) henhari(PMINS[i][t], vector<int>{2, 0, 2, 0, 1, 0, 1, 0}, vector<int>{0, 1, 2, 1, 0, 1, 2, 1});
}
// Step E. ダイクストラ法
for (int i = 0; i < N * 3; i++) dist[i] = (1LL << 60);
Q.push(make_pair(0, 0));
Q.push(make_pair(0, 1));
Q.push(make_pair(0, 2));
while (!Q.empty()) {
long long tm = Q.top().first;
long long pos = Q.top().second; Q.pop();
if (used2[pos] == false) {
if (tm != 0) used2[pos] = true;
for (int i = 0; i < G[pos].size(); i++) {
int to = G[pos][i].first;
long long cost = G[pos][i].second;
if (dist[to] > dist[pos] + cost) {
dist[to] = dist[pos] + cost;
Q.push(make_pair(dist[to], to));
}
}
}
if (used[pos / 3] == false) {
used[pos / 3] = true;
adds(tm, pos / 3, -1);
adds(tm, pos / 3, 0);
adds(tm, pos / 3, 1);
}
}
for (int i = 0; i < N; i++) X[i] = GX[X[i]];
for (int i = 0; i < N; i++) Y[i] = GY[Y[i]];
for (int i = 0; i < N; i++) final_dst[i] = (1LL << 60);
for (int i = 0; i < N * 3; i++) final_dst[i / 3] = min(final_dst[i / 3], dist[i]);
int cnt = 0;
final_dst[0] = 0;
for (int i = 0; i < N; i++) {
if (final_dst[i] != (1LL << 60)) cnt += 1;
}
return cnt;
}
int main() {
// Step #1. 入力(0-indexed)
scanf("%lld", &N);
for (int i = 0; i < N; i++) {
scanf("%lld%lld", &X[i], &Y[i]);
X[i] *= 2; Y[i] *= 2;
}
// Step #2. 全探索
long long Answer = 0;
for (int t = 0; t < 4; t++) {
long long ret = solve();
Answer = max(Answer, ret);
for (int i = 0; i < N; i++) {
long long sx = X[i], sy = Y[i];
X[i] = -sy;
Y[i] = sx;
}
}
// Step #3. 出力
cout << Answer << endl;
return 0;
}
Compilation message (stderr)
fever.cpp:9: warning: ignoring #pragma warning [-Wunknown-pragmas]
9 | #pragma warning (disable: 4996)
|
fever.cpp: In function 'void henhari(std::vector<std::tuple<long long int, long long int, int> >, std::vector<int>, std::vector<int>)':
fever.cpp:56:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<long long int, long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | for (int i = 0; i < v.size(); i++) {
| ~~^~~~~~~~~~
fever.cpp: In function 'void adds(long long int, int, int)':
fever.cpp:79:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<long long int, long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | if (pos1 < PMINS[MINS[pos]][3].size()) nex = get<2>(PMINS[MINS[pos]][3][pos1]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
fever.cpp:91:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<long long int, long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | if (pos1 < PPLUS[PLUS[pos]][2].size()) nex = get<2>(PPLUS[PLUS[pos]][2][pos1]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
fever.cpp:105:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<long long int, long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
105 | if (pos1 < PY[Y[pos]][2].size()) nex = get<2>(PY[Y[pos]][2][pos1]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
fever.cpp:109:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<long long int, long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
109 | if (pos1 < PX[X[pos]][3].size()) nex = get<2>(PX[X[pos]][3][pos1]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
fever.cpp:131:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<long long int, long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
131 | if (pos1 < PPLUS[PLUS[pos]][1].size()) nex = get<2>(PPLUS[PLUS[pos]][1][pos1]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
fever.cpp:135:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<long long int, long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
135 | if (pos1 < PMINS[MINS[pos]][2].size()) nex = get<2>(PMINS[MINS[pos]][2][pos1]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
fever.cpp:71:12: warning: unused variable 'uy' [-Wunused-variable]
71 | long long uy = GY[Y[pos]];
| ^~
fever.cpp: In function 'long long int solve()':
fever.cpp:189:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
189 | for (int i = 0; i < GX.size(); i++) sort(PX[i][t].begin(), PX[i][t].end());
| ~~^~~~~~~~~~~
fever.cpp:190:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
190 | for (int i = 0; i < GY.size(); i++) sort(PY[i][t].begin(), PY[i][t].end());
| ~~^~~~~~~~~~~
fever.cpp:191:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
191 | for (int i = 0; i < GPLUS.size(); i++) sort(PPLUS[i][t].begin(), PPLUS[i][t].end());
| ~~^~~~~~~~~~~~~~
fever.cpp:192:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
192 | for (int i = 0; i < GMINS.size(); i++) sort(PMINS[i][t].begin(), PMINS[i][t].end());
| ~~^~~~~~~~~~~~~~
fever.cpp:197:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
197 | for (int i = 0; i < GX.size(); i++) henhari(PX[i][t], vector<int>{0, 0, 2, 0, 0, 0, 1, 0}, vector<int>{1, 1, 1, 1, 1, 1, 1, 1});
| ~~^~~~~~~~~~~
fever.cpp:198:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
198 | for (int i = 0; i < GY.size(); i++) henhari(PY[i][t], vector<int>{2, 0, 0, 0, 1, 0, 0, 0}, vector<int>{1, 1, 1, 1, 1, 1, 1, 1});
| ~~^~~~~~~~~~~
fever.cpp:199:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
199 | for (int i = 0; i < GPLUS.size(); i++) henhari(PPLUS[i][t], vector<int>{2, 0, 1, 0, 1, 0, 2, 0}, vector<int>{2, 1, 0, 1, 2, 1, 0, 1});
| ~~^~~~~~~~~~~~~~
fever.cpp:200:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
200 | for (int i = 0; i < GMINS.size(); i++) henhari(PMINS[i][t], vector<int>{2, 0, 2, 0, 1, 0, 1, 0}, vector<int>{0, 1, 2, 1, 0, 1, 2, 1});
| ~~^~~~~~~~~~~~~~
fever.cpp:213:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
213 | for (int i = 0; i < G[pos].size(); i++) {
| ~~^~~~~~~~~~~~~~~
fever.cpp: In function 'int main()':
fever.cpp:245:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
245 | scanf("%lld", &N);
| ~~~~~^~~~~~~~~~~~
fever.cpp:247:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
247 | scanf("%lld%lld", &X[i], &Y[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |