Submission #943265

#	Time	Username	Problem	Language	Result	Execution time	Memory
943265		hmm789	Portals (BOI14_portals)	C++14	100 / 100	798 ms	240556 KiB

portals

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define INF 1000000000000000000

int32_t main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int r, c, sx, sy, ex, ey;
	cin >> r >> c;
	string a[r+2], str;
	for(int i = 1; i <= r; i++) {
		cin >> str;
		a[i] = '#' + str + '#';
	}
	str = "";
	for(int i = 0; i < c+2; i++) str += '#';
	a[0] = str; a[r+1] = str;
	r += 2; c += 2;
	int dist[r][c];
	memset(dist, -1, sizeof(dist));
	queue<pair<int, int>> q;
	int dx[4] = {-1, 0, 0, 1};
	int dy[4] = {0, -1, 1, 0};
	for(int i = 0; i < r; i++) for(int j = 0; j < c; j++) {
		if(a[i][j] == 'S') sx = i, sy = j;
		if(a[i][j] == 'C') ex = i, ey = j;
		if(a[i][j] == '#') {
			q.push({i, j});
			dist[i][j] = 0;
		}
	}
	while(!q.empty()) {
		pair<int, int> c1 = q.front();
		q.pop();
		for(int i = 0; i < 4; i++) {
			int nx = c1.first+dx[i], ny = c1.second+dy[i];
			if(nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
			if(dist[nx][ny] == -1 || dist[nx][ny] > dist[c1.first][c1.second]+1) {
				dist[nx][ny] = dist[c1.first][c1.second]+1;
				q.push({nx, ny});
			}
		}
	}
	vector<pair<pair<int, int>, int>> adj[r][c];
	bool v[r][c];
	memset(v, 0, sizeof(v));
	for(int i = 0; i < r; i++) {
		for(int j = 0; j < c; j++) if(!v[i][j] && a[i][j] != '#' && a[i-1][j] == '#') {
			int idx = i;
			while(idx < r && a[idx][j] != '#') v[idx++][j] = 1;
			for(int k = i; k < idx; k++) {
				adj[k][j].push_back({{i, j}, dist[k][j]});
				adj[k][j].push_back({{idx-1, j}, dist[k][j]});
			}
		}
	}
	memset(v, 0, sizeof(v));
	for(int i = 0; i < r; i++) {
		for(int j = 0; j < c; j++) if(!v[i][j] && a[i][j] != '#' && a[i][j-1] == '#') {
			int idx = j;
			while(idx < c && a[i][idx] != '#') v[i][idx++] = 1;
			for(int k = j; k < idx; k++) {
				adj[i][k].push_back({{i, j}, dist[i][k]});
				adj[i][k].push_back({{i, idx-1}, dist[i][k]});
			}
		}
	}
	for(int i = 0; i < r; i++) {
		for(int j = 0; j < c; j++) if(a[i][j] != '#') {
			for(int k = 0; k < 4; k++) {
				int nx = i+dx[k], ny = j+dy[k];
				if(nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
				if(a[nx][ny] == '#') continue;
				adj[i][j].push_back({{nx, ny}, 1});
			}
		}
	}
	memset(dist, -1, sizeof(dist));
	dist[sx][sy] = 0;
	priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;
	pq.push({0, {sx, sy}});
	while(!pq.empty()) {
		pair<int, pair<int, int>> c = pq.top();
		pq.pop();
		if(dist[c.second.first][c.second.second] != c.first) continue;
		for(auto i : adj[c.second.first][c.second.second]) {
			int nx = i.first.first, ny = i.first.second;
			if(dist[nx][ny] == -1 || dist[nx][ny] > dist[c.second.first][c.second.second]+i.second) {
				dist[nx][ny] = dist[c.second.first][c.second.second]+i.second;
				pq.push({dist[nx][ny], {nx, ny}});
			}
		}
	}
	cout << dist[ex][ey];
}

Compilation message (stderr)

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

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