Submission #793950

#TimeUsernameProblemLanguageResultExecution timeMemory
793950ymmIOI Fever (JOI21_fever)C++17
25 / 100
5042 ms109492 KiB
#include <bits/stdc++.h> #define Loop(x,l,r) for (ll x = (l); x < (r); ++x) #define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x) typedef long long ll; //typedef std::pair<int,int> pii; using namespace std; #define int ll const int N = 100'010; map<int,vector<int>> wa, as, sd, dw, ww, aa, ss, dd; int X[N], Y[N]; int dis[N]; int n; enum dir { W, A, S, D}; map<int,vector<int>> *dvec[4][3] = { {&dw, &wa, &ww}, {&as, &wa, &aa}, {&as, &sd, &ss}, {&dw, &sd, &dd}, }; pair<int,dir> colide(int i, int j, dir d) { int x = X[j] - X[i]; int y = Y[j] - Y[i]; if (x == 0) return {d == D? (y+1)/2: (-y+1)/2, d == D? A: D}; if (y == 0) return {d == W? (x+1)/2: (-x+1)/2, d == W? S: W}; assert(abs(x) == abs(y)); switch (d) { case W: return {y, x > 0? A: D}; case A: return {-x, y > 0? S: W}; case S: return {-y, x > 0? A: D}; case D: return {x, y > 0? S: W}; } } dir disdir[N]; int dij(int v, dir d) { fill(dis, dis+N, (ll)1e18); set<pair<int,int>> S; disdir[v] = d; dis[v] = 0; S.insert({dis[v], v}); int ans = 0; while (S.size()) { ++ans; int v = S.begin()->second; S.erase(S.begin()); dir d = disdir[v]; auto &vec1 = (*dvec[d][0])[X[v]-Y[v]]; auto &vec2 = (*dvec[d][1])[X[v]+Y[v]]; auto &vec3 = (*dvec[d][2])[(d == A || d == D? Y[v]: X[v])]; for (auto _vec : {&vec1, &vec2, &vec3}) { auto &vec = *_vec; //while (vec.size()) { // int u = vec.back(); Loop (i,0,vec.size()) { int u = vec[i]; auto [di, d2] = colide(v, u, d); if (di < dis[v]) continue; if (di < dis[u]) { S.erase({dis[u], u}); dis[u] = di; disdir[u] = d2; S.insert({dis[u], u}); } else { continue; } } } } return ans; //return q.size(); } signed main() { cin.tie(0) -> sync_with_stdio(false); cin >> n; Loop (i,0,n) cin >> X[i] >> Y[i]; Loop (i,1,n) { X[i] -= X[0]; Y[i] -= Y[0]; } X[0] = Y[0] = 0; int ans = 0; for (auto d : {W, A, S, D}) { for (auto mp : {&dw, &wa, &as, &sd}) for (auto &[_, vec] : *mp) vec.clear(); Loop (i,0,n) { dw[X[i]-Y[i]].push_back(i); wa[X[i]+Y[i]].push_back(i); as[X[i]-Y[i]].push_back(i); sd[X[i]+Y[i]].push_back(i); ww[X[i]].push_back(i); aa[Y[i]].push_back(i); ss[X[i]].push_back(i); dd[Y[i]].push_back(i); } for (auto &[_, vec] : dw) sort(vec.begin(), vec.end(), [&](int i, int j){ return X[i] < X[j]; }); for (auto &[_, vec] : wa) sort(vec.begin(), vec.end(), [&](int i, int j){ return X[i] > X[j]; }); for (auto &[_, vec] : as) sort(vec.begin(), vec.end(), [&](int i, int j){ return X[i] > X[j]; }); for (auto &[_, vec] : sd) sort(vec.begin(), vec.end(), [&](int i, int j){ return X[i] < X[j]; }); for (auto &[_, vec] : ww) sort(vec.begin(), vec.end(), [&](int i, int j){ return Y[i] < Y[j]; }); for (auto &[_, vec] : aa) sort(vec.begin(), vec.end(), [&](int i, int j){ return X[i] > X[j]; }); for (auto &[_, vec] : ss) sort(vec.begin(), vec.end(), [&](int i, int j){ return Y[i] > Y[j]; }); for (auto &[_, vec] : dd) sort(vec.begin(), vec.end(), [&](int i, int j){ return X[i] < X[j]; }); ans = max(ans, dij(0, d)); } cout << ans << '\n'; }

Compilation message (stderr)

fever.cpp: In function 'll dij(ll, dir)':
fever.cpp:2:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    2 | #define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
      |                                        ^
fever.cpp:62:4: note: in expansion of macro 'Loop'
   62 |    Loop (i,0,vec.size()) {
      |    ^~~~
fever.cpp: In function 'std::pair<long long int, dir> colide(ll, ll, dir)':
fever.cpp:39:1: warning: control reaches end of non-void function [-Wreturn-type]
   39 | }
      | ^
#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...