| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 410355 |
2021-05-22T14:54:06 Z |
jhwest2 |
IOI Fever (JOI21_fever) |
C++14 |
|
10 ms |
11636 KB |
#include <bits/stdc++.h>
#define va first
#define vb second
using namespace std;
typedef long long lint;
typedef pair<int, int> pint;
typedef pair<int, pint> pip;
const int M = 1e5 + 10;
const int Dx[8] = { 2, 1, 0, -1, -2, -1, 0, 1 };
const int Dy[8] = { 0, 1, 2, 1, 0, -1, -2, -1 };
int n, ans, X[M], Y[M], Dir[M], Dist[M][4], Chk[M];
vector<int> V[8][3];
vector<pint> G[M][4];
int dist(int a, int b) {
return abs(X[a] - X[b]) + abs(Y[a] - Y[b]);
}
int get_x(int a, int axis) {
return X[a] * Dx[axis] + Y[a] * Dy[axis];
}
void solve() {
// 0 = Right, 2 = Up, 4 = Left, 6 = Down;
// 1 = Right-Up, 3 = Left-Up, 5 = Left-Down, 7 = Right-Down
for (int i = 2; i <= n; i++) {
if (Y[i] >= X[i] && Y[i] <= -X[i]) Dir[i] = 0;
if (Y[i] < X[i] && Y[i] <= -X[i]) Dir[i] = 2;
if (Y[i] < X[i] && Y[i] > -X[i]) Dir[i] = 4;
if (Y[i] >= X[i] && Y[i] > -X[i]) Dir[i] = 6;
}
// V[i][j] : Vertices with direction j, when we set direction i as right
// 0 : y = x, 1 : y = 0, 2 : y = -x;
for (int j = 0; j < 3; j++) {
for (int i = 0; i < 8; i += 2) V[i][j].clear();
}
for (int i = 1; i <= n; i++) {
V[(Dir[i] + 2) % 8][0].push_back(i);
V[(Dir[i] + 4) % 8][1].push_back(i);
V[(Dir[i] + 6) % 8][2].push_back(i);
}
for (int i = 0; i < 8; i += 2) {
for (int j = 0; j < 3; j++) {
// Direction of x-axis, y-axis
int dx = (i - j + 7) % 8, dy = (i - j + 9) % 8;
sort(V[i][j].begin(), V[i][j].end(), [&](int a, int b) {
pint u = { get_x(a, dx), get_x(a, dy) };
pint v = { get_x(b, dx), get_x(b, dy) };
return u < v;
});
}
}
// Add edges between adjacent vertices
for (int i = 1; i <= n; i++) {
for (int j = 0; j < 3; j++) G[i][j].clear();
}
for (int i = 0; i < 8; i += 2) for (int j = 0; j < 3; j++) {
int dx = (i - j + 7) % 8;
for (int k = 0; k + 1 < V[i][j].size(); k++) {
int u = V[i][j][k], v = V[i][j][k + 1];
if (get_x(u, dx) != get_x(v, dx)) continue;
G[u][j].emplace_back(dist(u, v) / 2, v);
}
}
/* for (int i = 1; i <= n; i++) {
cout << i << "!\n";
for (auto [d, x] : G[i]) {
cout << d << ' ' << x << '\n';
}
} */
// Run Dijkstra
priority_queue<pip, vector<pip>, greater<pip>> Q;
Q.emplace(0, pint(1, 3));
memset(Dist, -1, sizeof Dist); memset(Chk, 0, sizeof Chk);
int cnt = 0;
while (!Q.empty()) {
auto [d, t] = Q.top(); auto [x, p] = t; Q.pop();
if (Dist[x][p] != -1) continue; Dist[x][p] = d;
if (!Chk[x]) ++cnt; Chk[x] = 1;
//cout << x << '\n';
// Using adjacent edges
for (auto [e, y] : G[x][p]) {
Q.emplace(d + e, pint(y, p));
//cout << x << " -> " << y << ": " << d + e << '\n';
}
// Transfer state
int i = Dir[x];
for (int j = 0; j < 3; j++) {
int dx = (i - j + 7) % 8, dy = (i - j + 9) % 8;
X[0] = X[x] + Dx[dy] * d;
Y[0] = Y[x] + Dy[dy] * d;
auto it = lower_bound(V[i][j].begin(), V[i][j].end(), 0, [&](int a, int b) {
pint u = { get_x(a, dx), get_x(a, dy) };
pint v = { get_x(b, dx), get_x(b, dy) };
return u == v ? a < b : u < v;
});
if (it == V[i][j].end() || get_x(0, dx) != get_x(*it, dx)) continue;
Q.emplace(dist(0, *it) / 2, pint(*it, j));
//cout << x << ' ' << "in Direction " << j << ": " << *it << '\n';
//cout << Dist[x][p] << ' ' << X[x] << ' ' << Y[x] << ' ' << X[0] << ' ' << Y[0] << '\n';
}
}
ans = max(ans, cnt);
}
int main() {
//cin.tie(0); ios_base::sync_with_stdio(0);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> X[i] >> Y[i];
X[i] *= 2; Y[i] *= 2;
if (i >= 2) X[i] -= X[1], Y[i] -= Y[1];
}
X[1] = Y[1] = 0;
for (int i = 0; i < 4; i++) {
//cout << i << "!\n";
solve();
// Rotate 90 degrees
for (int j = 2; j <= n; j++) {
swap(X[i], Y[i]); Y[i] = -Y[i];
}
}
cout << ans;
}
Compilation message
fever.cpp: In function 'void solve()':
fever.cpp:59:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | for (int k = 0; k + 1 < V[i][j].size(); k++) {
| ~~~~~~^~~~~~~~~~~~~~~~
fever.cpp:77:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
77 | auto [d, t] = Q.top(); auto [x, p] = t; Q.pop();
| ^
fever.cpp:77:37: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
77 | auto [d, t] = Q.top(); auto [x, p] = t; Q.pop();
| ^
fever.cpp:78:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
78 | if (Dist[x][p] != -1) continue; Dist[x][p] = d;
| ^~
fever.cpp:78:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
78 | if (Dist[x][p] != -1) continue; Dist[x][p] = d;
| ^~~~
fever.cpp:79:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
79 | if (!Chk[x]) ++cnt; Chk[x] = 1;
| ^~
fever.cpp:79:29: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
79 | if (!Chk[x]) ++cnt; Chk[x] = 1;
| ^~~
fever.cpp:83:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
83 | for (auto [e, y] : G[x][p]) {
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
11604 KB |
Output is correct |
| 2 |
Correct |
8 ms |
11612 KB |
Output is correct |
| 3 |
Correct |
8 ms |
11596 KB |
Output is correct |
| 4 |
Correct |
8 ms |
11568 KB |
Output is correct |
| 5 |
Incorrect |
8 ms |
11596 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
11604 KB |
Output is correct |
| 2 |
Correct |
8 ms |
11612 KB |
Output is correct |
| 3 |
Correct |
8 ms |
11596 KB |
Output is correct |
| 4 |
Correct |
8 ms |
11568 KB |
Output is correct |
| 5 |
Incorrect |
8 ms |
11596 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
11596 KB |
Output is correct |
| 2 |
Correct |
8 ms |
11616 KB |
Output is correct |
| 3 |
Correct |
8 ms |
11636 KB |
Output is correct |
| 4 |
Correct |
8 ms |
11616 KB |
Output is correct |
| 5 |
Correct |
8 ms |
11596 KB |
Output is correct |
| 6 |
Correct |
8 ms |
11596 KB |
Output is correct |
| 7 |
Correct |
8 ms |
11612 KB |
Output is correct |
| 8 |
Correct |
10 ms |
11596 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
11604 KB |
Output is correct |
| 2 |
Correct |
8 ms |
11612 KB |
Output is correct |
| 3 |
Correct |
8 ms |
11596 KB |
Output is correct |
| 4 |
Correct |
8 ms |
11568 KB |
Output is correct |
| 5 |
Incorrect |
8 ms |
11596 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
11604 KB |
Output is correct |
| 2 |
Correct |
8 ms |
11612 KB |
Output is correct |
| 3 |
Correct |
8 ms |
11596 KB |
Output is correct |
| 4 |
Correct |
8 ms |
11568 KB |
Output is correct |
| 5 |
Incorrect |
8 ms |
11596 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
11604 KB |
Output is correct |
| 2 |
Correct |
8 ms |
11612 KB |
Output is correct |
| 3 |
Correct |
8 ms |
11596 KB |
Output is correct |
| 4 |
Correct |
8 ms |
11568 KB |
Output is correct |
| 5 |
Incorrect |
8 ms |
11596 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
11604 KB |
Output is correct |
| 2 |
Correct |
8 ms |
11612 KB |
Output is correct |
| 3 |
Correct |
8 ms |
11596 KB |
Output is correct |
| 4 |
Correct |
8 ms |
11568 KB |
Output is correct |
| 5 |
Incorrect |
8 ms |
11596 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
