oj.uz

Submission #1095717

# Submission time Handle Problem Language Result Execution time Memory
1095717 2024-10-03T03:33:01 Z SoMotThanhXuan Portals (BOI14_portals) C++17
20 / 100
 19 ms 27872 KB 
#include <bits/stdc++.h>
using namespace std;

int R, C;
const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};
const int maxN = 1e3 + 2;
char a[1001][1001];
int val[1001][1001];
vector<int> adj[1000001];
int rem[1002];
int f[1000001];
bool isValid(int i, int j){
    return i >= 1 && i <= R && j >= 1 && j <= C && a[i][j] != '#';
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> R >> C;
    int cnt = 0;
    for(int i = 1; i <= R; ++i){
        for(int j = 1; j <= C; ++j){
            cin >> a[i][j];
            val[i][j] = ++cnt;
        }
    }
    for(int j = 1; j <= C; ++j){
        for(int i = 1; i <= R; ++i){
            if(a[i][j] == '#'){
                rem[i] = i;
                continue;
            }
            rem[i] = rem[i - 1];
            int s = val[i][j], e = val[rem[i] + 1][j];
            if(s != e)adj[s].push_back(e);
        }
        rem[R + 1] = R + 1;
        for(int i = R; i >= 1; --i){
            if(a[i][j] == '#'){
                rem[i] = i;
                continue;
            }
            rem[i] = rem[i + 1];
            int s = val[i][j], e = val[rem[i] - 1][j];
            if(s != e)adj[s].push_back(e);
        }
    }
    for(int i = 1; i <= R; ++i){
        for(int j = 1; j <= C; ++j){
            if(a[i][j] == '#'){
                rem[j] = j;
                continue;
            }
            rem[j] = rem[j - 1];
            int s = val[i][j], e = val[i][rem[j] + 1];
            if(s != e)adj[s].push_back(e);
        }
        rem[C + 1] = C + 1;
        for(int j = C; j >= 1; --j){
            if(a[i][j] == '#'){
                rem[j] = j;
                continue;
            }
            rem[j] = rem[j + 1];
            int s = val[i][j], e = val[i][rem[j] - 1];
            if(s != e)adj[s].push_back(e);
        }
    }

    for(int i = 1; i <= R; ++i){
        for(int j = 1; j <= C; ++j){
            if(a[i][j] == '#')continue;
            for(int k = 0; k < 4; ++k){
                int ni = i + dx[k];
                int nj = j + dy[k];
                if(isValid(ni, nj))adj[val[i][j]].push_back(val[ni][nj]);
            }
        }
    }
    const int INF = 1e9 + 9;
    int s, e;
    for(int i = 1; i <= R; ++i)for(int j = 1; j <= C; ++j)if(a[i][j] == 'S')s = val[i][j]; else if(a[i][j] == 'C') e = val[i][j];
    for(int i = 1; i <= cnt; ++i)f[i] = INF;
    f[s] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> Q;
    Q.push({0, s});
    while(!Q.empty()){
        int p = Q.top().second;
        int dis = Q.top().first;
        Q.pop();
        if(dis > f[p])continue;
        for(int v: adj[p]){
            if(f[v] > f[p] + 1){
                f[v] = f[p] + 1;
                Q.push({f[v], v});
            }
        }
    }
    cout << f[e];
    return 0;
}

Compilation message

portals.cpp: In function 'int main()':
portals.cpp:98:16: warning: 'e' may be used uninitialized in this function [-Wmaybe-uninitialized]
   98 |     cout << f[e];
      |                ^

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 25432 KB Output is correct
2 Correct 9 ms 25692 KB Output is correct
3 Correct 9 ms 25688 KB Output is correct
4 Correct 9 ms 25436 KB Output is correct
5 Correct 11 ms 25692 KB Output is correct
6 Incorrect 9 ms 25684 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 25436 KB Output is correct
2 Correct 10 ms 25692 KB Output is correct
3 Correct 9 ms 25624 KB Output is correct
4 Correct 11 ms 25436 KB Output is correct
5 Correct 12 ms 25512 KB Output is correct
6 Incorrect 10 ms 25692 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 25688 KB Output is correct
2 Correct 10 ms 25688 KB Output is correct
3 Correct 10 ms 25692 KB Output is correct
4 Correct 11 ms 25700 KB Output is correct
5 Correct 16 ms 27468 KB Output is correct
6 Correct 16 ms 27740 KB Output is correct
7 Correct 19 ms 27872 KB Output is correct
8 Correct 16 ms 27736 KB Output is correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 25436 KB Output is correct
2 Correct 10 ms 25692 KB Output is correct
3 Correct 10 ms 25436 KB Output is correct
4 Correct 10 ms 25532 KB Output is correct
5 Correct 9 ms 25688 KB Output is correct
6 Incorrect 10 ms 25688 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 25432 KB Output is correct
2 Correct 11 ms 25640 KB Output is correct
3 Correct 10 ms 25692 KB Output is correct
4 Correct 10 ms 25436 KB Output is correct
5 Correct 10 ms 25692 KB Output is correct
6 Incorrect 10 ms 25500 KB Output isn't correct
7 Halted 0 ms 0 KB -