| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 397649 |
2021-05-02T18:30:01 Z |
phathnv |
IOI Fever (JOI21_fever) |
C++11 |
|
20 ms |
28492 KB |
#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
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 time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
28492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
28492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
28492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
28492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
28492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
28492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
28492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
