Submission #400325

#TimeUsernameProblemLanguageResultExecution timeMemory
40032512tqianIOI Fever (JOI21_fever)C++17
25 / 100
5072 ms6344 KiB
#include <bits/stdc++.h> using namespace std; #define f1r(i, a, b) for (int i = a; i < b; ++i) #define f0r(i, a) f1r(i, 0, a) #define each(t, a) for (auto& t : a) #define mp make_pair #define f first #define s second #define pb push_back #define eb emplace_back #define sz(x) (int)(x).size() #define all(x) begin(x), end(x) typedef long long ll; typedef vector<int> vi; typedef vector<ll> vl; typedef pair<int, int> pi; typedef pair<ll, ll> pl; typedef vector<pi> vpi; typedef vector<pl> vpl; template <class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; } template <class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; } const ll INF = 1e18; int main() { cin.tie(0)->sync_with_stdio(0); int n; cin >> n; vpi p(n); f0r(i, n) cin >> p[i].f >> p[i].s; auto run_dijkstra = [&](int beg) -> int { typedef pair<ll, int> T; priority_queue<T, vector<T>, greater<T>> pq; vl dist(4 * n, INF); auto ad = [&](int a, ll b) { if (dist[a] <= b) return; pq.push({dist[a] = b, a}); }; ad(beg, 0); while (!pq.empty()) { auto x = pq.top(); pq.pop(); int u = x.s / 4; int d = x.s % 4; if (dist[4 * u + d] < x.f) { continue; } f0r(i, n) { if (i == u) continue; ll nd = max(abs(p[i].f - p[u].f), abs(p[i].s - p[u].s)); if (p[i].f == p[u].f) { nd = abs(p[i].s - p[u].s); } else if (p[i].s == p[u].s) { nd = abs(p[i].f - p[u].f); } if (nd < x.f) continue; if (p[i].f == p[u].f) { if (p[i].s < p[u].s) { if (d == 2) { ad(4 * i + 0, nd); } } else { if (d == 0) { ad(4 * i + 2, nd); } } } else if (p[i].s == p[u].s) { if (p[i].f < p[u].f) { if (d == 3) { ad(4 * i + 1, nd); } } else { if (d == 1) { ad(4 * i + 3, nd); } } } else if (p[i].f + p[i].s == p[u].f + p[u].s) { if (p[i].f < p[u].f) { if (d == 3) { ad(4 * i + 2, nd); } else if (d == 0) { ad(4 * i + 1, nd); } } else { if (d == 2) { ad(4 * i + 3, nd); } else if (d == 1) { ad(4 * i + 0, nd); } } } else if (p[i].f - p[i].s == p[u].f - p[u].s) { if (p[i].f < p[u].f) { if (d == 3) { ad(4 * i + 0, nd); } else if (d == 2) { ad(4 * i + 1, nd); } } else { if (d == 0) { ad(4 * i + 3, nd); } else if (d == 1) { ad(4 * i + 2, nd); } } } } } int res = 0; f0r(i, n) { int a = 0; f0r(d, 4) { a += (dist[4 * i + d] < INF); } assert(a <= 1); res += a; } return res; }; int ans = 0; f0r(d, 4) { ckmax(ans, run_dijkstra(d)); } cout << ans << '\n'; return 0; } /** * first try n^2 bash * 0 - up * 1 - right * 2 - down * 3 - left */
#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...