oj.uz

답안 #748150

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
748150 2023-05-25T13:09:18 Z onebit1024 포탈들 (BOI14_portals) C++17
100 / 100
 690 ms 43932 KB 
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define all(c) c.begin(), c.end()
#define endl "\n"

const double PI=3.141592653589;


void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define dbg(x...) cerr << "LINE(" << __LINE__ << ") -> " <<"[" << #x << "] = ["; _print(x)
#else
#define dbg(x...)
#endif

int n,m;
const int N = 1005;
int a[N][N],dist[N][N],wall[N][N],dp[N][N][4];
vector<pair<int,int>>neigh(int i, int j){
    vector<pair<int,int>>res;
    if(i < n)res.pb({i+1,j});
    if(i > 1)res.pb({i-1,j});
    if(j < m)res.pb({i,j+1});
    if(j > 1)res.pb({i,j-1});
    return res;
}

void solve()
{
    cin >> n >> m;

    priority_queue<vector<int>,vector<vector<int>>,greater<vector<int>>>pq;
    int ex = 0, ey = 0;
    
    for(int i = 0;i<=n+1;++i){
        for(int j = 0;j<=m+1;++j){
            wall[i][j] = dist[i][j] = 1e9;
            a[i][j] = 1;
        }
    }
    for(int i = 1;i<=n;++i){
        for(int j = 1;j<=m;++j){
            char x;
            cin >> x;
            if(x=='.')a[i][j] = 0;
            else if(x=='C')ex = i,ey = j,a[i][j]=0;
            else if(x=='S')pq.push({0,i,j}),dist[i][j] = 0,a[i][j]=0;
        }
    }
    /*
    dp[i][j][0] -> right
    1 -> left
    2 -> up
    3 -> down
    */
    for(int i = 1;i<=n;++i){
        int prev = m+1;
        for(int j = m;j>=1;--j){
            if(a[i][j])prev = j;
            dp[i][j][0] = prev;
        }
        prev = 0;
        for(int j = 1;j<=m;++j){
            if(a[i][j])prev = j;
            dp[i][j][1] = prev;
        }
    }
    for(int j = 1;j<=m;++j){
        int prev = 0;
        for(int i = 1;i<=n;++i){
            if(a[i][j])prev = i;
            dp[i][j][2] = prev;
        }
        prev = n+1;
        for(int i = n;i>=1;--i){
            if(a[i][j])prev = i;
            dp[i][j][3] = prev;
        }
    }
    vector<vector<int>>vis(n+2, vector<int>(m+2)); // closest wall cell
    queue<pair<int,int>>q;
    for(int i = 0;i<=n+1;++i){
        for(int j = 0;j<=m+1;++j){
            if(a[i][j]){
                wall[i][j] = 0;
                q.push({i,j});
            }
        }
    }
    while(!q.empty()){
        int i = q.front().first, j = q.front().second;
        q.pop();
        if(vis[i][j])continue;
        vis[i][j] = 1;
        for(auto &[x,y] : neigh(i,j)){
            if(a[x][y])continue;
            wall[x][y] = min(wall[x][y],wall[i][j]+1);
            q.push({x,y});
        }
    }
    while(!pq.empty()){
        int d = pq.top()[0], i = pq.top()[1], j = pq.top()[2];
        pq.pop();

        if(dist[i][j]!=d)continue;
        for(auto &[x,y] : neigh(i,j)){
            if(a[x][y])continue;
            int curr_dist = dist[x][y], new_dist = dist[i][j]+1;
            if(new_dist < curr_dist){
                dist[x][y] = new_dist;
                pq.push({new_dist, x, y});
            }
        }
        int val = wall[i][j];
        for(auto w : {dp[i][j][0], dp[i][j][1]}){
            int y = w+1;
            if(w > j)y = w-1;
            int x = i;
            int curr_dist = dist[x][y], new_dist = dist[i][j]+val;
            if(new_dist < curr_dist){
                dist[x][y] = new_dist;
                pq.push({new_dist, x, y});
            }
        }
        for(auto w : {dp[i][j][2], dp[i][j][3]}){
            int x = w+1;
            if(w > i)x = w-1;

            int y = j;
            int curr_dist = dist[x][y], new_dist = dist[i][j]+val;
            if(new_dist < curr_dist){
                dist[x][y] = new_dist;
                pq.push({new_dist, x, y});
            }
        }
    }
    cout << dist[ex][ey];
}   

int32_t main()
{

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);


    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    

    int T=1;
    for(int i = 1;i<=T;++i)
    {
        // cout << "Case #" << i << ": ";
        solve();
    }
}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 0 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 2 ms 1236 KB Output is correct
10 Correct 2 ms 1236 KB Output is correct
11 Correct 1 ms 1236 KB Output is correct
12 Correct 2 ms 1236 KB Output is correct
13 Correct 2 ms 1236 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 1108 KB Output is correct
16 Correct 1 ms 340 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 15 ms 4692 KB Output is correct
6 Correct 15 ms 4692 KB Output is correct
7 Correct 17 ms 4776 KB Output is correct
8 Correct 12 ms 4692 KB Output is correct

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 2 ms 1236 KB Output is correct
10 Correct 2 ms 1236 KB Output is correct
11 Correct 1 ms 1236 KB Output is correct
12 Correct 1 ms 1236 KB Output is correct
13 Correct 2 ms 1236 KB Output is correct
14 Correct 14 ms 4704 KB Output is correct
15 Correct 15 ms 4692 KB Output is correct
16 Correct 17 ms 4772 KB Output is correct
17 Correct 15 ms 4652 KB Output is correct
18 Correct 20 ms 4648 KB Output is correct
19 Correct 21 ms 4356 KB Output is correct
20 Correct 18 ms 4348 KB Output is correct
21 Correct 14 ms 4728 KB Output is correct
22 Correct 15 ms 4716 KB Output is correct
23 Correct 16 ms 4752 KB Output is correct
24 Correct 17 ms 4356 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 2 ms 1108 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 11 ms 4692 KB Output is correct

Subtask #5
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 2 ms 1236 KB Output is correct
10 Correct 2 ms 1236 KB Output is correct
11 Correct 2 ms 1236 KB Output is correct
12 Correct 1 ms 1236 KB Output is correct
13 Correct 2 ms 1236 KB Output is correct
14 Correct 17 ms 4716 KB Output is correct
15 Correct 15 ms 4692 KB Output is correct
16 Correct 16 ms 4820 KB Output is correct
17 Correct 15 ms 4748 KB Output is correct
18 Correct 18 ms 4692 KB Output is correct
19 Correct 19 ms 4352 KB Output is correct
20 Correct 20 ms 4352 KB Output is correct
21 Correct 14 ms 4692 KB Output is correct
22 Correct 15 ms 4712 KB Output is correct
23 Correct 16 ms 4752 KB Output is correct
24 Correct 436 ms 42660 KB Output is correct
25 Correct 690 ms 33664 KB Output is correct
26 Correct 534 ms 33216 KB Output is correct
27 Correct 531 ms 33372 KB Output is correct
28 Correct 341 ms 42324 KB Output is correct
29 Correct 364 ms 42584 KB Output is correct
30 Correct 406 ms 42716 KB Output is correct
31 Correct 17 ms 4308 KB Output is correct
32 Correct 514 ms 32968 KB Output is correct
33 Correct 0 ms 340 KB Output is correct
34 Correct 1 ms 1236 KB Output is correct
35 Correct 418 ms 37076 KB Output is correct
36 Correct 1 ms 340 KB Output is correct
37 Correct 14 ms 4784 KB Output is correct
38 Correct 274 ms 43932 KB Output is correct
39 Correct 311 ms 41220 KB Output is correct