답안 #69125 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
69125	2018-08-20T04:37:01 Z	MatheusLealV	포탈들 (BOI14_portals)	C++17	70 / 100	1000 ms	147092 KB

portals

#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], 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(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;

				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:51:6: warning: unused variable 'u' [-Wunused-variable]
  int u = fim;
      ^
portals.cpp: In function 'int main()':
portals.cpp:172:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int a = 0; a < pos.size(); a++)
                   ~~^~~~~~~~~~~~
portals.cpp:179: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

#	결과	실행 시간	메모리	Grader output
1	Correct	28 ms	27896 KB	Output is correct
2	Correct	29 ms	28260 KB	Output is correct
3	Correct	30 ms	28464 KB	Output is correct
4	Correct	27 ms	28464 KB	Output is correct
5	Correct	26 ms	28464 KB	Output is correct
6	Correct	28 ms	28464 KB	Output is correct
7	Correct	26 ms	28464 KB	Output is correct
8	Correct	27 ms	28464 KB	Output is correct
9	Correct	26 ms	28464 KB	Output is correct
10	Correct	28 ms	28464 KB	Output is correct

Subtask #2
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	25 ms	28464 KB	Output is correct
2	Correct	25 ms	28464 KB	Output is correct
3	Correct	26 ms	28464 KB	Output is correct
4	Correct	25 ms	28464 KB	Output is correct
5	Correct	27 ms	28464 KB	Output is correct
6	Correct	25 ms	28524 KB	Output is correct
7	Correct	28 ms	28524 KB	Output is correct
8	Correct	30 ms	28524 KB	Output is correct
9	Correct	27 ms	29564 KB	Output is correct
10	Correct	35 ms	29564 KB	Output is correct
11	Correct	31 ms	29564 KB	Output is correct
12	Correct	32 ms	29568 KB	Output is correct
13	Correct	31 ms	29568 KB	Output is correct
14	Correct	26 ms	29568 KB	Output is correct
15	Correct	33 ms	29692 KB	Output is correct
16	Correct	31 ms	29692 KB	Output is correct

Subtask #3
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	30 ms	29692 KB	Output is correct
2	Correct	26 ms	29692 KB	Output is correct
3	Correct	31 ms	29692 KB	Output is correct
4	Correct	43 ms	29692 KB	Output is correct
5	Correct	61 ms	35708 KB	Output is correct
6	Correct	48 ms	35840 KB	Output is correct
7	Correct	49 ms	36096 KB	Output is correct
8	Correct	67 ms	36096 KB	Output is correct

Subtask #4
19.0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	28 ms	36096 KB	Output is correct
2	Correct	28 ms	36096 KB	Output is correct
3	Correct	30 ms	36096 KB	Output is correct
4	Correct	25 ms	36096 KB	Output is correct
5	Correct	28 ms	36096 KB	Output is correct
6	Correct	33 ms	36096 KB	Output is correct
7	Correct	27 ms	36096 KB	Output is correct
8	Correct	30 ms	36096 KB	Output is correct
9	Correct	33 ms	36096 KB	Output is correct
10	Correct	28 ms	36096 KB	Output is correct
11	Correct	28 ms	36096 KB	Output is correct
12	Correct	29 ms	36096 KB	Output is correct
13	Correct	34 ms	36096 KB	Output is correct
14	Correct	66 ms	36096 KB	Output is correct
15	Correct	67 ms	36096 KB	Output is correct
16	Correct	64 ms	36096 KB	Output is correct
17	Correct	54 ms	36096 KB	Output is correct
18	Correct	52 ms	36476 KB	Output is correct
19	Correct	60 ms	37116 KB	Output is correct
20	Correct	56 ms	37116 KB	Output is correct
21	Correct	58 ms	37116 KB	Output is correct
22	Correct	54 ms	37116 KB	Output is correct
23	Correct	49 ms	37116 KB	Output is correct
24	Correct	62 ms	37116 KB	Output is correct
25	Correct	31 ms	37116 KB	Output is correct
26	Correct	29 ms	37116 KB	Output is correct
27	Correct	27 ms	37116 KB	Output is correct
28	Correct	49 ms	37116 KB	Output is correct

Subtask #5
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	25 ms	37116 KB	Output is correct
2	Correct	25 ms	37116 KB	Output is correct
3	Correct	25 ms	37116 KB	Output is correct
4	Correct	26 ms	37116 KB	Output is correct
5	Correct	26 ms	37116 KB	Output is correct
6	Correct	25 ms	37116 KB	Output is correct
7	Correct	26 ms	37116 KB	Output is correct
8	Correct	27 ms	37116 KB	Output is correct
9	Correct	34 ms	37116 KB	Output is correct
10	Correct	29 ms	37116 KB	Output is correct
11	Correct	28 ms	37116 KB	Output is correct
12	Correct	28 ms	37116 KB	Output is correct
13	Correct	38 ms	37116 KB	Output is correct
14	Correct	66 ms	37116 KB	Output is correct
15	Correct	56 ms	37116 KB	Output is correct
16	Correct	51 ms	37116 KB	Output is correct
17	Correct	51 ms	37116 KB	Output is correct
18	Correct	50 ms	37116 KB	Output is correct
19	Correct	51 ms	37116 KB	Output is correct
20	Correct	53 ms	37116 KB	Output is correct
21	Correct	64 ms	37116 KB	Output is correct
22	Correct	48 ms	37116 KB	Output is correct
23	Correct	52 ms	37116 KB	Output is correct
24	Correct	713 ms	122236 KB	Output is correct
25	Execution timed out	1091 ms	147092 KB	Time limit exceeded
26	Halted	0 ms	0 KB	-

답안 #69125

Compilation message

Subtask #1 11.0 / 11.0

Subtask #2 20.0 / 20.0

Subtask #3 20.0 / 20.0

Subtask #4 19.0 / 19.0

Subtask #5 0 / 30.0

Subtask #1
11.0 / 11.0

Subtask #2
20.0 / 20.0

Subtask #3
20.0 / 20.0

Subtask #4
19.0 / 19.0

Subtask #5
0 / 30.0