oj.uz

Submission #948619

# Submission time Handle Problem Language Result Execution time Memory
948619 2024-03-18T08:55:22 Z Darren0724 Portals (BOI14_portals) C++17
70 / 100
 43 ms 30744 KB 
#include <bits/stdc++.h>
using namespace std;
#define LCBorz ios_base::sync_with_stdio(false); cin.tie(0);
//#define int long long
#define all(x) x.begin(), x.end()
#define endl '\n'
const int N=505;
const int INF=1e9;
 
int32_t main() {
    LCBorz;
    int n,m;cin>>n>>m;
    vector<vector<char>> v(n+2,vector<char>(m+2,'#'));
    auto id=[&](int a,int b){
        return a*N+b;
    };
    auto valid=[&](int a,int b){
        return v[a][b]!='#';
    };
    auto rev=[&](int id){
        return make_pair(id/N,id%N);
    };
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>v[i][j];
        }
    }
    vector<int> adj[N*N];
    for(int i=1;i<=n;i++){
        int last=0;
        for(int j=1;j<=m;j++){
            if(!valid(i,j)){
                last=j;
                continue;
            }
            adj[id(i,j)].push_back(id(i,last+1));
        }
        last=m+1;
        for(int j=m;j>=1;j--){
            if(!valid(i,j)){
                last=j;
                continue;
            }
            adj[id(i,j)].push_back(id(i,last-1));
        }
    }
    for(int i=1;i<=m;i++){
        int last=0;
        for(int j=1;j<=n;j++){
            if(!valid(j,i)){
                last=j;
                continue;
            }
            adj[id(j,i)].push_back(id(last+1,i));
        }
        last=n+1;
        for(int j=n;j>=1;j--){
            if(!valid(j,i)){
                last=j;
                continue;
            }
            adj[id(j,i)].push_back(id(last-1,i));
        }
    }
    vector<int> dx={0,0,-1,1},dy={1,-1,0,0};
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(!valid(i,j))continue;
            for(int k=0;k<4;k++){
                int a=i+dx[k],b=j+dy[k];
                if(!valid(a,b))continue;
                adj[id(i,j)].push_back(id(a,b));
            }
        }
    }
    queue<int> q;
    vector<int> dis(N*N,INF);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(v[i][j-1]=='#'||v[i][j+1]=='#'||v[i-1][j]=='#'||v[i+1][j]=='#'){
                q.push(id(i,j));
                dis[id(i,j)]=0;
            }
        }
    }
    while(q.size()){
        int p=q.front();
        q.pop();
        for(int j:adj[p]){
            if(dis[j]==INF){
                dis[j]=dis[p]+1;
                q.push(j);
            }
        }
    }
    priority_queue<pair<int,int>> pq;
    vector dis1(N*N,INF);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(v[i][j]=='S'){
                dis1[id(i,j)]=0;
                pq.push({0,id(i,j)});
            }
        }
    }
    while(pq.size()){
        auto [dis2,t]=pq.top();
        pq.pop();
        dis2=-dis2;
        if(dis2!=dis1[t])continue;
        for(int j:adj[t]){
            int cost=dis1[t];
            if(abs(j-t)==N||abs(j-t)==1)cost+=1;
            else cost+=dis[t]+1;
            if(dis1[j]>cost){
                dis1[j]=cost;
                pq.push({-dis1[j],j});
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(v[i][j]=='C'){
                cout<<dis1[id(i,j)]<<endl;
            }
        }
    }
    
 
    
    return 0;
}

Compilation message

portals.cpp: In function 'int32_t main()':
portals.cpp:20:10: warning: variable 'rev' set but not used [-Wunused-but-set-variable]
   20 |     auto rev=[&](int id){
      |          ^~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8284 KB Output is correct
2 Correct 5 ms 8284 KB Output is correct
3 Correct 5 ms 8284 KB Output is correct
4 Correct 7 ms 8280 KB Output is correct
5 Correct 5 ms 8232 KB Output is correct
6 Correct 5 ms 8284 KB Output is correct
7 Correct 5 ms 8284 KB Output is correct
8 Correct 5 ms 8284 KB Output is correct
9 Correct 5 ms 8284 KB Output is correct
10 Correct 4 ms 8236 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8284 KB Output is correct
2 Correct 4 ms 8284 KB Output is correct
3 Correct 5 ms 8284 KB Output is correct
4 Correct 4 ms 8284 KB Output is correct
5 Correct 4 ms 8284 KB Output is correct
6 Correct 4 ms 8284 KB Output is correct
7 Correct 5 ms 8284 KB Output is correct
8 Correct 7 ms 8240 KB Output is correct
9 Correct 8 ms 8540 KB Output is correct
10 Correct 6 ms 8540 KB Output is correct
11 Correct 5 ms 8416 KB Output is correct
12 Correct 7 ms 8540 KB Output is correct
13 Correct 7 ms 8324 KB Output is correct
14 Correct 5 ms 8280 KB Output is correct
15 Correct 5 ms 8540 KB Output is correct
16 Correct 5 ms 8284 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8284 KB Output is correct
2 Correct 6 ms 8228 KB Output is correct
3 Correct 4 ms 8284 KB Output is correct
4 Correct 5 ms 8340 KB Output is correct
5 Correct 18 ms 9560 KB Output is correct
6 Correct 14 ms 9820 KB Output is correct
7 Correct 15 ms 9820 KB Output is correct
8 Correct 15 ms 9820 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8284 KB Output is correct
2 Correct 4 ms 8284 KB Output is correct
3 Correct 5 ms 8284 KB Output is correct
4 Correct 5 ms 8284 KB Output is correct
5 Correct 5 ms 8284 KB Output is correct
6 Correct 5 ms 8284 KB Output is correct
7 Correct 5 ms 8284 KB Output is correct
8 Correct 5 ms 8284 KB Output is correct
9 Correct 6 ms 8568 KB Output is correct
10 Correct 5 ms 8400 KB Output is correct
11 Correct 6 ms 8540 KB Output is correct
12 Correct 5 ms 8536 KB Output is correct
13 Correct 6 ms 8540 KB Output is correct
14 Correct 14 ms 9812 KB Output is correct
15 Correct 14 ms 9816 KB Output is correct
16 Correct 16 ms 9816 KB Output is correct
17 Correct 14 ms 9816 KB Output is correct
18 Correct 22 ms 10128 KB Output is correct
19 Correct 18 ms 10332 KB Output is correct
20 Correct 18 ms 10348 KB Output is correct
21 Correct 15 ms 9828 KB Output is correct
22 Correct 14 ms 9820 KB Output is correct
23 Correct 15 ms 9816 KB Output is correct
24 Correct 17 ms 10188 KB Output is correct
25 Correct 5 ms 8316 KB Output is correct
26 Correct 5 ms 8484 KB Output is correct
27 Correct 6 ms 8236 KB Output is correct
28 Correct 10 ms 9820 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8284 KB Output is correct
2 Correct 5 ms 8284 KB Output is correct
3 Correct 6 ms 8280 KB Output is correct
4 Correct 6 ms 8284 KB Output is correct
5 Correct 6 ms 8284 KB Output is correct
6 Correct 5 ms 8368 KB Output is correct
7 Correct 6 ms 8284 KB Output is correct
8 Correct 6 ms 8284 KB Output is correct
9 Correct 6 ms 8540 KB Output is correct
10 Correct 6 ms 8540 KB Output is correct
11 Correct 5 ms 8536 KB Output is correct
12 Correct 6 ms 8540 KB Output is correct
13 Correct 6 ms 8484 KB Output is correct
14 Correct 13 ms 9660 KB Output is correct
15 Correct 15 ms 9780 KB Output is correct
16 Correct 15 ms 9904 KB Output is correct
17 Correct 15 ms 9820 KB Output is correct
18 Correct 17 ms 9952 KB Output is correct
19 Correct 23 ms 10372 KB Output is correct
20 Correct 16 ms 10436 KB Output is correct
21 Correct 14 ms 9820 KB Output is correct
22 Correct 14 ms 9820 KB Output is correct
23 Correct 14 ms 9820 KB Output is correct
24 Runtime error 43 ms 30744 KB Execution killed with signal 11
25 Halted 0 ms 0 KB -