#include <bits/stdc++.h>
//#define int int64_t
using namespace std;
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
int n, m;
vector<pair<int, int>>delta = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
struct wall{
int up, down, left, right;
};
int check(int i, int j, auto&graph, auto&dist){
if(i < n && i>=0 && j < m && j>=0 && graph[i][j] != '#' && dist[i][j] == -1) return 1;
return 0;
}
vector<vector<int>>bfs(auto&graph, auto&start){
queue<pair<int, int>>q;
vector<vector<int>>dist(n, vector<int>(m, -1));
for(auto [x, y]: start){
q.push({x, y});
dist[x][y] = 0;
}
while(q.size()){
int i = q.front().first;
int j = q.front().second;
q.pop();
for(auto [x, y]: delta){
if(check(i+x, j+y, graph, dist)){
dist[i+x][j+y] = dist[i][j] + 1;
q.push({i+x, j+y});
}
}
}
return dist;
}
int dijkstra(auto&next, auto&w, auto&graph, pair<int, int>s, pair<int, int>e){
vector<vector<int>>dist(n, vector<int>(m, -1));
priority_queue<pair<pair<int, int>, int>>pq;
pq.push({{0, s.first}, s.second});
while(pq.size()){
int d = pq.top().first.first;
int i = pq.top().first.second;
int j = pq.top().second;
d = -d;
pq.pop();
if(dist[i][j] != -1) continue;
dist[i][j] = d;
for(auto [x, y]: delta){
if(check(i+x, j+y, graph, dist)){
pq.push({{-(d+1), i+x}, j+y});
}
}
int cur = next[i][j];
int nd = -(d+cur);
if(check(w[i][j].up, j, graph, dist)) pq.push({{nd, w[i][j].up}, j});
if(check(w[i][j].down, j, graph, dist)) pq.push({{nd, w[i][j].down}, j});
if(check(i, w[i][j].right, graph, dist)) pq.push({{nd, i}, w[i][j].right});
if(check(i, w[i][j].left, graph, dist)) pq.push({{nd, i}, w[i][j].left});
}
return dist[e.first][e.second];
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//ifstream cin ("input.in");
//ofstream cout ("output.out");
cin>>n>>m;
m += 2;
vector<string>graph;
string border;
for(int i = 0; i<m; ++i) border += '#';
graph.push_back(border);
for(int i = 0; i<n; ++i){
string s; cin>>s;
graph.push_back("#");
for(auto u: s) graph[i+1] += u;
graph[i+1] += '#';
}
graph.push_back(border);
/*
for(auto u: graph){
for(auto v: u) cout<<v;
cout<<endl;
}
cout<<endl;
*/
n += 2;
vector<vector<wall>>w(n, vector<wall>(m));
pair<int, int>s, e;
vector<pair<int, int>>start;
for(int i = 0; i<n; ++i){
int cur = 0;
for(int j = 0; j<m; ++j){
if(graph[i][j] == 'S') s = {i, j};
if(graph[i][j] == 'C') e = {i, j};
if(graph[i][j] == '#'){
cur = j;
start.push_back({i, j});
}
w[i][j].left = cur+1;
}
cur = m-1;
for(int j = m-1; j>=0; --j){
if(graph[i][j] == '#') cur = j;
w[i][j].right = cur-1;
}
}
for(int j = 0; j<m; ++j){
int cur = 0;
for(int i = 0; i<n; ++i){
if(graph[i][j] == '#') cur = i;
w[i][j].up = cur+1;
}
cur = n-1;
for(int i = n-1; i>=0; --i){
if(graph[i][j] == '#') cur = i;
w[i][j].down = cur-1;
}
}
vector<vector<int>>next = bfs(graph, start);
/*
for(auto u: next){
for(auto v: u) cout<<v<<" ";
cout<<endl;
}
cout<<endl;
*/
cout<<dijkstra(next, w, graph, s, e);
cout<<'\n';
}
Compilation message
portals.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
6 | #pragma GCC optimization ("O3")
|
portals.cpp:7: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
7 | #pragma GCC optimization ("unroll-loops")
|
portals.cpp:16:25: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
16 | int check(int i, int j, auto&graph, auto&dist){
| ^~~~
portals.cpp:16:37: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
16 | int check(int i, int j, auto&graph, auto&dist){
| ^~~~
portals.cpp:21:24: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
21 | vector<vector<int>>bfs(auto&graph, auto&start){
| ^~~~
portals.cpp:21:36: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
21 | vector<vector<int>>bfs(auto&graph, auto&start){
| ^~~~
portals.cpp: In function 'std::vector<std::vector<int> > bfs(auto:3&, auto:4&)':
portals.cpp:24:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
24 | for(auto [x, y]: start){
| ^
portals.cpp:34:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
34 | for(auto [x, y]: delta){
| ^
portals.cpp: At global scope:
portals.cpp:45:14: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
45 | int dijkstra(auto&next, auto&w, auto&graph, pair<int, int>s, pair<int, int>e){
| ^~~~
portals.cpp:45:25: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
45 | int dijkstra(auto&next, auto&w, auto&graph, pair<int, int>s, pair<int, int>e){
| ^~~~
portals.cpp:45:33: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
45 | int dijkstra(auto&next, auto&w, auto&graph, pair<int, int>s, pair<int, int>e){
| ^~~~
portals.cpp: In function 'int dijkstra(auto:5&, auto:6&, auto:7&, std::pair<int, int>, std::pair<int, int>)':
portals.cpp:61:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
61 | for(auto [x, y]: delta){
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
320 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
320 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
324 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
324 KB |
Output is correct |
10 |
Correct |
1 ms |
320 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
328 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
3 ms |
468 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
320 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
320 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
8 ms |
1488 KB |
Output is correct |
6 |
Correct |
11 ms |
1488 KB |
Output is correct |
7 |
Correct |
12 ms |
1532 KB |
Output is correct |
8 |
Correct |
5 ms |
1492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
324 KB |
Output is correct |
9 |
Correct |
1 ms |
320 KB |
Output is correct |
10 |
Correct |
3 ms |
468 KB |
Output is correct |
11 |
Correct |
1 ms |
324 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
8 ms |
1488 KB |
Output is correct |
15 |
Correct |
10 ms |
1488 KB |
Output is correct |
16 |
Correct |
12 ms |
1492 KB |
Output is correct |
17 |
Correct |
13 ms |
1492 KB |
Output is correct |
18 |
Correct |
20 ms |
1576 KB |
Output is correct |
19 |
Correct |
24 ms |
1592 KB |
Output is correct |
20 |
Correct |
34 ms |
3020 KB |
Output is correct |
21 |
Correct |
8 ms |
1488 KB |
Output is correct |
22 |
Correct |
9 ms |
1488 KB |
Output is correct |
23 |
Correct |
10 ms |
1492 KB |
Output is correct |
24 |
Correct |
17 ms |
1448 KB |
Output is correct |
25 |
Correct |
1 ms |
320 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
27 |
Correct |
1 ms |
324 KB |
Output is correct |
28 |
Correct |
4 ms |
1492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
2 ms |
340 KB |
Output is correct |
10 |
Correct |
2 ms |
468 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
324 KB |
Output is correct |
14 |
Correct |
8 ms |
1488 KB |
Output is correct |
15 |
Correct |
11 ms |
1488 KB |
Output is correct |
16 |
Correct |
12 ms |
1492 KB |
Output is correct |
17 |
Correct |
12 ms |
1492 KB |
Output is correct |
18 |
Correct |
17 ms |
1528 KB |
Output is correct |
19 |
Correct |
20 ms |
1492 KB |
Output is correct |
20 |
Correct |
34 ms |
3152 KB |
Output is correct |
21 |
Correct |
9 ms |
1540 KB |
Output is correct |
22 |
Correct |
11 ms |
1488 KB |
Output is correct |
23 |
Correct |
11 ms |
1492 KB |
Output is correct |
24 |
Correct |
363 ms |
29700 KB |
Output is correct |
25 |
Correct |
570 ms |
27492 KB |
Output is correct |
26 |
Correct |
777 ms |
33240 KB |
Output is correct |
27 |
Execution timed out |
1095 ms |
51656 KB |
Time limit exceeded |
28 |
Halted |
0 ms |
0 KB |
- |