Submission #386287

#TimeUsernameProblemLanguageResultExecution timeMemory
386287model_codeIOI Fever (JOI21_fever)C++17
100 / 100
1436 ms128400 KiB
#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 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...