Submission #945513

#	Time	Username	Problem	Language	Result	Execution time	Memory
945513		yhkhoo	Portals (BOI14_portals)	C++17	20 / 100	15 ms	4700 KiB

portals

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
typedef pair<int, pii> pipii;

#define mp make_pair
#define fi first
#define se second

const int INF=1e9;

int main(){
    // cin.tie(0); ios_base::sync_with_stdio(0);
    int r, c;
    cin >> r >> c;
    char m[r][c];
    vector<int> xw[r], yw[c];
    pii sl, cl;
    for(auto && i: xw){
        i.push_back(-1);
    }
    for(auto && i: yw){
        i.push_back(-1);
    }
    for(int i=0; i<r; i++){
        for(int j=0; j<c; j++){
            cin >> m[i][j];
            if(m[i][j] == '#'){
                xw[i].push_back(j);
                yw[j].push_back(i);
            }
            else if(m[i][j] == 'S'){
                sl = mp(i, j);
            }
            else if(m[i][j] == 'C'){
                cl = mp(i, j);
            }
        }
    }
    for(auto && i: xw){
        i.push_back(c);
    }
    for(auto && i: yw){
        i.push_back(r);
    }
    queue<pii> wq;
    int dw[r][c];
    memset(dw, -1, sizeof(dw));
    vector<pipii> al[r][c];
    const int dx[] = {-1, 1, 0, 0};
    const int dy[] = {0, 0, -1, 1};
    for(int i=0; i<r; i++){
        for(int j=0; j<c; j++){
            for(int k=0; k<4; k++){
                int nx = i+dx[k], ny = j+dy[k];
                if(nx == -1 || ny == -1 || nx == r || ny== c || m[nx][ny] == '#'){
                    if(dw[i][j] == 1) continue;
                    wq.emplace(i, j);
                    dw[i][j] = 1;
                }
                else{
                    al[i][j].emplace_back(1, mp(nx, ny));
                }
            }
        }
    }
    while(wq.size()){
        auto[cx, cy] = wq.front();
        wq.pop();
        for(int k=0; k<4; k++){
            int nx = cx+dx[k], ny = cy+dy[k];
            if(nx == -1 || ny == -1 || nx == r || ny == c) continue;
            if(m[nx][ny] == '#') continue;
            if(dw[nx][ny] != -1) continue;
            dw[nx][ny] = dw[cx][cy] + 1;
            wq.emplace(cx, cy);
        }
    }
    for(int i=0; i<r; i++){
        for(int j=0; j<c; j++){
            if(m[i][j] == '#') continue;
            vector<int>::iterator xw1, xw2, yw1, yw2;
            xw2 = upper_bound(xw[i].begin(), xw[i].end(), j);
            xw1 = xw2-1;
            yw2 = upper_bound(yw[j].begin(), yw[j].end(), i);
            yw1 = yw2-1;
            // dw[i][j] = 69420;
            if(*xw2 - j > 2) al[i][j].emplace_back(dw[i][j], mp(i, (*xw2)-1));
            if(j - *xw1 > 2) al[i][j].emplace_back(dw[i][j], mp(i, (*xw1)+1));
            if(*yw2 - i > 2) al[i][j].emplace_back(dw[i][j], mp((*yw2)-1, j));
            if(i - *yw1 > 2) al[i][j].emplace_back(dw[i][j], mp((*yw1)+1, j));
        }
    }
    /*for(int i=0; i<r; i++){
        for(int j=0; j<c; j++){
            cout << i << ' ' << j << ':' << ' ';
            for(auto k: al[i][j]){
                cout << k.fi << '{' << k.se.fi << ',' << k.se.se << '}' << ' ';
            }
            cout << '\n';
        }
    }*/
    priority_queue<pipii, vector<pipii>, greater<pipii>> pq;
    int dst[r][c];
    bool visited[r][c];
    for(int i=0; i<r; i++){
		for(int j=0; j<c; j++){
			dst[i][j] = INF;
		}
	}
    memset(visited, 0, sizeof(visited));
    dst[sl.fi][sl.se] = 0;
    pq.emplace(0, sl);
    while(pq.size()){
        auto[cd, cxy] = pq.top();
        pq.pop();
        auto[cx, cy] = cxy;
        if(visited[cx][cy]) continue;
        for(auto [nw, nxy] : al[cx][cy]){
            auto[nx, ny] = nxy;
            if(dst[nx][ny] > cd+nw){
                dst[nx][ny] = cd+nw;
                pq.emplace(dst[nx][ny], nxy);
            }
        }
        visited[cx][cy] = true;
    }
    cout << dst[cl.fi][cl.se];
    return 0;
}

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