oj.uz

Submission #234697

# Submission time Handle Problem Language Result Execution time Memory
234697 2020-05-25T08:15:43 Z BamiTorabi Portals (BOI14_portals) C++14
100 / 100
 401 ms 34552 KB 
//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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 24064 KB Output is correct
2 Correct 17 ms 24064 KB Output is correct
3 Correct 17 ms 24192 KB Output is correct
4 Correct 18 ms 24064 KB Output is correct
5 Correct 17 ms 24064 KB Output is correct
6 Correct 17 ms 24064 KB Output is correct
7 Correct 17 ms 24064 KB Output is correct
8 Correct 17 ms 24192 KB Output is correct
9 Correct 17 ms 24064 KB Output is correct
10 Correct 17 ms 24064 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 24064 KB Output is correct
2 Correct 17 ms 24320 KB Output is correct
3 Correct 18 ms 24192 KB Output is correct
4 Correct 16 ms 24064 KB Output is correct
5 Correct 17 ms 24064 KB Output is correct
6 Correct 17 ms 24064 KB Output is correct
7 Correct 17 ms 24064 KB Output is correct
8 Correct 17 ms 24064 KB Output is correct
9 Correct 18 ms 24320 KB Output is correct
10 Correct 18 ms 24320 KB Output is correct
11 Correct 17 ms 24320 KB Output is correct
12 Correct 17 ms 24320 KB Output is correct
13 Correct 18 ms 24320 KB Output is correct
14 Correct 16 ms 24064 KB Output is correct
15 Correct 17 ms 24320 KB Output is correct
16 Correct 16 ms 24064 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 24064 KB Output is correct
2 Correct 17 ms 24192 KB Output is correct
3 Correct 17 ms 24064 KB Output is correct
4 Correct 17 ms 24192 KB Output is correct
5 Correct 23 ms 25088 KB Output is correct
6 Correct 25 ms 25080 KB Output is correct
7 Correct 26 ms 25080 KB Output is correct
8 Correct 21 ms 25088 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 24064 KB Output is correct
2 Correct 17 ms 24064 KB Output is correct
3 Correct 17 ms 24064 KB Output is correct
4 Correct 17 ms 24064 KB Output is correct
5 Correct 17 ms 24192 KB Output is correct
6 Correct 17 ms 24064 KB Output is correct
7 Correct 18 ms 24184 KB Output is correct
8 Correct 17 ms 24064 KB Output is correct
9 Correct 18 ms 24320 KB Output is correct
10 Correct 17 ms 24320 KB Output is correct
11 Correct 17 ms 24320 KB Output is correct
12 Correct 19 ms 24320 KB Output is correct
13 Correct 17 ms 24320 KB Output is correct
14 Correct 23 ms 25088 KB Output is correct
15 Correct 26 ms 25088 KB Output is correct
16 Correct 26 ms 25088 KB Output is correct
17 Correct 25 ms 25088 KB Output is correct
18 Correct 28 ms 25088 KB Output is correct
19 Correct 28 ms 24960 KB Output is correct
20 Correct 27 ms 24960 KB Output is correct
21 Correct 24 ms 25088 KB Output is correct
22 Correct 25 ms 25088 KB Output is correct
23 Correct 26 ms 25088 KB Output is correct
24 Correct 26 ms 24960 KB Output is correct
25 Correct 17 ms 24064 KB Output is correct
26 Correct 17 ms 24320 KB Output is correct
27 Correct 17 ms 24064 KB Output is correct
28 Correct 21 ms 25088 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 24064 KB Output is correct
2 Correct 17 ms 24064 KB Output is correct
3 Correct 18 ms 24064 KB Output is correct
4 Correct 18 ms 24192 KB Output is correct
5 Correct 17 ms 24064 KB Output is correct
6 Correct 18 ms 24064 KB Output is correct
7 Correct 17 ms 24064 KB Output is correct
8 Correct 17 ms 24064 KB Output is correct
9 Correct 18 ms 24320 KB Output is correct
10 Correct 18 ms 24320 KB Output is correct
11 Correct 17 ms 24320 KB Output is correct
12 Correct 19 ms 24320 KB Output is correct
13 Correct 21 ms 24320 KB Output is correct
14 Correct 25 ms 25088 KB Output is correct
15 Correct 27 ms 25088 KB Output is correct
16 Correct 26 ms 25080 KB Output is correct
17 Correct 25 ms 25088 KB Output is correct
18 Correct 28 ms 25088 KB Output is correct
19 Correct 29 ms 24960 KB Output is correct
20 Correct 27 ms 24960 KB Output is correct
21 Correct 24 ms 25088 KB Output is correct
22 Correct 26 ms 25088 KB Output is correct
23 Correct 26 ms 25088 KB Output is correct
24 Correct 281 ms 33016 KB Output is correct
25 Correct 401 ms 29816 KB Output is correct
26 Correct 327 ms 29176 KB Output is correct
27 Correct 344 ms 29560 KB Output is correct
28 Correct 200 ms 33632 KB Output is correct
29 Correct 227 ms 33784 KB Output is correct
30 Correct 265 ms 33912 KB Output is correct
31 Correct 26 ms 24960 KB Output is correct
32 Correct 321 ms 29176 KB Output is correct
33 Correct 17 ms 24064 KB Output is correct
34 Correct 17 ms 24320 KB Output is correct
35 Correct 249 ms 31100 KB Output is correct
36 Correct 17 ms 24064 KB Output is correct
37 Correct 21 ms 25088 KB Output is correct
38 Correct 134 ms 34552 KB Output is correct
39 Correct 176 ms 33144 KB Output is correct