oj.uz

답안 #748149

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

#define int long long
#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;
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;
    vector<vector<int>>a(n+2, vector<int>(m+2,1)),dist(n+2, vector<int>(m+2,1e18)),left(n+1, vector<int>(m+1)),right(n+1, vector<int>(m+1)),up(n+1, vector<int>(m+1)),down(n+1, vector<int>(m+1));
    priority_queue<vector<int>,vector<vector<int>>,greater<vector<int>>>pq;
    int ex = 0, ey = 0;
    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] closest wall
    for(int i = 1;i<=n;++i){
        int prev = m+1;
        for(int j = m;j>=1;--j){
            if(a[i][j])prev = j;
            right[i][j] = prev;
        }
        prev = 0;
        for(int j = 1;j<=m;++j){
            if(a[i][j])prev = j;
            left[i][j] = prev;
        }
    }
    for(int j = 1;j<=m;++j){
        int prev = 0;
        for(int i = 1;i<=n;++i){
            if(a[i][j])prev = i;
            up[i][j] = prev;
        }
        prev = n+1;
        for(int i = n;i>=1;--i){
            if(a[i][j])prev = i;
            down[i][j] = prev;
        }
    }
    vector<vector<int>>wall(n+2, vector<int>(m+2, 1e18)),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();
        dbg(i,j,dist[i][j]);
        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 : {left[i][j],right[i][j]}){
            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 : {up[i][j],down[i][j]}){
            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 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 2 ms 324 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 324 KB Output is correct
7 Correct 2 ms 324 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 36 ms 636 KB Output is correct
10 Correct 37 ms 588 KB Output is correct
11 Correct 23 ms 604 KB Output is correct
12 Correct 26 ms 628 KB Output is correct
13 Correct 28 ms 764 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 29 ms 588 KB Output is correct
16 Correct 1 ms 212 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 328 KB Output is correct
5 Correct 328 ms 4912 KB Output is correct
6 Correct 358 ms 4852 KB Output is correct
7 Correct 375 ms 5092 KB Output is correct
8 Correct 398 ms 5212 KB Output is correct

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 38 ms 632 KB Output is correct
10 Correct 37 ms 600 KB Output is correct
11 Correct 21 ms 608 KB Output is correct
12 Correct 25 ms 612 KB Output is correct
13 Correct 25 ms 616 KB Output is correct
14 Correct 339 ms 4812 KB Output is correct
15 Correct 367 ms 4848 KB Output is correct
16 Correct 378 ms 5032 KB Output is correct
17 Correct 381 ms 4940 KB Output is correct
18 Correct 474 ms 5220 KB Output is correct
19 Correct 580 ms 4864 KB Output is correct
20 Correct 573 ms 4848 KB Output is correct
21 Correct 336 ms 4768 KB Output is correct
22 Correct 328 ms 4764 KB Output is correct
23 Correct 372 ms 4904 KB Output is correct
24 Correct 590 ms 4812 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 34 ms 584 KB Output is correct
27 Correct 1 ms 212 KB Output is correct
28 Correct 387 ms 5068 KB Output is correct

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 320 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 324 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 2 ms 320 KB Output is correct
9 Correct 36 ms 724 KB Output is correct
10 Correct 34 ms 608 KB Output is correct
11 Correct 21 ms 588 KB Output is correct
12 Correct 23 ms 596 KB Output is correct
13 Correct 25 ms 612 KB Output is correct
14 Correct 336 ms 4960 KB Output is correct
15 Correct 350 ms 4888 KB Output is correct
16 Correct 382 ms 5080 KB Output is correct
17 Correct 377 ms 5084 KB Output is correct
18 Correct 455 ms 5268 KB Output is correct
19 Correct 563 ms 4932 KB Output is correct
20 Correct 563 ms 4956 KB Output is correct
21 Correct 331 ms 4928 KB Output is correct
22 Correct 378 ms 5012 KB Output is correct
23 Correct 351 ms 4968 KB Output is correct
24 Execution timed out 1095 ms 89192 KB Time limit exceeded
25 Halted 0 ms 0 KB -