Submission #777619

#TimeUsernameProblemLanguageResultExecution timeMemory
777619marvinthangIOI Fever (JOI21_fever)C++17
37 / 100
5055 ms236324 KiB
/************************************* * author: marvinthang * * created: 09.07.2023 15:47:28 * *************************************/ #include <bits/stdc++.h> using namespace std; #define fi first #define se second #define left ___left #define right ___right #define TIME (1.0 * clock() / CLOCKS_PER_SEC) #define MASK(i) (1LL << (i)) #define BIT(x, i) ((x) >> (i) & 1) #define __builtin_popcount __builtin_popcountll #define ALL(v) (v).begin(), (v).end() #define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i) #define REPD(i, n) for (int i = (n); i--; ) #define FOR(i, a, b) for (int i = (a), _b = (b); i < _b; ++i) #define FORD(i, b, a) for (int i = (b), _a = (a); --i >= _a; ) #define FORE(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i) #define FORDE(i, b, a) for (int i = (b), _a = (a); i >= _a; --i) #define scan_op(...) istream & operator >> (istream &in, __VA_ARGS__ &u) #define print_op(...) ostream & operator << (ostream &out, const __VA_ARGS__ &u) #ifdef LOCAL #include "debug.h" #else #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); } #define DB(...) 23 #define db(...) 23 #define debug(...) 23 #endif template <class U, class V> scan_op(pair <U, V>) { return in >> u.first >> u.second; } template <class T> scan_op(vector <T>) { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; } template <class U, class V> print_op(pair <U, V>) { return out << '(' << u.first << ", " << u.second << ')'; } template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")"; else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); } template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); } template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; } template <class A, class B> bool minimize(A &a, B b) { if (a > b) { a = b; return true; } return false; } template <class A, class B> bool maximize(A &a, B b) { if (a < b) { a = b; return true; } return false; } // end of template const long long INF = 1e18; const int MAX = 1e5 + 5; int N, X[MAX], Y[MAX]; void init(void) { cin >> N; REP(i, N) cin >> X[i] >> Y[i]; REPD(i, N) X[i] -= X[0], Y[i] -= Y[0]; } int dir[MAX]; bool inter(int u, int v) { if (dir[u] == dir[v]) return false; if ((dir[u] ^ dir[v]) == 2) { if (BIT(dir[u], 0)) { if (Y[u] != Y[v]) return false; return dir[u] == 1 ? X[u] <= X[v] : X[u] >= X[v]; } if (X[u] != X[v]) return false; return dir[u] ? Y[u] >= Y[v] : Y[u] <= Y[v]; } if ((dir[u] ^ dir[v]) == 1) { if (X[u] + Y[u] != X[v] + Y[v]) return false; return X[u] > X[v] ? dir[u] == 0 || dir[u] == 3 : dir[v] == 0 || dir[v] == 3; } if (X[u] - Y[u] != X[v] - Y[v]) return false; return X[u] > X[v] ? dir[u] == 2 || dir[u] == 3 : dir[v] == 2 || dir[v] == 3; } long long dist[MAX][3]; bool visited[MAX]; vector <pair <int, int>> tadj[MAX][3]; int get_dist(int x, int y) { return abs(X[x] - X[y]) + abs(Y[x] - Y[y]); } void process(void) { int res = 0; REP(rt, 4) { dir[0] = 1; FOR(i, 1, N) { if (X[i] >= 0) { if (Y[i] >= 0) dir[i] = X[i] <= Y[i] ? 2 : 3; else dir[i] = X[i] <= -Y[i] ? 0 : 3; } else { if (Y[i] >= 0) dir[i] = -X[i] < Y[i] ? 2 : 1; else dir[i] = -X[i] < -Y[i] ? 0 : 1; } } map <int, set <pair <int, int>>> sum[4], diff[4], sx[4], sy[4]; REP(i, N) { REP(j, 12) { dist[i][j] = INF; tadj[i][j].clear(); } visited[i] = false; sum[dir[i]][X[i] + Y[i]].emplace(X[i], i); diff[dir[i]][X[i] - Y[i]].emplace(X[i], i); sx[dir[i]][X[i]].emplace(Y[i], i); sy[dir[i]][Y[i]].emplace(X[i], i); REP(d, 4) { sum[d][X[i] + Y[i]].emplace(-1e9, -1); sum[d][X[i] + Y[i]].emplace(1e9, -1); diff[d][X[i] - Y[i]].emplace(-1e9, -1); diff[d][X[i] - Y[i]].emplace(1e9, -1); sx[d][X[i]].emplace(-1e9, -1); sx[d][X[i]].emplace(1e9, -1); sy[d][Y[i]].emplace(-1e9, -1); sy[d][Y[i]].emplace(1e9, -1); } } REP(i, N) { int sdir = dir[i] ^ 1; int ddir = dir[i] ^ 3; int odir = dir[i] ^ 2; int s = X[i] + Y[i]; int d = X[i] - Y[i]; auto it = sum[dir[i]][s].find(make_pair(X[i], i)); if (dir[i] == 0 || dir[i] == 3) it = next(it); else it = prev(it); int v = it->se; if (v != -1) tadj[i][0].emplace_back(get_dist(i, v), v); it = diff[dir[i]][d].find(make_pair(X[i], i)); if (dir[i] == 2 || dir[i] == 3) it = next(it); else it = prev(it); v = it->se; if (v != -1) tadj[i][1].emplace_back(get_dist(i, v), v); if (!BIT(dir[i], 0)) { it = sx[dir[i]][X[i]].find(make_pair(Y[i], i)); if (dir[i] == 2) it = next(it); else it = prev(it); } else { it = sy[dir[i]][Y[i]].find(make_pair(X[i], i)); if (dir[i] == 3) it = next(it); else it = prev(it); } v = it->se; if (v != -1) tadj[i][2].emplace_back(get_dist(i, v), v); } priority_queue <tuple <long long, int, int>, vector <tuple <long long, int, int>>, greater <tuple <long long, int, int>>> pq; pq.emplace(0, 0, -1); int cnt = 0; while (!pq.empty()) { auto [du, u, t] = pq.top(); pq.pop(); if (t != -1) { if (dist[u][t] != du) continue; for (auto [w, v]: tadj[u][t]) if (minimize(dist[v][t], du + w)) pq.emplace(dist[v][t], v, t); } if (visited[u]) continue; visited[u] = true; vector <tuple <int, int, int>> adj; int sdir = dir[u] ^ 1; int ddir = dir[u] ^ 3; int odir = dir[u] ^ 2; int s = X[u] + Y[u]; int d = X[u] - Y[u]; sum[dir[u]][X[u] + Y[u]].erase(make_pair(X[u], u)); diff[dir[u]][X[u] - Y[u]].erase(make_pair(X[u], u)); sx[dir[u]][X[u]].erase(make_pair(Y[u], u)); sy[dir[u]][Y[u]].erase(make_pair(X[u], u)); set<pair <int, int>>::iterator it; if (dir[u] == 0 || dir[u] == 3) it = prev(sum[sdir][s].lower_bound(make_pair(X[u] - du / 2, -1))); else it = sum[sdir][s].lower_bound(make_pair(X[u] + (du + 1) / 2, -1)); int v = it->se; if (v != -1) adj.emplace_back(0, get_dist(u, v), v); it = diff[ddir][d].lower_bound(make_pair(X[u], -1)); if (dir[u] == 2 || dir[u] == 3) it = prev(diff[ddir][d].lower_bound(make_pair(X[u] - du / 2, -1))); else it = diff[ddir][d].lower_bound(make_pair(X[u] + (du + 1) / 2, -1)); v = it->se; if (v != -1) adj.emplace_back(1, get_dist(u, v), v); if (!BIT(dir[u], 0)) { if (dir[u] == 2) it = prev(sx[odir][X[u]].lower_bound(make_pair(Y[u] - du, N))); else it = sx[odir][X[u]].lower_bound(make_pair(Y[u] + du, -1)); } else { if (dir[u] == 3) it = prev(sy[odir][Y[u]].lower_bound(make_pair(X[u] - du, N))); else it = sy[odir][Y[u]].lower_bound(make_pair(X[u] + du, -1)); } v = it->se; if (v != -1) adj.emplace_back(2, get_dist(u, v), v); for (auto [t, w, v]: adj) if (w >= du && minimize(dist[v][t], w)) pq.emplace(dist[v][t], v, t); ++cnt; } maximize(res, cnt); REP(i, N) { swap(X[i], Y[i]); X[i] = -X[i]; } } cout << res << '\n'; } int main(void) { ios_base::sync_with_stdio(false); cin.tie(nullptr); // cout.tie(nullptr); file("fever"); init(); process(); cerr << "Time elapsed: " << TIME << " s.\n"; return (0^0); }

Compilation message (stderr)

fever.cpp: In function 'void process()':
fever.cpp:124:8: warning: unused variable 'sdir' [-Wunused-variable]
  124 |    int sdir = dir[i] ^ 1;
      |        ^~~~
fever.cpp:125:8: warning: unused variable 'ddir' [-Wunused-variable]
  125 |    int ddir = dir[i] ^ 3;
      |        ^~~~
fever.cpp:126:8: warning: unused variable 'odir' [-Wunused-variable]
  126 |    int odir = dir[i] ^ 2;
      |        ^~~~
fever.cpp: In function 'int main()':
fever.cpp:30:61: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
fever.cpp:216:2: note: in expansion of macro 'file'
  216 |  file("fever");
      |  ^~~~
fever.cpp:30:94: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                                                       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
fever.cpp:216:2: note: in expansion of macro 'file'
  216 |  file("fever");
      |  ^~~~
fever.cpp: In function 'void process()':
fever.cpp:104:16: warning: iteration 3 invokes undefined behavior [-Waggressive-loop-optimizations]
  104 |     dist[i][j] = INF;
      |     ~~~~~~~~~~~^~~~~
fever.cpp:19:58: note: within this loop
   19 | #define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
      |                                                          ^
fever.cpp:103:4: note: in expansion of macro 'REP'
  103 |    REP(j, 12) {
      |    ^~~
#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...