Submission #397649

#TimeUsernameProblemLanguageResultExecution timeMemory
397649phathnvIOI Fever (JOI21_fever)C++11
0 / 100
20 ms28492 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e5 + 7; const int INF = 1e9 + 7; struct Edge{ int v, w; Edge(int _v, int _w){ v = _v; w = _w; } }; int n, x[N], y[N], curInd, ind[N][4], f[N][2][4], nxt[N][2][4], ord[N], dist[N * 12]; vector<Edge> adj[N * 12]; bool imp[N]; int Dist(int a, int b){ int dx = abs(x[a] - x[b]); int dy = abs(y[a] - y[b]); assert(dx == dy); return dx; } int Calc(int s){ for(int i = 1; i <= curInd; i++) dist[i] = INF; priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; dist[s] = 0; pq.push({0, s}); while (!pq.empty()){ int u = pq.top().second; int d = pq.top().first; pq.pop(); if (d != dist[u]) continue; for(Edge e : adj[u]) if (dist[e.v] > dist[u] + e.w){ dist[e.v] = dist[u] + e.w; pq.push({dist[e.v], e.v}); } if (u <= 4 * n){ int dir = (u - 1) % 4; u = (u + 3) / 4; for(int type = 0; type < 2; type++){ int v = u; while (nxt[v][type][dir] != v && Dist(u, v) < d) v = nxt[v][type][dir]; if (u == v) v = nxt[v][type][dir]; if (u != v && Dist(u, v) >= d && dist[f[v][type][dir]] > Dist(u, v)){ dist[f[v][type][dir]] = Dist(u, v); pq.push({Dist(u, v), f[v][type][dir]}); } } } } int res = 0; for(int i = 1; i <= n; i++) for(int dir = 0; dir < 4; dir++) res += (dist[ind[i][dir]] != INF); return res; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); freopen("inp.txt", "r", stdin); cin >> n; for(int i = 1; i <= n; i++){ cin >> x[i] >> y[i]; x[i] *= 2; y[i] *= 2; ord[i] = i; } for(int i = 1; i <= n; i++) for(int dir = 0; dir < 4; dir++) ind[i][dir] = ++curInd; for(int i = 1; i <= n; i++) for(int type = 0; type < 2; type++) for(int dir = 0; dir < 4; dir++) f[i][type][dir] = ++curInd; for(int i = 1; i <= n; i++){ adj[f[i][0][0]].push_back(Edge(ind[i][3], 0)); adj[f[i][0][1]].push_back(Edge(ind[i][2], 0)); adj[f[i][0][2]].push_back(Edge(ind[i][1], 0)); adj[f[i][0][3]].push_back(Edge(ind[i][0], 0)); adj[f[i][1][0]].push_back(Edge(ind[i][1], 0)); adj[f[i][1][1]].push_back(Edge(ind[i][0], 0)); adj[f[i][1][2]].push_back(Edge(ind[i][3], 0)); adj[f[i][1][3]].push_back(Edge(ind[i][2], 0)); } sort(ord + 1, ord + 1 + n, [&](const int &a, const int &b){ return pair<int, int>(x[a] - y[a], x[a]) < pair<int, int>(x[b] - y[b], x[b]); }); for(int l = 1; l <= n; l++){ int r = l; while (r <= n && x[ord[l]] - y[ord[l]] == x[ord[r]] - y[ord[r]]) r++; r--; for(int i = l; i <= r; i++){ int u = ord[i]; nxt[u][0][0] = (i == r? u : ord[i + 1]); nxt[u][0][1] = (i == r? u : ord[i + 1]); nxt[u][0][2] = (i == l? u : ord[i - 1]); nxt[u][0][3] = (i == l? u : ord[i - 1]); } for(int i = l; i < r; i++){ int u = ord[i]; int v = ord[i + 1]; int d = Dist(u, v); adj[f[u][0][0]].push_back(Edge(f[v][0][0], d)); adj[f[u][0][1]].push_back(Edge(f[v][0][1], d)); adj[f[v][0][2]].push_back(Edge(f[u][0][2], d)); adj[f[v][0][3]].push_back(Edge(f[u][0][3], d)); } l = r; } sort(ord + 1, ord + 1 + n, [&](const int &a, const int &b){ return pair<int, int>(x[a] + y[a], x[a]) < pair<int, int>(x[b] + y[b], x[b]); }); for(int l = 1; l <= n; l++){ int r = l; while (r <= n && x[ord[l]] + y[ord[l]] == x[ord[r]] + y[ord[r]]) r++; r--; for(int i = l; i <= r; i++){ int u = ord[i]; nxt[u][1][0] = (i == l? u : ord[i - 1]); nxt[u][1][1] = (i == r? u : ord[i + 1]); nxt[u][1][2] = (i == r? u : ord[i + 1]); nxt[u][1][3] = (i == l? u : ord[i - 1]); } for(int i = l; i < r; i++){ int u = ord[i]; int v = ord[i + 1]; int d = Dist(u, v); adj[f[v][1][0]].push_back(Edge(f[u][1][0], d)); adj[f[u][1][1]].push_back(Edge(f[v][1][1], d)); adj[f[u][1][2]].push_back(Edge(f[v][1][2], d)); adj[f[v][1][3]].push_back(Edge(f[u][1][3], d)); } l = r; } int res = 0; for(int dir = 0; dir < 4; dir++) res = max(res, Calc(ind[1][dir])); cout << res; return 0; }

Compilation message (stderr)

fever.cpp: In function 'int main()':
fever.cpp:71:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   71 |     freopen("inp.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#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...