Submission #734440

#TimeUsernameProblemLanguageResultExecution timeMemory
734440QwertyPiIOI Fever (JOI21_fever)C++14
11 / 100
9 ms12116 KiB
#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 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...