QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#68082 | #3583. Cyclists versus Clouds | Yunan | AC ✓ | 320ms | 69760kb | C++17 | 3.9kb | 2022-12-14 16:16:25 | 2022-12-14 16:16:26 |
Judging History
answer
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template <class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
//#define int long long int
#define pb push_back
#define pi pair<int, int>
#define pii pair<int, pi>
#define x first
#define y second
#define MAXN 1005
#define mod 998244353
struct poly
{
char c;
int dx, dy, sz;
pi v[101];
void read()
{
cin >> c >> sz;
for (int i = 0; i < sz; i++)
{
cin >> v[i].x >> v[i].y;
v[i].x *= 3;
v[i].y *= 3;
}
get_dir();
}
void get_dir()
{
dx = 0, dy = 0;
if (c == 'N')
dy++;
else if (c == 'S')
dy--;
else if (c == 'E')
dx++;
else
dx--;
}
vector<pi> translate(int x)
{
vector<pi> ans;
for (auto const &i : v)
ans.pb({i.x + (x * dx), i.y + (x * dy)});
return ans;
}
};
int n;
poly v[101];
bool vis[301][301][310];
bool dp[301][301][310];
bool can[301][301][310];
bool can0[301][301][101];
int mat[301][301];
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
bool is(int x, int y)
{
return (x >= 0 && x <= 300 && y >= 0 && y <= 300);
}
void dfs(int x, int y)
{
mat[x][y] = 2;
for (int d = 0; d < 4; d++)
{
int i = x + dx[d], j = y + dy[d];
if (!is(i, j) || mat[i][j] != 0)
continue;
dfs(i, j);
}
}
bool get(int i, int j, int k)
{
if (dp[i][j][k])
return can[i][j][k];
dp[i][j][k] = 1;
can[i][j][k] = 1;
for (int id = 0; id < n; id++)
{
int x = i - (k * v[id].dx), y = j - (k * v[id].dy);
if (is(x, y) && !can0[x][y][id])
return can[i][j][k] = 0;
}
return 1;
}
signed main()
{
int a, b, c, d;
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> a >> b >> c >> d >> n;
a *= 3, b *= 3, c *= 3, d *= 3;
for (int i = 0; i < n; i++)
v[i].read();
for (int k = 0; k < n; k++)
{
memset(mat, 0, sizeof(mat));
pi to_fill = {-1, -1};
for (int i = 0; i < v[k].sz; i++)
{
int j = (i + 1) % v[k].sz;
if (v[k].v[i].x == v[k].v[j].x)
{
int a = min(v[k].v[i].y, v[k].v[j].y);
int b = max(v[k].v[i].y, v[k].v[j].y);
for (int _ = a; _ <= b; _++)
mat[v[k].v[i].x][_] = 1;
pi curr = {v[k].v[i].x - 1, (a + b) >> 1};
to_fill = max(to_fill, curr);
}
else
{
int a = min(v[k].v[i].x, v[k].v[j].x);
int b = max(v[k].v[i].x, v[k].v[j].x);
for (int _ = a; _ <= b; _++)
mat[_][v[k].v[i].y] = 1;
}
}
dfs(to_fill.x, to_fill.y);
for (int i = 0; i <= 300; i++)
{
for (int j = 0; j <= 300; j++)
can0[i][j][k] = (mat[i][j] == 2) ? 0 : 1;
}
}
queue<pii> q;
q.push({0, {a, b}});
while (!q.empty())
{
int x = q.front().y.x;
int y = q.front().y.y;
int t = q.front().x;
q.pop();
if (vis[x][y][t])
continue;
vis[x][y][t] = 1;
if (t + 3 <= 309)
{
for (int d = 0; d < 4; d++)
{
int i = x + dx[d], j = y + dy[d];
int i2 = x + (2 * dx[d]), j2 = y + (2 * dy[d]);
int i3 = x + (3 * dx[d]), j3 = y + (3 * dy[d]);
if (!is(i3, j3))
continue;
if (get(i, j, t + 1) && get(i2, j2, t + 2) && get(i3, j3, t + 3))
q.push({t + 3, {i3, j3}});
}
q.push({t + 3, {x, y}}); // parado
}
}
int ans = 1e9;
for (int i = 0; i <= 309; i++)
{
if (vis[c][d][i])
{
ans = i / 3;
break;
}
}
for (int i = 0; i <= 300; i++)
{
for (int j = 0; j <= 300; j++)
{
if (vis[i][j][309])
{
int t = (abs(i - c) / 3) + (abs(j - d) / 3) + 103;
ans = min(ans, t);
}
}
}
cout << ans << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 50ms
memory: 59152kb
input:
4 0 1 4 1 E 8 0 5 3 5 3 2 5 2 5 1 2 1 2 2 0 2
output:
7
result:
ok single line: '7'
Test #2:
score: 0
Accepted
time: 65ms
memory: 66600kb
input:
50 0 50 100 2 S 4 0 20 50 20 50 80 0 80 S 4 100 20 50 20 50 80 100 80
output:
100
result:
ok single line: '100'
Test #3:
score: 0
Accepted
time: 22ms
memory: 53664kb
input:
50 0 50 100 3 S 4 0 20 50 20 50 80 0 80 S 4 100 20 50 20 50 80 100 80 S 4 49 80 51 80 51 100 49 100
output:
120
result:
ok single line: '120'
Test #4:
score: 0
Accepted
time: 35ms
memory: 56896kb
input:
1 1 1 1 1 S 4 0 0 0 2 2 2 2 0
output:
0
result:
ok single line: '0'
Test #5:
score: 0
Accepted
time: 79ms
memory: 65140kb
input:
29 1 29 25 1 S 8 0 40 29 40 29 20 31 20 31 3 29 3 29 0 0 0
output:
28
result:
ok single line: '28'
Test #6:
score: 0
Accepted
time: 55ms
memory: 60060kb
input:
29 1 29 25 1 S 8 0 40 29 40 29 20 31 20 31 2 29 2 29 0 0 0
output:
43
result:
ok single line: '43'
Test #7:
score: 0
Accepted
time: 51ms
memory: 55932kb
input:
0 0 0 100 1 W 100 0 0 1 0 1 1 2 1 2 2 3 2 3 3 4 3 4 4 5 4 5 5 6 5 6 6 7 6 7 7 8 7 8 8 9 8 9 9 10 9 10 10 11 10 11 11 12 11 12 12 13 12 13 13 14 13 14 14 15 14 15 15 16 15 16 16 17 16 17 17 18 17 18 18 19 18 19 19 20 19 20 20 21 20 21 21 22 21 22 22 23 22 23 23 24 23 24 24 25 24 25 25 26 25 26 26 27 ...
output:
101
result:
ok single line: '101'
Test #8:
score: 0
Accepted
time: 45ms
memory: 56468kb
input:
0 0 0 100 1 W 100 0 0 2 0 2 1 4 1 4 2 6 2 6 3 8 3 8 4 10 4 10 5 12 5 12 6 14 6 14 7 16 7 16 8 18 8 18 9 20 9 20 10 22 10 22 11 24 11 24 12 26 12 26 13 28 13 28 14 30 14 30 15 32 15 32 16 34 16 34 17 36 17 36 18 38 18 38 19 40 19 40 20 42 20 42 21 44 21 44 22 46 22 46 23 48 23 48 24 50 24 50 25 52 25...
output:
150
result:
ok single line: '150'
Test #9:
score: 0
Accepted
time: 48ms
memory: 53156kb
input:
0 0 0 100 1 W 70 0 0 3 0 3 1 6 1 6 2 9 2 9 3 12 3 12 4 15 4 15 5 18 5 18 6 21 6 21 7 24 7 24 8 27 8 27 9 30 9 30 10 33 10 33 11 36 11 36 12 39 12 39 13 42 13 42 14 45 14 45 15 48 15 48 16 51 16 51 17 54 17 54 18 57 18 57 19 60 19 60 20 63 20 63 21 66 21 66 22 69 22 69 23 72 23 72 24 75 24 75 25 78 2...
output:
167
result:
ok single line: '167'
Test #10:
score: 0
Accepted
time: 46ms
memory: 55756kb
input:
0 0 0 100 1 W 100 0 0 1 0 1 1 4 1 4 2 5 2 5 3 8 3 8 4 9 4 9 5 12 5 12 6 14 6 14 7 15 7 15 8 18 8 18 9 19 9 19 10 20 10 20 11 22 11 22 12 25 12 25 13 27 13 27 14 28 14 28 15 31 15 31 16 33 16 33 17 34 17 34 18 37 18 37 19 38 19 38 20 40 20 40 21 42 21 42 22 45 22 45 23 48 23 48 24 51 24 51 25 53 25 5...
output:
145
result:
ok single line: '145'
Test #11:
score: 0
Accepted
time: 139ms
memory: 60160kb
input:
1 50 100 50 20 S 22 31 32 31 39 35 39 35 35 44 35 44 33 45 33 45 38 46 38 46 40 52 40 52 34 53 34 53 31 50 31 50 32 49 32 49 31 47 31 47 30 34 30 34 32 N 18 19 17 19 25 21 25 21 32 23 32 23 25 33 25 33 16 32 16 32 13 36 13 36 9 32 9 32 8 27 8 27 12 24 12 24 17 S 18 20 63 20 69 33 69 33 63 39 63 39 5...
output:
115
result:
ok single line: '115'
Test #12:
score: 0
Accepted
time: 51ms
memory: 57992kb
input:
4 0 1 4 1 S 8 0 5 3 5 3 2 5 2 5 1 2 1 2 2 0 2
output:
8
result:
ok single line: '8'
Test #13:
score: 0
Accepted
time: 60ms
memory: 46564kb
input:
1 50 100 50 20 W 38 57 34 57 39 58 39 58 41 65 41 65 45 67 45 67 41 68 41 68 43 69 43 69 50 66 50 66 49 62 49 62 54 71 54 71 55 72 55 72 56 82 56 82 39 93 39 93 37 92 37 92 23 79 23 79 37 73 37 73 25 66 25 66 26 61 26 61 34 60 34 60 31 58 31 58 34 W 32 64 81 64 91 71 91 71 93 72 93 72 95 73 95 73 96...
output:
150
result:
ok single line: '150'
Test #14:
score: 0
Accepted
time: 135ms
memory: 61908kb
input:
1 50 100 50 20 W 10 26 39 26 55 43 55 43 50 40 50 40 47 43 47 43 34 33 34 33 39 E 10 24 31 24 38 26 38 26 49 32 49 32 43 43 43 43 33 34 33 34 31 E 16 43 33 43 39 49 39 49 49 61 49 61 40 69 40 69 41 79 41 79 35 75 35 75 34 61 34 61 27 52 27 52 33 N 18 65 2 65 13 67 13 67 20 80 20 80 25 73 25 73 35 81...
output:
125
result:
ok single line: '125'
Test #15:
score: 0
Accepted
time: 138ms
memory: 55256kb
input:
1 50 100 50 50 W 18 14 36 14 40 22 40 22 43 28 43 28 41 38 41 38 39 30 39 30 38 39 38 39 28 35 28 35 26 25 26 25 31 21 31 21 36 W 18 50 64 50 67 53 67 53 71 63 71 63 78 73 78 73 67 68 67 68 61 67 61 67 56 60 56 60 60 57 60 57 55 53 55 53 64 S 18 76 42 76 54 83 54 83 53 85 53 85 61 87 61 87 55 91 55 ...
output:
138
result:
ok single line: '138'
Test #16:
score: 0
Accepted
time: 56ms
memory: 22872kb
input:
34 99 74 48 100 S 76 0 0 0 66 7 66 7 9 9 9 9 49 13 49 13 34 15 34 15 42 17 42 17 98 26 98 26 73 29 73 29 24 30 24 30 34 31 34 31 95 33 95 33 98 34 98 34 4 35 4 35 74 36 74 36 84 37 84 37 17 48 17 48 76 49 76 49 71 50 71 50 27 54 27 54 99 60 99 60 23 62 23 62 78 63 78 63 44 66 44 66 73 67 73 67 33 72...
output:
189
result:
ok single line: '189'
Test #17:
score: 0
Accepted
time: 68ms
memory: 21072kb
input:
81 88 12 33 100 E 100 100 74 100 71 99 71 99 69 98 69 98 68 96 68 96 69 94 69 94 70 92 70 92 71 91 71 91 73 90 73 90 71 88 71 88 72 87 72 87 71 86 71 86 72 82 72 82 71 81 71 81 70 80 70 80 68 79 68 79 69 75 69 75 70 68 70 68 73 67 73 67 70 63 70 63 72 62 72 62 73 60 73 60 68 57 68 57 73 56 73 56 68 ...
output:
212
result:
ok single line: '212'
Test #18:
score: 0
Accepted
time: 50ms
memory: 16920kb
input:
4 70 60 22 100 S 100 42 100 43 100 43 99 72 99 72 95 44 95 44 94 57 94 57 93 72 93 72 91 70 91 70 88 56 88 56 87 43 87 43 86 50 86 50 84 51 84 51 83 50 83 50 81 64 81 64 80 58 80 58 79 49 79 49 77 53 77 53 74 48 74 48 73 47 73 47 72 57 72 57 69 46 69 46 68 58 68 58 64 56 64 56 61 54 61 54 58 64 58 6...
output:
200
result:
ok single line: '200'
Test #19:
score: 0
Accepted
time: 67ms
memory: 24088kb
input:
19 81 54 90 95 N 100 1 38 1 81 2 81 2 69 4 69 4 78 5 78 5 50 9 50 9 73 11 73 11 99 14 99 14 84 16 84 16 40 18 40 18 49 20 49 20 85 21 85 21 99 27 99 27 49 29 49 29 74 31 74 31 94 33 94 33 65 34 65 34 55 35 55 35 86 38 86 38 79 39 79 39 51 44 51 44 75 46 75 46 48 49 48 49 81 53 81 53 87 56 87 56 70 5...
output:
125
result:
ok single line: '125'
Test #20:
score: 0
Accepted
time: 104ms
memory: 52088kb
input:
1 50 100 50 20 W 32 37 73 37 79 49 79 49 77 50 77 50 85 58 85 58 72 66 72 66 70 62 70 62 67 60 67 60 66 58 66 58 65 57 65 57 64 51 64 51 63 53 63 53 57 49 57 49 58 41 58 41 68 42 68 42 69 39 69 39 71 41 71 41 73 W 26 37 26 37 31 46 31 46 35 54 35 54 36 63 36 63 31 69 31 69 29 71 29 71 25 76 25 76 17...
output:
121
result:
ok single line: '121'
Test #21:
score: 0
Accepted
time: 9ms
memory: 20140kb
input:
1 50 100 50 20 W 32 16 55 16 61 19 61 19 67 20 67 20 70 22 70 22 73 32 73 32 59 30 59 30 53 41 53 41 52 42 52 42 53 44 53 44 52 53 52 53 36 40 36 40 51 39 51 39 47 36 47 36 43 24 43 24 50 22 50 22 53 19 53 19 55 W 24 4 30 4 47 14 47 14 57 12 57 12 67 24 67 24 63 31 63 31 58 35 58 35 56 25 56 25 57 2...
output:
178
result:
ok single line: '178'
Test #22:
score: 0
Accepted
time: 118ms
memory: 38188kb
input:
1 50 5 90 100 W 24 37 32 37 43 47 43 47 45 49 45 49 37 52 37 52 34 53 34 53 35 54 35 54 42 56 42 56 38 62 38 62 28 56 28 56 24 54 24 54 22 47 22 47 24 41 24 41 32 N 24 11 57 11 59 21 59 21 63 23 63 23 64 28 64 28 57 30 57 30 53 33 53 33 54 44 54 44 48 34 48 34 43 23 43 23 50 21 50 21 52 19 52 19 55 ...
output:
106
result:
ok single line: '106'
Test #23:
score: 0
Accepted
time: 52ms
memory: 55600kb
input:
1 2 1 3 1 N 4 1 4 2 4 2 1 1 1
output:
1
result:
ok single line: '1'
Test #24:
score: 0
Accepted
time: 21ms
memory: 18248kb
input:
1 50 100 50 50 W 14 48 57 48 77 56 77 56 89 72 89 72 88 79 88 79 66 65 66 65 57 61 57 61 50 57 50 57 57 W 26 54 52 54 73 73 73 73 55 81 55 81 49 95 49 95 34 80 34 80 31 83 31 83 29 86 29 86 8 79 8 79 19 74 19 74 21 63 21 63 13 60 13 60 25 62 25 62 49 71 49 71 52 W 22 18 42 18 62 28 62 28 43 47 43 47...
output:
193
result:
ok single line: '193'
Test #25:
score: 0
Accepted
time: 44ms
memory: 43272kb
input:
1 50 100 50 20 W 32 68 67 68 69 75 69 75 71 73 71 73 75 68 75 68 77 73 77 73 78 68 78 68 84 69 84 69 90 70 90 70 96 73 96 73 95 74 95 74 90 77 90 77 92 87 92 87 89 95 89 95 77 85 77 85 76 90 76 90 73 85 73 85 67 W 34 36 9 36 18 40 18 40 24 43 24 43 26 40 26 40 33 52 33 52 38 48 38 48 46 54 46 54 42 ...
output:
150
result:
ok single line: '150'
Test #26:
score: 0
Accepted
time: 12ms
memory: 18860kb
input:
1 50 100 50 20 W 22 34 59 34 71 41 71 41 79 50 79 50 69 46 69 46 61 53 61 53 57 58 57 58 55 59 55 59 48 57 48 57 44 49 44 49 48 38 48 38 57 41 57 41 59 W 22 76 42 76 58 79 58 79 62 80 62 80 65 81 65 81 71 88 71 88 72 92 72 92 68 98 68 98 61 92 61 92 60 98 60 98 54 87 54 87 52 86 52 86 42 W 28 31 55 ...
output:
188
result:
ok single line: '188'
Test #27:
score: 0
Accepted
time: 8ms
memory: 25420kb
input:
1 50 100 50 20 W 26 46 31 46 44 51 44 51 33 60 33 60 21 71 21 71 14 68 14 68 13 71 13 71 9 68 9 68 3 66 3 66 2 56 2 56 12 54 12 54 15 56 15 56 16 48 16 48 23 47 23 47 31 W 32 59 56 59 63 70 63 70 60 71 60 71 65 77 65 77 73 79 73 79 65 82 65 82 63 85 63 85 58 91 58 91 60 95 60 95 58 98 58 98 50 90 50...
output:
176
result:
ok single line: '176'
Test #28:
score: 0
Accepted
time: 25ms
memory: 26240kb
input:
1 50 100 50 50 W 30 60 63 60 71 68 71 68 76 66 76 66 78 63 78 63 88 66 88 66 89 74 89 74 88 81 88 81 82 74 82 74 78 84 78 84 77 86 77 86 74 76 74 76 72 81 72 81 69 80 69 80 61 74 61 74 68 73 68 73 63 W 22 38 65 38 71 45 71 45 75 40 75 40 79 43 79 43 84 45 84 45 88 50 88 50 84 54 84 54 88 56 88 56 91...
output:
179
result:
ok single line: '179'
Test #29:
score: 0
Accepted
time: 49ms
memory: 23992kb
input:
1 50 100 50 100 E 28 59 44 59 56 66 56 66 60 80 60 80 58 82 58 82 51 86 51 86 49 96 49 96 46 98 46 98 36 91 36 91 43 90 43 90 42 84 42 84 35 92 35 92 32 82 32 82 34 74 34 74 39 65 39 65 44 S 26 33 49 33 53 39 53 39 54 48 54 48 55 46 55 46 58 48 58 48 62 60 62 60 60 63 60 63 66 70 66 70 53 72 53 72 3...
output:
191
result:
ok single line: '191'
Test #30:
score: 0
Accepted
time: 49ms
memory: 32116kb
input:
50 5 90 5 100 S 20 63 37 63 43 78 43 78 41 79 41 79 54 84 54 84 49 93 49 93 35 92 35 92 23 80 23 80 28 74 28 74 33 80 33 80 35 72 35 72 37 N 34 57 36 57 47 62 47 62 52 68 52 68 62 76 62 76 71 92 71 92 60 79 60 79 46 73 46 73 40 82 40 82 44 84 44 84 40 86 40 86 33 88 33 88 31 90 31 90 26 82 26 82 29 ...
output:
117
result:
ok single line: '117'
Test #31:
score: 0
Accepted
time: 320ms
memory: 59004kb
input:
1 50 100 50 100 E 16 87 75 87 80 92 80 92 77 93 77 93 74 96 74 96 70 95 70 95 66 94 66 94 65 90 65 90 72 89 72 89 75 S 20 50 68 50 72 53 72 53 75 56 75 56 78 59 78 59 70 58 70 58 69 62 69 62 67 59 67 59 65 56 65 56 67 55 67 55 65 52 65 52 68 E 10 44 29 44 35 53 35 53 33 52 33 52 25 51 25 51 24 48 24...
output:
115
result:
ok single line: '115'
Test #32:
score: 0
Accepted
time: 39ms
memory: 57444kb
input:
0 0 0 1 1 W 4 1 1 1 0 0 0 0 1
output:
2
result:
ok single line: '2'
Test #33:
score: 0
Accepted
time: 47ms
memory: 58640kb
input:
20 1 1 10 2 E 4 1 30 15 30 15 0 1 0 S 4 0 29 100 29 100 22 0 22
output:
32
result:
ok single line: '32'
Test #34:
score: 0
Accepted
time: 127ms
memory: 69760kb
input:
42 42 42 42 0
output:
0
result:
ok single line: '0'
Test #35:
score: 0
Accepted
time: 6ms
memory: 16996kb
input:
0 0 100 100 4 N 4 0 0 0 100 100 100 100 0 E 4 0 0 0 100 100 100 100 0 W 4 0 0 0 100 100 100 100 0 S 4 0 0 0 100 100 100 100 0
output:
300
result:
ok single line: '300'
Test #36:
score: 0
Accepted
time: 36ms
memory: 56736kb
input:
50 0 50 100 1 S 4 0 20 60 20 60 100 0 100
output:
120
result:
ok single line: '120'
Test #37:
score: 0
Accepted
time: 82ms
memory: 67756kb
input:
50 0 50 100 1 S 4 0 20 100 20 100 21 0 21
output:
101
result:
ok single line: '101'