oj.uz

Submission #941010

# Submission time Handle Problem Language Result Execution time Memory
941010 2024-03-08T05:05:01 Z Sir_Ahmed_Imran Portals (BOI14_portals) C++17
70 / 100
 370 ms 64220 KB 
                              ///~~~LOTA~~~///
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define append push_back
#define add insert
#define nl "\n"
#define ff first
#define ss second
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define L0TA ios_base::sync_with_stdio(false);cin.tie(NULL)
#define N 1004
char a[N][N];
pii UP[N][N];
pii DOWN[N][N];
pii LEFT[N][N];
pii RIGHT[N][N];
int dist[N][N];
bool vis[N][N];
vector<pii> mov{{-1,0},{0,-1},{0,1},{1,0}};
void solve(){
    pii pi;
    vector<pii> v,u;
    int n,m,p,q,r,x,y;
    cin>>n>>m;
    for(int i=0;i<n+4;i++){
        v.append({i,1});
        v.append({i,m+2});
        a[i][1]=a[i][m+2]='#';
        vis[i][1]=vis[i][m+2]=1;
    }
    for(int i=0;i<m+4;i++){
        v.append({1,i});
        v.append({n+2,i});
        a[1][i]=a[n+2][i]='#';
        vis[1][i]=vis[n+2][i]=1;
    }
    for(int i=2;i<n+2;i++){
        for(int j=2;j<m+2;j++){
            cin>>a[i][j];
            if(a[i][j]=='#'){
                vis[i][j]=1;
                v.append({i,j});
            }
            else dist[i][j]=1e9;
            if(a[i][j]=='S'){
                p=i;
                q=j;
            }
            if(a[i][j]=='C'){
                x=i;
                y=j;
            }
        }
    }
    for(int i=0;i<n*m;i++){
        if(v.empty()) break;
        for(auto& j:v){
            dist[j.ff][j.ss]=i;
            for(auto k:mov){
                pi=j;
                pi.ff+=k.ff;
                pi.ss+=k.ss;
                if(dist[pi.ff][pi.ss]>i+1){
                    dist[pi.ff][pi.ss]=i+1;
                    u.append(pi);
                }
            }
        }
        swap(v,u);
        u.clear();
    }
    for(int i=2;i<n+2;i++){
        for(int j=2;j<m+2;j++){
            UP[i][j]=UP[i-1][j];
            if(a[i-1][j]=='#')
                UP[i][j]={i,j};
            LEFT[i][j]=LEFT[i][j-1];
            if(a[i][j-1]=='#')
                LEFT[i][j]={i,j};
        }
    }
    for(int i=n+1;i>1;i--){
        for(int j=m+1;j>1;j--){
            DOWN[i][j]=DOWN[i+1][j];
            if(a[i+1][j]=='#')
                DOWN[i][j]={i,j};
            RIGHT[i][j]=RIGHT[i][j+1];
            if(a[i][j+1]=='#')
                RIGHT[i][j]={i,j};
        }
    }
    pi={x,y};
    priority_queue<pair<int,pii>,vector<pair<int,pii>>,greater<pair<int,pii>>> Q; 
    Q.push({0,{p,q}});
    while(Q.top().ss!=pi){
        p=Q.top().ss.ff;
        q=Q.top().ss.ss;
        r=Q.top().ff;
        Q.pop();
        if(!vis[p][q]){
            vis[p][q]=1;
            for(auto& i:mov){
                if(!vis[p+i.ff][q+i.ss])
                    Q.push({r+1,{p+i.ff,q+i.ss}});
            }
            if(!vis[UP[p][q].ff][UP[p][q].ss])
                    Q.push({r+dist[p][q],{UP[p][q].ff,UP[p][q].ss}});
            if(!vis[LEFT[p][q].ff][LEFT[p][q].ss])
                    Q.push({r+dist[p][q],{LEFT[p][q].ff,LEFT[p][q].ss}});
            if(!vis[DOWN[p][q].ff][DOWN[p][q].ss])
                    Q.push({r+dist[p][q],{DOWN[p][q].ff,DOWN[p][q].ss}});
            if(!vis[RIGHT[p][q].ff][RIGHT[p][q].ss])
                    Q.push({r+dist[p][q],{RIGHT[p][q].ff,RIGHT[p][q].ss}});
        }
    }
    cout<<Q.top().ff;
}
int main(){
    solve();
    return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4440 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 1 ms 4700 KB Output is correct
8 Correct 1 ms 4700 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4440 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 1 ms 4696 KB Output is correct
8 Correct 1 ms 4700 KB Output is correct
9 Correct 2 ms 7516 KB Output is correct
10 Correct 2 ms 7516 KB Output is correct
11 Correct 2 ms 7516 KB Output is correct
12 Correct 2 ms 7516 KB Output is correct
13 Correct 2 ms 7516 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 2 ms 7516 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4696 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 8 ms 11864 KB Output is correct
6 Correct 10 ms 11864 KB Output is correct
7 Correct 9 ms 11736 KB Output is correct
8 Correct 6 ms 11736 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4696 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 1 ms 4700 KB Output is correct
8 Correct 1 ms 4700 KB Output is correct
9 Correct 2 ms 7516 KB Output is correct
10 Correct 3 ms 7516 KB Output is correct
11 Correct 2 ms 7512 KB Output is correct
12 Correct 2 ms 7516 KB Output is correct
13 Correct 2 ms 7516 KB Output is correct
14 Correct 9 ms 11612 KB Output is correct
15 Correct 11 ms 11844 KB Output is correct
16 Correct 9 ms 11736 KB Output is correct
17 Correct 11 ms 11760 KB Output is correct
18 Correct 14 ms 11736 KB Output is correct
19 Correct 5 ms 11356 KB Output is correct
20 Correct 14 ms 13012 KB Output is correct
21 Correct 8 ms 11864 KB Output is correct
22 Correct 9 ms 11632 KB Output is correct
23 Correct 10 ms 11852 KB Output is correct
24 Correct 13 ms 11352 KB Output is correct
25 Correct 1 ms 4440 KB Output is correct
26 Correct 2 ms 7260 KB Output is correct
27 Correct 1 ms 4444 KB Output is correct
28 Correct 6 ms 11736 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 1 ms 4700 KB Output is correct
8 Correct 1 ms 4700 KB Output is correct
9 Correct 2 ms 7508 KB Output is correct
10 Correct 2 ms 7516 KB Output is correct
11 Correct 2 ms 7516 KB Output is correct
12 Correct 2 ms 7516 KB Output is correct
13 Correct 2 ms 7516 KB Output is correct
14 Correct 10 ms 11612 KB Output is correct
15 Correct 10 ms 11724 KB Output is correct
16 Correct 11 ms 11736 KB Output is correct
17 Correct 12 ms 11732 KB Output is correct
18 Correct 14 ms 11736 KB Output is correct
19 Correct 5 ms 11356 KB Output is correct
20 Correct 15 ms 13272 KB Output is correct
21 Correct 8 ms 11860 KB Output is correct
22 Correct 9 ms 11608 KB Output is correct
23 Correct 12 ms 11736 KB Output is correct
24 Correct 310 ms 45668 KB Output is correct
25 Correct 370 ms 38960 KB Output is correct
26 Correct 83 ms 45076 KB Output is correct
27 Correct 267 ms 64220 KB Output is correct
28 Runtime error 76 ms 37436 KB Execution killed with signal 11
29 Halted 0 ms 0 KB -