Submission #943199

#	Time	Username	Problem	Language	Result	Execution time	Memory
943199		kxd	Portals (BOI14_portals)	C++17	100 / 100	322 ms	100932 KiB

portals

#include <bits/stdc++.h>
//#define DEBUG 1106
#define int long long
#define ll long long
#define ld long double
#define pb push_back
#define p_q priority_queue
#define m_p make_pair
#define pii pair<int,int>
#define endl '\n'
#define INIT ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define FOR(i,a,b) for(int i = a; i <= b; i++)
#define forn(i,n) for (int i = 0; i < n; i++)
#define forn1(i,n) for (int i = 1; i <= n; i++)
#define all(x) x.begin(),x.end()
#define ft first
#define sd second
#define lowbit(x) (x&(-x))
#define chmax(x,y) x=max(x,y)
#define chmin(x,y) x=min(x,y)
#ifdef DEBUG
#define debug(x) cout << #x << ": " << x << endl;
#else
#define debug(x) 1106;
#endif

using namespace std;
const int N = 1106;
const int inf = 1e9;
const int INF = 1e18;
const int MOD = 1e9+7;

const int dx[4] = {1,-1,0,0};
const int dy[4] = {0,0,1,-1};

int dist[N][N], wall[N][N];
char a[N][N];
pii p[N][N][4];

signed main() {
	INIT
	#ifdef DEBUG
	freopen("input.txt", "r", stdin);
	#endif
	///////////
	forn(i,1005) {
		forn(j,1005) {
			wall[i][j] = (int)1e9;
		}
	}
	forn(i,1005) {
		forn(j,1005) {
			dist[i][j] = (int)1e9;
		}
	}
	int n, m;
	cin >> n >> m;
	n += 2, m += 2;
	forn(i,n) {
		forn(j,m) {
			if (i == 0 || j == 0 || j == m - 1 || i == n - 1) a[i][j] = '#';
			else cin >> a[i][j];
		}
	}
	int sx, sy, ex, ey;
	queue<pii> Q;	
	forn(i,n) {
		forn(j,m) {
			if (a[i][j] == 'S') sx = i, sy = j;
			if (a[i][j] == 'C') ex = i, ey = j;
			if (a[i][j]== '#') {
				wall[i][j] = 0;
				Q.push({i,j});
			}
		}
	}
	while(!Q.empty()){
		auto [x,y] = Q.front();
		Q.pop();
		for (int dir = 0; dir < 4; dir++){
			int nx = x + dx[dir];
			int ny = y + dy[dir];
			if (nx < n && nx >= 0 && ny < m && ny >= 0){
				if (wall[nx][ny] > wall[x][y] + 1){
					Q.push({nx,ny});
					wall[nx][ny] = wall[x][y] + 1;
				}
			}
		}
	}
	forn(j,m) {
		int t = 0;
		forn(i,n) {
			if (a[i][j] == '#') {
				t = i;
			}
			p[i][j][0] = {t + 1,j};
		}
		t = n - 1;
		for (int i = n - 1; i>=0; i--){
			if (a[i][j] == '#'){
				t = i;
			}
			p[i][j][1] = {t - 1,j};
		}
	}
	forn(i,n) {
		int t = 0;
		forn(j,m){
			if (a[i][j] == '#'){
				t = j;
			}
			p[i][j][3] = {i, t + 1};
		}
		t = m - 1;
		for (int j = m - 1; j>=0; j--){
			if (a[i][j] == '#'){
				t = j;
			}
			p[i][j][2] = {i,t - 1};
		}
	}
	p_q<pair<int,pii>> pq;
	pq.push({0,{sx,sy}});
	dist[sx][sy]=0;
	while(!pq.empty()){
		int d = -pq.top().ft;
		auto [x,y] = pq.top().sd;
		pq.pop();
		if (d != dist[x][y]) continue;
		for (int dir = 0; dir < 4; dir++){
			int nx = x + dx[dir];
			int ny = y + dy[dir];
			if (nx < n && nx >= 0 && ny < m && ny >= 0){
				if (a[nx][ny] != '#'){
					if (dist[nx][ny] > d + 1){
						pq.push({-d-1, {nx,ny}});
						dist[nx][ny] = d + 1;
					}
				}
			}
			nx = p[x][y][dir].ft;
			ny = p[x][y][dir].sd;
			if (dist[nx][ny] > wall[x][y] + d){
				if (a[nx][ny] != '#'){
					dist[nx][ny] = d + wall[x][y];
					pq.push({-dist[nx][ny], {nx,ny}});
				}
			}
		}
	}
	cout << dist[ex][ey];
}

Compilation message (stderr)

portals.cpp: In function 'int main()':
portals.cpp:125:14: warning: 'sy' may be used uninitialized in this function [-Wmaybe-uninitialized]
  125 |  dist[sx][sy]=0;
      |  ~~~~~~~~~~~~^~
portals.cpp:152:21: warning: 'ey' may be used uninitialized in this function [-Wmaybe-uninitialized]
  152 |  cout << dist[ex][ey];
      |                     ^
portals.cpp:152:21: warning: 'ex' may be used uninitialized in this function [-Wmaybe-uninitialized]
portals.cpp:125:14: warning: 'sx' may be used uninitialized in this function [-Wmaybe-uninitialized]
  125 |  dist[sx][sy]=0;
      |  ~~~~~~~~~~~~^~

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