oj.uz

Submission #69121

# Submission time Handle Problem Language Result Execution time Memory
69121 2018-08-20T04:31:05 Z MatheusLealV Portals (BOI14_portals) C++17
70 / 100
 1000 ms 151804 KB 
#include <bits/stdc++.h>
#define N 1050
#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], pai[N*N];

pii O[N];

char mat[N][N];

vector<pii> grafo[N*N];

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().s;

		fila.pop();

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

				pai[v.f] = x;

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

	int u = fim;

	return dist[fim];
}

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

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};
		}
	}
}

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

	cin>>n>>m;

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

			O[id[i][j]] = {i, j};
		}
	}

	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;
			}

			cin>>mat[i][j];

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

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

	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 solve(int, int)':
portals.cpp:30:25: warning: unused variable 'd' [-Wunused-variable]
   int x = fila.top().s, d = fila.top().s;
                         ^
portals.cpp:47:6: warning: unused variable 'u' [-Wunused-variable]
  int u = fim;
      ^
portals.cpp: In function 'int main()':
portals.cpp:168:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int a = 0; a < pos.size(); a++)
                   ~~^~~~~~~~~~~~
portals.cpp:175: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 33 ms 30584 KB Output is correct
2 Correct 28 ms 30824 KB Output is correct
3 Correct 32 ms 30848 KB Output is correct
4 Correct 34 ms 30848 KB Output is correct
5 Correct 29 ms 31156 KB Output is correct
6 Correct 32 ms 31156 KB Output is correct
7 Correct 35 ms 31156 KB Output is correct
8 Correct 30 ms 31156 KB Output is correct
9 Correct 35 ms 31156 KB Output is correct
10 Correct 31 ms 31156 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 31156 KB Output is correct
2 Correct 30 ms 31156 KB Output is correct
3 Correct 37 ms 31156 KB Output is correct
4 Correct 31 ms 31156 KB Output is correct
5 Correct 31 ms 31156 KB Output is correct
6 Correct 35 ms 31212 KB Output is correct
7 Correct 35 ms 31212 KB Output is correct
8 Correct 33 ms 31212 KB Output is correct
9 Correct 32 ms 32236 KB Output is correct
10 Correct 32 ms 32236 KB Output is correct
11 Correct 33 ms 32236 KB Output is correct
12 Correct 32 ms 32236 KB Output is correct
13 Correct 29 ms 32236 KB Output is correct
14 Correct 28 ms 32236 KB Output is correct
15 Correct 30 ms 32252 KB Output is correct
16 Correct 29 ms 32252 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 32252 KB Output is correct
2 Correct 34 ms 32252 KB Output is correct
3 Correct 29 ms 32252 KB Output is correct
4 Correct 34 ms 32252 KB Output is correct
5 Correct 49 ms 38440 KB Output is correct
6 Correct 51 ms 38524 KB Output is correct
7 Correct 68 ms 38784 KB Output is correct
8 Correct 48 ms 38784 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 38784 KB Output is correct
2 Correct 39 ms 38784 KB Output is correct
3 Correct 27 ms 38784 KB Output is correct
4 Correct 29 ms 38784 KB Output is correct
5 Correct 29 ms 38784 KB Output is correct
6 Correct 28 ms 38784 KB Output is correct
7 Correct 32 ms 38784 KB Output is correct
8 Correct 32 ms 38784 KB Output is correct
9 Correct 34 ms 38784 KB Output is correct
10 Correct 30 ms 38784 KB Output is correct
11 Correct 32 ms 38784 KB Output is correct
12 Correct 34 ms 38784 KB Output is correct
13 Correct 33 ms 38784 KB Output is correct
14 Correct 55 ms 38784 KB Output is correct
15 Correct 68 ms 38784 KB Output is correct
16 Correct 60 ms 38784 KB Output is correct
17 Correct 55 ms 38784 KB Output is correct
18 Correct 66 ms 39212 KB Output is correct
19 Correct 70 ms 39868 KB Output is correct
20 Correct 67 ms 39868 KB Output is correct
21 Correct 48 ms 39868 KB Output is correct
22 Correct 51 ms 39868 KB Output is correct
23 Correct 49 ms 39868 KB Output is correct
24 Correct 64 ms 39868 KB Output is correct
25 Correct 27 ms 39868 KB Output is correct
26 Correct 28 ms 39868 KB Output is correct
27 Correct 28 ms 39868 KB Output is correct
28 Correct 49 ms 39868 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 39868 KB Output is correct
2 Correct 29 ms 39868 KB Output is correct
3 Correct 27 ms 39868 KB Output is correct
4 Correct 29 ms 39868 KB Output is correct
5 Correct 29 ms 39868 KB Output is correct
6 Correct 29 ms 39868 KB Output is correct
7 Correct 27 ms 39868 KB Output is correct
8 Correct 27 ms 39868 KB Output is correct
9 Correct 32 ms 39868 KB Output is correct
10 Correct 32 ms 39868 KB Output is correct
11 Correct 36 ms 39868 KB Output is correct
12 Correct 31 ms 39868 KB Output is correct
13 Correct 32 ms 39868 KB Output is correct
14 Correct 47 ms 39868 KB Output is correct
15 Correct 48 ms 39868 KB Output is correct
16 Correct 79 ms 39868 KB Output is correct
17 Correct 65 ms 39868 KB Output is correct
18 Correct 77 ms 39868 KB Output is correct
19 Correct 80 ms 39868 KB Output is correct
20 Correct 73 ms 39868 KB Output is correct
21 Correct 53 ms 39868 KB Output is correct
22 Correct 51 ms 39868 KB Output is correct
23 Correct 55 ms 39868 KB Output is correct
24 Correct 706 ms 127228 KB Output is correct
25 Execution timed out 1093 ms 151804 KB Time limit exceeded
26 Halted 0 ms 0 KB -