oj.uz

Submission #896057

# Submission time Handle Problem Language Result Execution time Memory
896057 2023-12-31T15:02:48 Z niter Maze (JOI23_ho_t3) C++14
0 / 100
 2000 ms 34900 KB 
#include <bits/stdc++.h>
#define loop(i,a,b) for(int i = (a); i < (b); i ++)
#define pb push_back
#define ins insert
#define pii pair<int,int>
#define ff first
#define ss second
#define BAE(x) (x).begin(), (x).end()
#define op(x) cerr << #x << " = " << x << endl;
#define opa(x) cerr << #x << " = " << x << ", ";
#define spac cerr << ' ';
#define entr cerr << endl;
#define STL(x) cerr << #x << " : "; for(auto &qwe:x) cerr << qwe << ' '; cerr << endl;
#define ARR(x, nnn) cerr << #x << " : "; loop(qwe,0,nnn) cerr << x[qwe] << ' '; cerr << endl;
using namespace std;
mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count());
ostream& operator<<(ostream& os, pii A){ os << "\n[" << A.ff << ", " << A.ss << "]"; }
 
inline bool check(int i, int j, int n, int m){
    return i >= 0 && j >= 0 && i < n && j < m;
}
const int INF = (int)(1e9);
const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};
vector<pii> dr;
vector<vector<char>> c;
vector<vector<int>> dis;
vector<vector<bool>> special;
 
int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    int n, m, L;
    cin >> n >> m >> L;
    pii s, t;
    cin >> s.ff >> s.ss >> t.ff >> t.ss;
    s.ff--; s.ss--; t.ff--; t.ss--;
    c = vector<vector<char>>(n, vector<char>(m, ' '));
    loop(i,0,n){
        loop(j,0,m){
            cin >> c[i][j];
        }
    }
    for(int i = -1; i <= 1; i += 2){
        for(int j = -1; j <= 1; j += 2){
            for(int k = 0; k < L; k ++){
                dr.pb({k * i, L * j});
                dr.pb({L * j, k * i});
            }
        }
    }
    sort(BAE(dr));
    dr.resize(unique(BAE(dr)) - dr.begin());
//    STL(dr);
    special = vector<vector<bool>>(n, vector<bool>(m, false));
    for(auto &i:dr){
        int nx = s.ff + i.ff;
        int ny = s.ss + i.ss;
        if(check(nx, ny, n, m)){
            special[nx][ny] = true;
        }
    }
    dis = vector<vector<int>>(n, vector<int>(m, INF));
    dis[s.ff][s.ss] = 0;
    queue<pii> Q;
    Q.push(s);
    while(!Q.empty()){
        int nowx = Q.front().ff;
        int nowy = Q.front().ss;
        Q.pop();
        if(special[nowx][nowy]) continue;
        loop(d,0,4){
            int nx = nowx + dx[d];
            int ny = nowy + dy[d];
            if(!check(nx, ny, n, m)) continue;
            if(dis[nx][ny] == INF){
                dis[nx][ny] = 1;
                Q.push({nx, ny});
            }
        }
    }
//    for(auto &i:dis){
//        STL(i) entr
//    }
    priority_queue<pair<int,pii>, vector<pair<int,pii>>, greater<pair<int,pii>>> pq;
    loop(i,0,n){
        loop(j,0,m){
            if(dis[i][j] != INF) pq.push({dis[i][j], {i, j}});
        }
    }
//    pq.push({0, s});
    while(!pq.empty()){
        int nowx = pq.top().ss.ff;
        int nowy = pq.top().ss.ss;
        int nowd = pq.top().ff;
        pq.pop();
        if(nowd != dis[nowx][nowy]) continue;
      	if(nowd >= 10) continue;
        loop(d,0,4){
            int nx = nowx + dx[d];
            int ny = nowy + dy[d];
            if(!check(nx, ny, n, m)) continue;
            if(c[nx][ny] == '#') continue;
            if(dis[nx][ny] > nowd){
                dis[nx][ny] = nowd;
                pq.push({dis[nx][ny], {nx, ny}});
            }
        }
        for(auto &d:dr){
            int nx = nowx + d.ff;
            int ny = nowy + d.ss;
            if(!check(nx, ny, n, m)) continue;
            if(dis[nx][ny] > nowd + 1){
                dis[nx][ny] = nowd + 1;
                pq.push({dis[nx][ny], {nx, ny}});
            }
        }
    }
    assert(dis[t.ff][t.ss] != INF);
    cout << dis[t.ff][t.ss] << '\n';
}
/*
5 5 2
1 1
4 4
.####
#####
#####
###.#
#####
*/

Compilation message

Main.cpp: In function 'std::ostream& operator<<(std::ostream&, std::pair<int, int>)':
Main.cpp:17:86: warning: no return statement in function returning non-void [-Wreturn-type]
   17 | ostream& operator<<(ostream& os, pii A){ os << "\n[" << A.ff << ", " << A.ss << "]"; }
      |                                                                                      ^

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Runtime error 1 ms 604 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 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 Runtime error 1 ms 460 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 2 ms 600 KB Output is correct
26 Correct 19 ms 1628 KB Output is correct
27 Correct 7 ms 860 KB Output is correct
28 Correct 133 ms 1624 KB Output is correct
29 Correct 121 ms 1880 KB Output is correct
30 Correct 124 ms 1748 KB Output is correct
31 Correct 31 ms 1020 KB Output is correct
32 Correct 11 ms 860 KB Output is correct
33 Correct 3 ms 940 KB Output is correct
34 Correct 134 ms 2864 KB Output is correct
35 Correct 18 ms 1444 KB Output is correct
36 Correct 498 ms 5496 KB Output is correct
37 Correct 493 ms 5960 KB Output is correct
38 Correct 475 ms 4560 KB Output is correct
39 Correct 316 ms 10596 KB Output is correct
40 Correct 1518 ms 34012 KB Output is correct
41 Correct 217 ms 9892 KB Output is correct
42 Execution timed out 2013 ms 34900 KB Time limit exceeded
43 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 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 Runtime error 1 ms 460 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 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 Runtime error 1 ms 460 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Runtime error 1 ms 604 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #7
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Runtime error 1 ms 604 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Runtime error 1 ms 604 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -