Submission #793897

#TimeUsernameProblemLanguageResultExecution timeMemory
793897ymmIOI Fever (JOI21_fever)C++17
25 / 100
5033 ms46488 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; 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}; } } 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]]; for (auto _vec : {&vec1, &vec2}) { auto &vec = *_vec; //while (vec.size()) { // int u = vec.back(); LoopR (i,0,vec.size()) { int u = vec[i]; auto [di, d2] = colide(v, u, d); if (di < dis[v]) break; if (di < dis[u]) { S.erase({dis[u], u}); dis[u] = di; disdir[u] = d2; S.insert({dis[u], u}); } } } } 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); } 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, dij(0, d)); } cout << ans << '\n'; }

Compilation message (stderr)

fever.cpp: In function 'std::pair<long long int, dir> colide(ll, ll, dir)':
fever.cpp:35:1: warning: control reaches end of non-void function [-Wreturn-type]
   35 | }
      | ^
#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...