oj.uz

Submission #69122

# Submission time Handle Problem Language Result Execution time Memory
69122 2018-08-20T04:33:06 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];

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

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

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 28 ms 30584 KB Output is correct
2 Correct 28 ms 30872 KB Output is correct
3 Correct 32 ms 30940 KB Output is correct
4 Correct 28 ms 30940 KB Output is correct
5 Correct 26 ms 31008 KB Output is correct
6 Correct 29 ms 31028 KB Output is correct
7 Correct 30 ms 31056 KB Output is correct
8 Correct 28 ms 31084 KB Output is correct
9 Correct 33 ms 31084 KB Output is correct
10 Correct 33 ms 31084 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 31084 KB Output is correct
2 Correct 29 ms 31100 KB Output is correct
3 Correct 29 ms 31100 KB Output is correct
4 Correct 27 ms 31100 KB Output is correct
5 Correct 36 ms 31100 KB Output is correct
6 Correct 29 ms 31100 KB Output is correct
7 Correct 33 ms 31192 KB Output is correct
8 Correct 30 ms 31192 KB Output is correct
9 Correct 31 ms 32188 KB Output is correct
10 Correct 36 ms 32272 KB Output is correct
11 Correct 31 ms 32272 KB Output is correct
12 Correct 30 ms 32272 KB Output is correct
13 Correct 34 ms 32272 KB Output is correct
14 Correct 32 ms 32272 KB Output is correct
15 Correct 29 ms 32272 KB Output is correct
16 Correct 28 ms 32272 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 32272 KB Output is correct
2 Correct 27 ms 32272 KB Output is correct
3 Correct 32 ms 32272 KB Output is correct
4 Correct 29 ms 32272 KB Output is correct
5 Correct 52 ms 38396 KB Output is correct
6 Correct 63 ms 38524 KB Output is correct
7 Correct 54 ms 38784 KB Output is correct
8 Correct 53 ms 38784 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 38784 KB Output is correct
2 Correct 27 ms 38784 KB Output is correct
3 Correct 34 ms 38784 KB Output is correct
4 Correct 32 ms 38784 KB Output is correct
5 Correct 34 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 29 ms 38784 KB Output is correct
10 Correct 30 ms 38784 KB Output is correct
11 Correct 34 ms 38784 KB Output is correct
12 Correct 32 ms 38784 KB Output is correct
13 Correct 34 ms 38784 KB Output is correct
14 Correct 50 ms 38784 KB Output is correct
15 Correct 54 ms 38784 KB Output is correct
16 Correct 56 ms 38784 KB Output is correct
17 Correct 52 ms 38784 KB Output is correct
18 Correct 74 ms 39164 KB Output is correct
19 Correct 65 ms 39932 KB Output is correct
20 Correct 67 ms 39932 KB Output is correct
21 Correct 55 ms 39932 KB Output is correct
22 Correct 56 ms 39932 KB Output is correct
23 Correct 68 ms 39932 KB Output is correct
24 Correct 73 ms 39932 KB Output is correct
25 Correct 40 ms 39932 KB Output is correct
26 Correct 40 ms 39932 KB Output is correct
27 Correct 30 ms 39932 KB Output is correct
28 Correct 56 ms 39932 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 39932 KB Output is correct
2 Correct 33 ms 39932 KB Output is correct
3 Correct 33 ms 39932 KB Output is correct
4 Correct 29 ms 39932 KB Output is correct
5 Correct 32 ms 39932 KB Output is correct
6 Correct 34 ms 39932 KB Output is correct
7 Correct 34 ms 39932 KB Output is correct
8 Correct 30 ms 39932 KB Output is correct
9 Correct 33 ms 39932 KB Output is correct
10 Correct 34 ms 39932 KB Output is correct
11 Correct 35 ms 39932 KB Output is correct
12 Correct 36 ms 39932 KB Output is correct
13 Correct 32 ms 39932 KB Output is correct
14 Correct 55 ms 39932 KB Output is correct
15 Correct 59 ms 39932 KB Output is correct
16 Correct 62 ms 39932 KB Output is correct
17 Correct 53 ms 39932 KB Output is correct
18 Correct 62 ms 39932 KB Output is correct
19 Correct 78 ms 39932 KB Output is correct
20 Correct 72 ms 39932 KB Output is correct
21 Correct 49 ms 39932 KB Output is correct
22 Correct 69 ms 39932 KB Output is correct
23 Correct 70 ms 39932 KB Output is correct
24 Correct 731 ms 127152 KB Output is correct
25 Execution timed out 1093 ms 151804 KB Time limit exceeded
26 Halted 0 ms 0 KB -