oj.uz

Submission #69129

# Submission time Handle Problem Language Result Execution time Memory
69129 2018-08-20T04:54:48 Z MatheusLealV Portals (BOI14_portals) C++17
70 / 100
 1000 ms 142992 KB 
#include <bits/stdc++.h>
#define N 1003
#define f first
#define s second
using namespace std;
typedef pair<int, int> pii;

int n, m, xo, yo, xi, yi, dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};

int id[N][N], cnt, dist[N*N];

char mat[N][N];

vector<pii> grafo[N*N];

inline int solve(int ini, int fim)
{
	priority_queue<pii, vector<pii>, greater<pii> > fila;

	memset(dist, 0x3f3f3f3f, sizeof dist);

	dist[ini] = 0;

	fila.push({0, ini});

	while(!fila.empty())
	{
		int x = fila.top().s, d = fila.top().f;

		fila.pop();

		if(x == fim) break;

		if(d > dist[x]) continue;

		for(auto v: grafo[x])
		{
			if(dist[v.f] > dist[x] + v.s)
			{
				dist[v.f] = dist[x] + v.s;

				fila.push({dist[v.f], v.f});
			}
		}
	}

	return dist[fim];
}

pii esq[N][N], dir[N][N], baixo[N][N], cima[N][N];

inline void fill()
{
	for(int i = 1; i <= n; i++)
	{
		int ultimo = 0;

		for(int j = 1; j <= m; j++)
		{
			if(mat[i][j] == '#') ultimo = j;

			esq[i][j] = {i, ultimo + 1};
		}

		ultimo = m + 1;

		for(int j = m; j >= 1; j--)
		{
			if(mat[i][j] == '#') ultimo = j;

			dir[i][j] = {i, ultimo - 1};			
		}
	}

	for(int j = 1; j <= m; j++)
	{
		int ultimo = 0;

		for(int i = 1; i <= n; i++)
		{
			if(mat[i][j] == '#') ultimo = i;

			cima[i][j] = {ultimo + 1, j};
		}

		ultimo = n + 1;

		for(int i = n; i >= 1; i --)
		{
			if(mat[i][j] == '#') ultimo = i;

			baixo[i][j] = {ultimo - 1, j};
		}
	}
}

inline int get(){

	int n = 0, x;

	for(x=getchar();x<'0'||x>'9';x=getchar()){}

	for(;x>='0'&& x<='9';x=getchar()) n = (n<<3) + (n<<1) + x - '0';

	return n;
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);

	n = get(), m = get();

	for(int i = 0; i <= n + 1; i++)
		for(int j = 0; j <= m + 1; j++)
			id[i][j] = ++ cnt;


	for(int i = 0; i <= n + 1; i++)
	{
		for(int j = 0; j <= m + 1; j++)
		{
			if(!i or i == n + 1 or !j or j == m + 1)
			{
				mat[i][j] = '#';

				continue;
			}

			mat[i][j] = getchar();

			if(mat[i][j] == 'S') xo = i, yo = j;

			if(mat[i][j] == 'C') xi = i, yi = j;

			if(j == m) getchar();
		}
	}

	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= m; j++)
		{
			int x = id[i][j];

			if(mat[i][j] != '#')
			{
				for(int p = 0; p < 4; p++)
				{
					int a = i + dx[p], b = j + dy[p];

					if(a < 0 or b < 0 or a > n + 1 or b > m + 1) continue;

					 if(mat[a][b] != '#') grafo[x].push_back({id[a][b], 1}); 
				}
			}
		}
	}

	fill();

	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= m; j++)
		{
			if(mat[i][j] == '#') continue;

			vector< pii > pos;

			pos.push_back(esq[i][j]), pos.push_back(dir[i][j]);

			pos.push_back(baixo[i][j]), pos.push_back(cima[i][j]);

			int x = id[i][j], custo = 2000000000;

			for(int a = 0; a < pos.size(); a++)
			{
				int A = abs(i - pos[a].f) + abs(j - pos[a].s);

				custo = min(custo, A + 1);
			}

			for(int a = 0; a < pos.size(); a++) grafo[x].push_back({id[pos[a].f][pos[a].s], custo});
		}
	}

	cout<<solve(id[xo][yo], id[xi][yi])<<"\n";
}

Compilation message

portals.cpp: In function 'int main()':
portals.cpp:176:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int a = 0; a < pos.size(); a++)
                   ~~^~~~~~~~~~~~
portals.cpp:183:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int a = 0; a < pos.size(); a++) grafo[x].push_back({id[pos[a].f][pos[a].s], custo});
                   ~~^~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 27900 KB Output is correct
2 Correct 37 ms 28132 KB Output is correct
3 Correct 24 ms 28168 KB Output is correct
4 Correct 24 ms 28244 KB Output is correct
5 Correct 25 ms 28320 KB Output is correct
6 Correct 25 ms 28368 KB Output is correct
7 Correct 24 ms 28396 KB Output is correct
8 Correct 25 ms 28400 KB Output is correct
9 Correct 24 ms 28400 KB Output is correct
10 Correct 26 ms 28420 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 28420 KB Output is correct
2 Correct 27 ms 28524 KB Output is correct
3 Correct 29 ms 28524 KB Output is correct
4 Correct 27 ms 28524 KB Output is correct
5 Correct 30 ms 28524 KB Output is correct
6 Correct 25 ms 28524 KB Output is correct
7 Correct 26 ms 28524 KB Output is correct
8 Correct 25 ms 28524 KB Output is correct
9 Correct 29 ms 29548 KB Output is correct
10 Correct 27 ms 29548 KB Output is correct
11 Correct 26 ms 29548 KB Output is correct
12 Correct 26 ms 29548 KB Output is correct
13 Correct 26 ms 29548 KB Output is correct
14 Correct 27 ms 29548 KB Output is correct
15 Correct 27 ms 29548 KB Output is correct
16 Correct 25 ms 29548 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 29548 KB Output is correct
2 Correct 29 ms 29548 KB Output is correct
3 Correct 26 ms 29548 KB Output is correct
4 Correct 29 ms 29548 KB Output is correct
5 Correct 68 ms 35392 KB Output is correct
6 Correct 48 ms 35580 KB Output is correct
7 Correct 46 ms 35708 KB Output is correct
8 Correct 47 ms 35856 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 35856 KB Output is correct
2 Correct 29 ms 35856 KB Output is correct
3 Correct 27 ms 35856 KB Output is correct
4 Correct 25 ms 35856 KB Output is correct
5 Correct 25 ms 35856 KB Output is correct
6 Correct 33 ms 35856 KB Output is correct
7 Correct 34 ms 35856 KB Output is correct
8 Correct 32 ms 35856 KB Output is correct
9 Correct 32 ms 35856 KB Output is correct
10 Correct 31 ms 35856 KB Output is correct
11 Correct 31 ms 35856 KB Output is correct
12 Correct 27 ms 35856 KB Output is correct
13 Correct 29 ms 35856 KB Output is correct
14 Correct 52 ms 35856 KB Output is correct
15 Correct 46 ms 35856 KB Output is correct
16 Correct 47 ms 35856 KB Output is correct
17 Correct 47 ms 35856 KB Output is correct
18 Correct 55 ms 36068 KB Output is correct
19 Correct 46 ms 36732 KB Output is correct
20 Correct 62 ms 36732 KB Output is correct
21 Correct 45 ms 36732 KB Output is correct
22 Correct 55 ms 36732 KB Output is correct
23 Correct 45 ms 36732 KB Output is correct
24 Correct 53 ms 36732 KB Output is correct
25 Correct 25 ms 36732 KB Output is correct
26 Correct 30 ms 36732 KB Output is correct
27 Correct 32 ms 36732 KB Output is correct
28 Correct 55 ms 36732 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 36732 KB Output is correct
2 Correct 25 ms 36732 KB Output is correct
3 Correct 25 ms 36732 KB Output is correct
4 Correct 26 ms 36732 KB Output is correct
5 Correct 26 ms 36732 KB Output is correct
6 Correct 28 ms 36732 KB Output is correct
7 Correct 28 ms 36732 KB Output is correct
8 Correct 29 ms 36732 KB Output is correct
9 Correct 34 ms 36732 KB Output is correct
10 Correct 29 ms 36732 KB Output is correct
11 Correct 27 ms 36732 KB Output is correct
12 Correct 27 ms 36732 KB Output is correct
13 Correct 27 ms 36732 KB Output is correct
14 Correct 53 ms 36732 KB Output is correct
15 Correct 67 ms 36732 KB Output is correct
16 Correct 48 ms 36732 KB Output is correct
17 Correct 48 ms 36732 KB Output is correct
18 Correct 50 ms 36732 KB Output is correct
19 Correct 60 ms 36988 KB Output is correct
20 Correct 75 ms 36988 KB Output is correct
21 Correct 46 ms 36988 KB Output is correct
22 Correct 50 ms 36988 KB Output is correct
23 Correct 54 ms 36988 KB Output is correct
24 Correct 663 ms 118524 KB Output is correct
25 Execution timed out 1090 ms 142992 KB Time limit exceeded
26 Halted 0 ms 0 KB -