Submission #105978

#	Time	Username	Problem	Language	Result	Execution time	Memory
105978		xiaowuc1	Portals (BOI14_portals)	C++14	100 / 100	841 ms	117540 KiB

portals

#include <algorithm>
#include <cassert>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> pipii;
typedef vector<vector<ll>> matrix;

int closestWall[1000][1000];
vector<pii> dests[1000][1000];
int dp[1000][1000];
vector<pii> locs[1000000];
string g[1000];
int r, c;
int dx[4]{-1,0,1,0};
int dy[4]{0,1,0,-1};

void relax(int x, int y) {
	// one move
	for(int k = 0; k < 4; k++) {
		int nx = x + dx[k];
		int ny = y + dy[k];
		if(nx < 0 || nx >= r || ny < 0 || ny >= c || g[nx][ny] == '#') continue;
		if(dp[nx][ny] > 1 + dp[x][y]) {
			dp[nx][ny] = 1 + dp[x][y];
			locs[dp[nx][ny]].push_back({nx, ny});
		}
	}
	// portal
	for(pii out: dests[x][y]) {
		int nt = dp[x][y] + closestWall[x][y] + 1;
		if(dp[out.first][out.second] > nt) {
			dp[out.first][out.second] = nt;
			locs[dp[out.first][out.second]].push_back({out.first, out.second});
		}
	}
}

void bfs() {
	for(int qq = 0; qq < r*c; qq++) {
		for(pii out: locs[qq]) {
			if(dp[out.first][out.second] != qq) continue;
			relax(out.first, out.second);
		}
	}
}

void solve() {
	cin >> r >> c;
	for(int i = 0; i < r; i++) cin >> g[i];
	for(int i = 0; i < r; i++) {
		for(int j = 0; j < c; j++) {
			if(g[i][j] == 'S') {
				locs[0].push_back({i, j});
			}
			else {
				dp[i][j] = 1 << 25;
			}
			closestWall[i][j] = 1 << 25;
		}
	}
	for(int j = 0; j < c; j++) {
		int currDist = 0;
		for(int i = 0; i < r; i++) {
			if(g[i][j] == '#') {
				currDist = 0;
			}
			else {
				dests[i][j].push_back({i-currDist, j});
				closestWall[i][j] = min(closestWall[i][j], currDist++);
			}
		}
	}
	for(int j = 0; j < c; j++) {
		int currDist = 0;
		for(int i = r-1; i >= 0; i--) {
			if(g[i][j] == '#') {
				currDist = 0;
			}
			else {
				dests[i][j].push_back({i+currDist, j});
				closestWall[i][j] = min(closestWall[i][j], currDist++);
			}
		}
	}
	for(int i = 0; i < r; i++) {
		int currDist = 0;
		for(int j = 0; j < c; j++) {
			if(g[i][j] == '#') {
				currDist = 0;
			}
			else {
				dests[i][j].push_back({i, j-currDist});
				closestWall[i][j] = min(closestWall[i][j], currDist++);
			}
		}
	}
	for(int i = 0; i < r; i++) {
		int currDist = 0;
		for(int j = c-1; j >= 0; j--) {
			if(g[i][j] == '#') {
				currDist = 0;
			}
			else {
				dests[i][j].push_back({i, j+currDist});
				closestWall[i][j] = min(closestWall[i][j], currDist++);
			}
		}
	}
	bfs();
	for(int i = 0; i < r; i++) {
		for(int j = 0; j < c; j++) {
			if(g[i][j] == 'C') {
				cout << dp[i][j] << endl;
				return;
			}
		}
	}
}


int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
	/*
  int t;
  cin >> t;
  for(int i = 1; i <= t; i++) {
    cout << "Case #" << i << ": ";
    solve();
  }
	*/
	solve();
}

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