Submission #1176223

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176223		ThommyDB	Portals (BOI14_portals)	C++20	0 / 100	0 ms	400 KiB

portals

#include<bits/stdc++.h>

using namespace std;

int r, c;
vector<vector<char>> grid;
vector<vector<pair<pair<int, int>, pair<int, int>>>> teleport;

signed main(){
    cin >> r >> c;
    grid.resize(r, vector<char>(c));
    teleport.resize(r, vector<pair<pair<int, int>, pair<int, int>>>(c, {{-1, -1}, {-1, -1}}));
    priority_queue<pair<int, pair<int, int>>> q;
    pair<int, int> cakePos;
    for(int i = 0; i < r; i++){
        for(int j = 0; j < c; j++){
            cin >> grid[i][j];
            if(grid[i][j] != '#' && i==0)teleport[i][j].second.first=0;
            if(grid[i][j] != '#' && j==0)teleport[i][j].first.first=0;
            if(grid[i][j] != '#' && i!=0) teleport[i][j].second.first=teleport[i-1][j].second.first+1;
            if(grid[i][j] != '#' && j!=0) teleport[i][j].first.first=teleport[i][j-1].first.first+1;

            if(grid[i][j]=='S') q.push({0, {i, j}});
            if(grid[i][j]=='C') cakePos = {i, j};
        }
    }
    for(int i = r-2; i >= 0; i--){
        for(int j = c-2; j >= 0; j--){
            if(grid[i][j] != '#' && i==r-1)teleport[i][j].second.second=0;
            if(grid[i][j] != '#' && j==c-1)teleport[i][j].first.second=0;
            if(grid[i][j] != '#')teleport[i][j].second.second=teleport[i+1][j].second.second+1;
            if(grid[i][j] != '#')teleport[i][j].first.second=teleport[i][j+1].first.second+1;
        }
    }

    vector<vector<int>> dist(r, vector<int>(c, INT_MAX));
    dist[q.top().second.first][q.top().second.second]=0;
    vector<vector<bool>> visited(r, vector<bool>(c));
    vector<pair<int, int>> dir = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    while(!q.empty()){
        int d = -q.top().first; int i = q.top().second.first; int j = q.top().second.second; q.pop();
        //cout << "d: " << d << "\n";
        //cout << "i: " << i << "\n";
        //cout << "j: " << j << "\n";
        if(visited[i][j]) continue;
        visited[i][j]=true;
        /*if(i==0 && j==2){
            cout << teleport[i][j].first.first << " & " << teleport[i][j].first.second << " & " << teleport[i][j].second.first << " & " << teleport[i][j].second.second << "\n";
        }*/
        for(auto u : dir){
            if(i+u.first <0 || j+u.second<0 ||i+u.first>r-1 || j+u.second>c-1) continue;
            if(grid[i+u.first][j+u.second]!='#'){
                if(dist[i+u.first][j+u.second]>d+1){
                    dist[i+u.first][j+u.second]=d+1;
                    q.push({-d-1, {i+u.first, j+u.second}});
                }
            }
        }
        int mn = INT_MAX;
        if(teleport[i][j].first.first!=-1)mn = min(mn, teleport[i][j].first.first);
        if(teleport[i][j].first.second!=-1)mn = min(mn, teleport[i][j].first.second);
        if(teleport[i][j].second.first!=-1)mn = min(mn, teleport[i][j].second.first);
        if(teleport[i][j].second.second!=-1)mn= min(mn, teleport[i][j].second.second);
        if(teleport[i][j].second.first>0){
            if(dist[i-teleport[i][j].second.first][j]>d+mn){
                dist[i-teleport[i][j].second.first][j]=d+mn+1;
                q.push({-d-mn-1, {i-teleport[i][j].second.first, j}});
            }
        }
        if(teleport[i][j].second.second>0){
            if(dist[i+teleport[i][j].second.second][j]>d+mn){
                dist[i+teleport[i][j].second.second][j]=d+mn+1;
                q.push({-d-mn-1, {i+teleport[i][j].second.second, j}});
            }
        }
        if(teleport[i][j].first.first>0){
            if(dist[i][j-teleport[i][j].first.first]>d+mn){
                dist[i][j-teleport[i][j].first.first]=d+mn+1;
                q.push({-d-mn-1, {i, j-teleport[i][j].first.first}});
            }
        }
        if(teleport[i][j].first.second>0){
            if(dist[i][j+teleport[i][j].first.second]>d+mn){
                dist[i][j+teleport[i][j].first.second]=d+mn+1;
                q.push({-d-mn-1, {i, j+teleport[i][j].first.second}});
            }
        }
        //cout << "q: "<< q.size() << "\n";
    }
    /*for(int i = 0; i < r; i++){
        for(int j = 0; j < c; j++){
            if(teleport[i][j].second.second>=100){
                cout << "# ";
                continue;
            }
            cout << teleport[i][j].second.second << " ";
        }
        cout << "\n";
    }
    cout << "\n";
    for(int i = 0; i < r; i++){
        for(int j = 0; j < c; j++){
            if(dist[i][j]>=100){
                cout << "# ";
                continue;
            }
            cout << dist[i][j] << " ";
        }
        cout << "\n";
    }*/
    int ans = dist[cakePos.first][cakePos.second];
    cout << ans << "\n";
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30