Submission #234697

#	Time	Username	Problem	Language	Result	Execution time	Memory
234697		BamiTorabi	Portals (BOI14_portals)	C++14	100 / 100	401 ms	34552 KiB

portals

//Sasayego! Sasayego! Shinzou wo Sasageyo!

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <numeric>
#include <bitset>
#include <ctime>
#define debug(x)  cerr << #x << " = " << x << endl
#define lid (id << 1)
#define rid (lid ^ 1)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll, ll> pll;
typedef pair <int, int> pii;

const int maxN = 1e3 + 5;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;

int aX[] = {-1, 0, +1, 0};
int aY[] = {0, -1, 0, +1};
int board[maxN][maxN];
int dir[maxN][maxN][4];
int dis[2][maxN][maxN];
queue <pii> Q;
set <pair <int, pii> > st;
pii S, T;

int main(){
	time_t START = clock();
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	memset(dir, -1, sizeof dir);
	memset(dis, 63, sizeof dis);
	int n, m; scanf("%d%d\n", &n, &m);
	for (int i = 1; i <= n; i++, getchar())
		for (int j = 1; j <= m; j++){
			int ch = getchar();
			board[i][j] = (ch != '#');
			if (ch == 'S')
				S = {i, j};
			if (ch == 'C')
				T = {i, j};
		}
	for (int i = 1; i <= n; i++){
		int lt = 0, rt = 0;
		while (lt != m + 1){
			rt++;
			while (board[i][rt])
				rt++;
			for (int j = lt + 1; j < rt; j++){
				dir[i][j][0] = lt + 1;
				dir[i][j][2] = rt - 1;
			}
			lt = rt;
		}
	}
	for (int j = 1; j <= m; j++){
		int lt = 0, rt = 0;
		while (lt != n + 1){
			rt++;
			while (board[rt][j])
				rt++;
			for (int i = lt + 1; i < rt; i++){
				dir[i][j][1] = lt + 1;
				dir[i][j][3] = rt - 1;
			}
			lt = rt;
		}
	}
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++){
			bool flag = false;
			for (int x = 0; x < 4; x++)
				flag |= !board[i + aX[x]][j + aY[x]];
			flag &= board[i][j];
			if (flag){
				Q.push({i, j});
				dis[0][i][j] = 1;
			}
		}
	while (!Q.empty()){
		int x, y; tie(x, y) = Q.front();
		Q.pop();
		for (int i = 0; i < 4; i++){
			int nx = x + aX[i];
			int ny = y + aY[i];
			if (!board[nx][ny])
				continue;
			if (dis[0][nx][ny] > dis[0][x][y] + 1){
				dis[0][nx][ny] = dis[0][x][y] + 1;
				Q.push({nx, ny});
			}
		}
	}
	dis[1][S.first][S.second] = 0;
	st.insert({0, S});
	while (!st.empty()){
		int x, y; tie(x, y) = st.begin()->second;
		st.erase(st.begin());
		for (int i = 0; i < 4; i++){
			int nx = x + aX[i];
			int ny = y + aY[i];
			if (board[nx][ny])
				if (dis[1][nx][ny] > dis[1][x][y] + 1){
					st.erase({dis[1][nx][ny], {nx, ny}});
					dis[1][nx][ny] = dis[1][x][y] + 1;
					st.insert({dis[1][nx][ny], {nx, ny}});
				}
			nx = (i % 2 ? dir[x][y][i] : x);
			ny = (i % 2 ? y : dir[x][y][i]);
			if (board[nx][ny])
				if (dis[1][nx][ny] > dis[1][x][y] + dis[0][x][y]){
					st.erase({dis[1][nx][ny], {nx, ny}});
					dis[1][nx][ny] = dis[1][x][y] + dis[0][x][y];
					st.insert({dis[1][nx][ny], {nx, ny}});
				}
		}
	}
	printf("%d\n", dis[1][T.first][T.second]);
	time_t FINISH = clock();
	cerr << "Execution time: " << (ld)(FINISH - START) / CLOCKS_PER_SEC * 1000.0 << " milliseconds.\n";
	return 0;
}
 

Compilation message (stderr)

portals.cpp: In function 'int main()':
portals.cpp:45:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n, m; scanf("%d%d\n", &n, &m);
            ~~~~~^~~~~~~~~~~~~~~~~~

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