oj.uz

Submission #69124

# Submission time Handle Problem Language Result Execution time Memory
69124 2018-08-20T04:34:53 Z MatheusLealV Portals (BOI14_portals) C++17
70 / 100
 1000 ms 151904 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().f;

		fila.pop();

		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;

				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:49:6: warning: unused variable 'u' [-Wunused-variable]
  int u = fim;
      ^
portals.cpp: In function 'int main()':
portals.cpp:170:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int a = 0; a < pos.size(); a++)
                   ~~^~~~~~~~~~~~
portals.cpp:177: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 30896 KB Output is correct
3 Correct 27 ms 30896 KB Output is correct
4 Correct 27 ms 30896 KB Output is correct
5 Correct 29 ms 30932 KB Output is correct
6 Correct 32 ms 31004 KB Output is correct
7 Correct 27 ms 31132 KB Output is correct
8 Correct 32 ms 31132 KB Output is correct
9 Correct 28 ms 31132 KB Output is correct
10 Correct 33 ms 31132 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 31132 KB Output is correct
2 Correct 29 ms 31132 KB Output is correct
3 Correct 28 ms 31132 KB Output is correct
4 Correct 28 ms 31132 KB Output is correct
5 Correct 30 ms 31132 KB Output is correct
6 Correct 36 ms 31132 KB Output is correct
7 Correct 31 ms 31212 KB Output is correct
8 Correct 34 ms 31228 KB Output is correct
9 Correct 37 ms 32256 KB Output is correct
10 Correct 41 ms 32256 KB Output is correct
11 Correct 29 ms 32256 KB Output is correct
12 Correct 30 ms 32256 KB Output is correct
13 Correct 29 ms 32256 KB Output is correct
14 Correct 29 ms 32256 KB Output is correct
15 Correct 29 ms 32300 KB Output is correct
16 Correct 32 ms 32300 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 32300 KB Output is correct
2 Correct 32 ms 32300 KB Output is correct
3 Correct 32 ms 32300 KB Output is correct
4 Correct 27 ms 32300 KB Output is correct
5 Correct 56 ms 38396 KB Output is correct
6 Correct 74 ms 38524 KB Output is correct
7 Correct 60 ms 38780 KB Output is correct
8 Correct 74 ms 38780 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 38780 KB Output is correct
2 Correct 29 ms 38780 KB Output is correct
3 Correct 32 ms 38780 KB Output is correct
4 Correct 27 ms 38780 KB Output is correct
5 Correct 28 ms 38780 KB Output is correct
6 Correct 27 ms 38780 KB Output is correct
7 Correct 26 ms 38780 KB Output is correct
8 Correct 27 ms 38780 KB Output is correct
9 Correct 29 ms 38780 KB Output is correct
10 Correct 33 ms 38780 KB Output is correct
11 Correct 32 ms 38780 KB Output is correct
12 Correct 37 ms 38780 KB Output is correct
13 Correct 29 ms 38780 KB Output is correct
14 Correct 51 ms 38780 KB Output is correct
15 Correct 72 ms 38780 KB Output is correct
16 Correct 65 ms 38784 KB Output is correct
17 Correct 58 ms 38896 KB Output is correct
18 Correct 69 ms 39164 KB Output is correct
19 Correct 83 ms 39748 KB Output is correct
20 Correct 88 ms 39804 KB Output is correct
21 Correct 73 ms 39804 KB Output is correct
22 Correct 56 ms 39804 KB Output is correct
23 Correct 62 ms 39804 KB Output is correct
24 Correct 60 ms 39808 KB Output is correct
25 Correct 28 ms 39808 KB Output is correct
26 Correct 29 ms 39808 KB Output is correct
27 Correct 28 ms 39808 KB Output is correct
28 Correct 52 ms 39808 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 39808 KB Output is correct
2 Correct 30 ms 39808 KB Output is correct
3 Correct 28 ms 39808 KB Output is correct
4 Correct 33 ms 39808 KB Output is correct
5 Correct 30 ms 39808 KB Output is correct
6 Correct 34 ms 39808 KB Output is correct
7 Correct 28 ms 39808 KB Output is correct
8 Correct 30 ms 39808 KB Output is correct
9 Correct 32 ms 39808 KB Output is correct
10 Correct 30 ms 39808 KB Output is correct
11 Correct 31 ms 39808 KB Output is correct
12 Correct 31 ms 39808 KB Output is correct
13 Correct 29 ms 39808 KB Output is correct
14 Correct 59 ms 39808 KB Output is correct
15 Correct 57 ms 39808 KB Output is correct
16 Correct 58 ms 39808 KB Output is correct
17 Correct 65 ms 39808 KB Output is correct
18 Correct 70 ms 39808 KB Output is correct
19 Correct 76 ms 39808 KB Output is correct
20 Correct 63 ms 39932 KB Output is correct
21 Correct 49 ms 39932 KB Output is correct
22 Correct 57 ms 39932 KB Output is correct
23 Correct 70 ms 39932 KB Output is correct
24 Correct 732 ms 127100 KB Output is correct
25 Execution timed out 1097 ms 151904 KB Time limit exceeded
26 Halted 0 ms 0 KB -