# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
853241 |
2023-09-23T17:57:54 Z |
NK_ |
Portals (BOI14_portals) |
C++17 |
|
538 ms |
88852 KB |
// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define pb push_back
#define pf push_front
#define mp make_pair
#define f first
#define s second
#define sz(x) int(x.size())
template<class T> using V = vector<T>;
using pi = pair<int, int>;
using vi = V<int>;
using vpi = V<pi>;
using ll = long long;
using pl = pair<ll, ll>;
using vpl = V<pl>;
using vl = V<ll>;
using db = long double;
template<class T> using pq = priority_queue<T, V<T>, greater<T>>;
const int MOD = 1e9 + 7;
const ll INFL = ll(1e17);
const int LG = 18;
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
int main() {
cin.tie(0)->sync_with_stdio(0);
int N, M; cin >> N >> M;
N += 2, M += 2;
V<string> A(N, string(M, '#'));
for(int i = 1; i < N-1; i++) {
string t; cin >> t;
t = "#"+t+"#";
A[i] = t;
}
V<vi> W(N, vi(M, MOD)), vis(N, vi(M, 0));
{
queue<pi> q;
for(int i = 0; i < N; i++) for(int j = 0; j < M; j++) {
if (A[i][j] == '#') {
W[i][j] = 0;
q.push(mp(i, j));
}
}
while(sz(q)) {
auto [r, c] = q.front(); q.pop();
if (vis[r][c]) continue;
vis[r][c] = 1;
for(int d = 0; d < 4; d++) {
int nr = r + dx[d], nc = c + dy[d];
if (nr < 0 || nc < 0 || nr >= N || nc >= M) continue;
if (W[nr][nc] > W[r][c] + 1) {
W[nr][nc] = W[r][c] + 1;
q.push(mp(nr, nc));
}
}
}
}
// for(auto x : A) cout << x << nl;
// for(auto v : W) {
// for(auto x : v) cout << x << " ";
// cout << endl;
// }
pi S, C; for(int i = 0; i < N; i++) for(int j = 0; j < M; j++) {
if (A[i][j] == 'S') {
A[i][j] = '.';
S = mp(i, j);
}
if (A[i][j] == 'C') {
A[i][j] = '.';
C = mp(i, j);
}
}
V<V<vpi>> port(N, V<vpi>(M));
{
pi cur;
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
if (A[i][j] == '#') continue;
if (A[i][j-1] == '#') cur = mp(i, j);
port[i][j].pb(cur);
}
}
}
{
pi cur;
for(int i = 0; i < N; i++) {
for(int j = M - 1; j >= 0; j--) {
if (A[i][j] == '#') continue;
if (A[i][j+1] == '#') cur = mp(i, j);
port[i][j].pb(cur);
}
}
}
{
pi cur;
for(int j = 0; j < M; j++) {
for(int i = 0; i < N; i++) {
if (A[i][j] == '#') continue;
if (A[i-1][j] == '#') cur = mp(i, j);
port[i][j].pb(cur);
}
}
}
{
pi cur;
for(int j = 0; j < M; j++) {
for(int i = N - 1; i >= 0; i--) {
if (A[i][j] == '#') continue;
if (A[i+1][j] == '#') cur = mp(i, j);
port[i][j].pb(cur);
}
}
}
V<vi> D(N, vi(M, MOD));
pq<array<int, 3>> q; q.push({D[S.f][S.s] = 0, S.f, S.s});
while(sz(q)) {
auto [d, r, c] = q.top(); q.pop();
if (D[r][c] != d) continue;
// cout << r << " " << c << " => " << d << endl;
for(int dir = 0; dir < 4; dir++) {
int nr = r + dx[dir], nc = c + dy[dir];
if (A[nr][nc] == '#') continue;
if (D[nr][nc] > D[r][c]+1) q.push({D[nr][nc] = D[r][c]+1, nr, nc});
}
for(auto p : port[r][c]) {
auto [nr, nc] = p;
// cout << nr << ", " << nc << endl;
if (D[nr][nc] > D[r][c]+W[r][c]) q.push({D[nr][nc] = D[r][c]+W[r][c], nr, nc});
}
}
cout << D[C.f][C.s] << nl;
exit(0-0);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
344 KB |
Output is correct |
7 |
Correct |
0 ms |
600 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
344 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
712 KB |
Output is correct |
10 |
Correct |
1 ms |
604 KB |
Output is correct |
11 |
Correct |
1 ms |
672 KB |
Output is correct |
12 |
Correct |
1 ms |
604 KB |
Output is correct |
13 |
Correct |
1 ms |
604 KB |
Output is correct |
14 |
Correct |
0 ms |
344 KB |
Output is correct |
15 |
Correct |
1 ms |
604 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
7 ms |
2908 KB |
Output is correct |
6 |
Correct |
9 ms |
3248 KB |
Output is correct |
7 |
Correct |
9 ms |
3180 KB |
Output is correct |
8 |
Correct |
6 ms |
3160 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
344 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
344 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
604 KB |
Output is correct |
10 |
Correct |
1 ms |
600 KB |
Output is correct |
11 |
Correct |
1 ms |
604 KB |
Output is correct |
12 |
Correct |
1 ms |
684 KB |
Output is correct |
13 |
Correct |
1 ms |
604 KB |
Output is correct |
14 |
Correct |
7 ms |
3024 KB |
Output is correct |
15 |
Correct |
9 ms |
3164 KB |
Output is correct |
16 |
Correct |
9 ms |
3164 KB |
Output is correct |
17 |
Correct |
9 ms |
3164 KB |
Output is correct |
18 |
Correct |
11 ms |
3420 KB |
Output is correct |
19 |
Correct |
14 ms |
3932 KB |
Output is correct |
20 |
Correct |
11 ms |
3796 KB |
Output is correct |
21 |
Correct |
8 ms |
2908 KB |
Output is correct |
22 |
Correct |
8 ms |
3164 KB |
Output is correct |
23 |
Correct |
9 ms |
3164 KB |
Output is correct |
24 |
Correct |
11 ms |
3928 KB |
Output is correct |
25 |
Correct |
0 ms |
344 KB |
Output is correct |
26 |
Correct |
1 ms |
604 KB |
Output is correct |
27 |
Correct |
0 ms |
348 KB |
Output is correct |
28 |
Correct |
6 ms |
3164 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
344 KB |
Output is correct |
6 |
Correct |
0 ms |
344 KB |
Output is correct |
7 |
Correct |
0 ms |
456 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
604 KB |
Output is correct |
10 |
Correct |
1 ms |
704 KB |
Output is correct |
11 |
Correct |
1 ms |
604 KB |
Output is correct |
12 |
Correct |
1 ms |
600 KB |
Output is correct |
13 |
Correct |
1 ms |
604 KB |
Output is correct |
14 |
Correct |
7 ms |
2952 KB |
Output is correct |
15 |
Correct |
9 ms |
3164 KB |
Output is correct |
16 |
Correct |
9 ms |
3164 KB |
Output is correct |
17 |
Correct |
9 ms |
3164 KB |
Output is correct |
18 |
Correct |
11 ms |
3420 KB |
Output is correct |
19 |
Correct |
12 ms |
3932 KB |
Output is correct |
20 |
Correct |
11 ms |
3932 KB |
Output is correct |
21 |
Correct |
8 ms |
3164 KB |
Output is correct |
22 |
Correct |
8 ms |
3164 KB |
Output is correct |
23 |
Correct |
9 ms |
3164 KB |
Output is correct |
24 |
Correct |
327 ms |
72312 KB |
Output is correct |
25 |
Correct |
538 ms |
88852 KB |
Output is correct |
26 |
Correct |
470 ms |
88400 KB |
Output is correct |
27 |
Correct |
455 ms |
88588 KB |
Output is correct |
28 |
Correct |
255 ms |
66608 KB |
Output is correct |
29 |
Correct |
296 ms |
67792 KB |
Output is correct |
30 |
Correct |
328 ms |
68084 KB |
Output is correct |
31 |
Correct |
11 ms |
3944 KB |
Output is correct |
32 |
Correct |
456 ms |
88404 KB |
Output is correct |
33 |
Correct |
0 ms |
348 KB |
Output is correct |
34 |
Correct |
1 ms |
604 KB |
Output is correct |
35 |
Correct |
349 ms |
75520 KB |
Output is correct |
36 |
Correct |
1 ms |
348 KB |
Output is correct |
37 |
Correct |
6 ms |
3164 KB |
Output is correct |
38 |
Correct |
244 ms |
71856 KB |
Output is correct |
39 |
Correct |
225 ms |
62420 KB |
Output is correct |