oj.uz

Submission #69120

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

	// while(true)
	// {
	// 	int x = O[u].f, y = O[u].s;

	// 	cout<<"at position "<<x<<" "<<y<<"\n";

	// 	if(u == ini) break;

	// 	u = pai[u];
	// }

	return dist[fim];
}

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

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

			vector< pii > pos;

			for(int z = j; z > 0; z--)
			{
				if(mat[i][z] == '#') break;

				if(mat[i][z - 1] == '#' and mat[i][z] != '#')
				{
					pos.push_back({i, z});

					break;
				}
			}

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

				if(mat[i][z + 1] == '#' and mat[i][z] != '#')
				{
					pos.push_back({i, z});

					break;
				}
			}

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

				if(mat[z + 1][j] == '#' and mat[z][j] != '#')
				{
					pos.push_back({z, j});

					break;
				}
			}

			for(int z = i; z > 0; z --)
			{
				if(mat[z][j] == '#') break;

				if(mat[z - 1][j] == '#' and mat[z][j] != '#')
				{
					pos.push_back({z, j});

					break;
				}
			}

			int x = id[i][j];

			for(int a = 0; a < pos.size(); a++)
			{
				for(int b = 0; b < pos.size(); b++)
				{
					if(a == b) continue;

					int A = abs(i - pos[a].f) + abs(j - pos[a].s), B = abs(i - pos[b].f) + abs(j - pos[b].s);

					int custo = min(A, B) + 1;

					 grafo[x].push_back({id[pos[a].f][pos[a].s], custo});

					// grafo[id[pos[b].f][pos[b].s]].push_back({id[pos[a].f][pos[a].s], custo});

					//cout<<"GRAFO "<<i<<" "<<j<<"   "<<pos[a].f<<" "<<pos[a].s<<"    "<<pos[b].f<<" "<<pos[b].s<<" "<<custo<<"\n";
				}
			}
		}
	}

	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:174:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int a = 0; a < pos.size(); a++)
                   ~~^~~~~~~~~~~~
portals.cpp:176:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int b = 0; b < pos.size(); b++)
                    ~~^~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 30584 KB Output is correct
2 Correct 27 ms 30700 KB Output is correct
3 Correct 28 ms 30700 KB Output is correct
4 Correct 38 ms 30772 KB Output is correct
5 Correct 32 ms 30772 KB Output is correct
6 Correct 31 ms 30820 KB Output is correct
7 Correct 34 ms 30820 KB Output is correct
8 Correct 31 ms 30936 KB Output is correct
9 Correct 29 ms 30936 KB Output is correct
10 Correct 30 ms 30936 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 30936 KB Output is correct
2 Correct 26 ms 30936 KB Output is correct
3 Correct 27 ms 30936 KB Output is correct
4 Correct 27 ms 30936 KB Output is correct
5 Correct 28 ms 30976 KB Output is correct
6 Correct 28 ms 30976 KB Output is correct
7 Correct 28 ms 31224 KB Output is correct
8 Correct 27 ms 31224 KB Output is correct
9 Correct 30 ms 31584 KB Output is correct
10 Correct 36 ms 31592 KB Output is correct
11 Correct 34 ms 31592 KB Output is correct
12 Correct 37 ms 31596 KB Output is correct
13 Correct 30 ms 31596 KB Output is correct
14 Correct 28 ms 31596 KB Output is correct
15 Correct 35 ms 31596 KB Output is correct
16 Correct 29 ms 31596 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 31596 KB Output is correct
2 Correct 28 ms 31596 KB Output is correct
3 Correct 29 ms 31596 KB Output is correct
4 Correct 28 ms 31596 KB Output is correct
5 Correct 58 ms 35696 KB Output is correct
6 Correct 58 ms 35800 KB Output is correct
7 Correct 64 ms 36228 KB Output is correct
8 Correct 55 ms 36296 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 36296 KB Output is correct
2 Correct 27 ms 36296 KB Output is correct
3 Correct 30 ms 36296 KB Output is correct
4 Correct 35 ms 36296 KB Output is correct
5 Correct 30 ms 36296 KB Output is correct
6 Correct 30 ms 36296 KB Output is correct
7 Correct 31 ms 36296 KB Output is correct
8 Correct 30 ms 36296 KB Output is correct
9 Correct 33 ms 36296 KB Output is correct
10 Correct 35 ms 36296 KB Output is correct
11 Correct 35 ms 36296 KB Output is correct
12 Correct 33 ms 36296 KB Output is correct
13 Correct 28 ms 36296 KB Output is correct
14 Correct 55 ms 36296 KB Output is correct
15 Correct 64 ms 36296 KB Output is correct
16 Correct 62 ms 36472 KB Output is correct
17 Correct 61 ms 36472 KB Output is correct
18 Correct 66 ms 37208 KB Output is correct
19 Correct 97 ms 38528 KB Output is correct
20 Correct 90 ms 38568 KB Output is correct
21 Correct 58 ms 38568 KB Output is correct
22 Correct 63 ms 38568 KB Output is correct
23 Correct 58 ms 38568 KB Output is correct
24 Correct 111 ms 38732 KB Output is correct
25 Correct 28 ms 38732 KB Output is correct
26 Correct 30 ms 38732 KB Output is correct
27 Correct 32 ms 38732 KB Output is correct
28 Correct 79 ms 38732 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 38732 KB Output is correct
2 Correct 27 ms 38732 KB Output is correct
3 Correct 27 ms 38732 KB Output is correct
4 Correct 29 ms 38732 KB Output is correct
5 Correct 28 ms 38732 KB Output is correct
6 Correct 29 ms 38732 KB Output is correct
7 Correct 28 ms 38732 KB Output is correct
8 Correct 29 ms 38732 KB Output is correct
9 Correct 40 ms 38732 KB Output is correct
10 Correct 39 ms 38732 KB Output is correct
11 Correct 32 ms 38732 KB Output is correct
12 Correct 31 ms 38732 KB Output is correct
13 Correct 37 ms 38732 KB Output is correct
14 Correct 57 ms 38732 KB Output is correct
15 Correct 60 ms 38732 KB Output is correct
16 Correct 61 ms 38732 KB Output is correct
17 Correct 60 ms 38732 KB Output is correct
18 Correct 80 ms 38732 KB Output is correct
19 Correct 108 ms 39068 KB Output is correct
20 Correct 127 ms 39108 KB Output is correct
21 Correct 58 ms 39108 KB Output is correct
22 Correct 57 ms 39108 KB Output is correct
23 Correct 62 ms 39108 KB Output is correct
24 Correct 968 ms 139464 KB Output is correct
25 Execution timed out 1101 ms 139464 KB Time limit exceeded
26 Halted 0 ms 0 KB -