Submission #793863

#TimeUsernameProblemLanguageResultExecution timeMemory
793863ymmIOI Fever (JOI21_fever)C++17
6 / 100
1 ms1108 KiB
#include <bits/stdc++.h> #define Loop(x,l,r) for (ll x = (l); x < (r); ++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; int X[N], Y[N]; int dis[N]; int n; enum dir { W, A, S, D}; map<int,vector<int>> *dvec[4][2] = { {&dw, &wa}, {&as, &wa}, {&as, &sd}, {&dw, &sd}, }; pair<int,dir> colide(int i, int j, dir d) { int x = X[j] - X[i]; int y = Y[j] - Y[i]; 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}; } } int bfs(int v, dir d) { vector<pair<int,dir>> q = {{v, d}}; memset(dis, -1, sizeof(dis)); dis[v] = 0; Loop (i,0,q.size()) { auto [v, d] = q[i]; auto &vec1 = (*dvec[d][0])[X[v]-Y[v]]; auto &vec2 = (*dvec[d][1])[X[v]+Y[v]]; for (auto _vec : {&vec1, &vec2}) { auto &vec = *_vec; while (vec.size()) { int u = vec.back(); if (dis[u] != -1) { vec.pop_back(); continue; } auto [di, d2] = colide(v, u, d); if (di < dis[v]) break; vec.pop_back(); dis[u] = di; q.push_back({u, d2}); } } } 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); } 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]; }); ans = max(ans, bfs(0, d)); } cout << ans << '\n'; }

Compilation message (stderr)

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