oj.uz

Submission #115747

# Submission time Handle Problem Language Result Execution time Memory
115747 2019-06-08T20:06:27 Z pamaj Portal (COCI17_portal) C++14
96 / 120
 50 ms 6008 KB 
#include <bits/stdc++.h>
#define F first
#define S second
 
using namespace std;
 
const int maxn = 510, inf = 1e9;
 
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, -1, 1};
 
typedef pair<int, int> ii;
 
int n, m, dist[maxn][maxn];
char mat[maxn][maxn], vis[maxn][maxn];
ii pi, pf;
 
struct pos
{
	int xi, xf, yi, yf;
} last[maxn][maxn];
 
struct iii
{
	int d, x, y;
 
	bool operator<(const iii& o) const
	{
		return d > o.d;
	}
};
 
void dijkstra(ii x)
{
	for(int i = 1 ; i <= n ; ++i)
	{
		for(int j = 1 ; j <= m ; ++j)
		{
			dist[i][j] = inf;
		}
	}
 
	priority_queue<iii> row;
 
	dist[x.F][x.S] = 0;
	row.push({0, x.F, x.S});
 
	while(!row.empty())
	{
		int d = row.top().d;
		int x = row.top().x;
		int y = row.top().y;
		
		row.pop();
 
		if(d > dist[x][y] || vis[x][y] == 1) continue; 
 		vis[x][y] = 1;
		int D = dist[x][y] + 1;
		for(int i = 0 ; i < 4 ; ++i)
		{
			if(x + dx[i] <= n && x + dx[i] >= 1 && y + dy[i] >= 1 && y + dy[i] <= m && mat[x + dx[i]][y + dy[i]] != '#' && dist[x][y] + 1 < dist[x + dx[i]][y + dy[i]])
			{
				dist[x + dx[i]][y + dy[i]] = dist[x][y] + 1;
				row.push({D, x + dx[i], y + dy[i]});
			}
		}
 
		int xi = last[x][y].xi;
		int xf = last[x][y].xf;
		int yi = last[x][y].yi;
		int yf = last[x][y].yf;
 
		if(xi == y - 1)
		{
			if(xf != y + 1 && D < dist[x][xf-1])
			{
				dist[x][xf-1] = D;
				row.push({D, x, xf-1});
			}
 
			if(yi != x - 1 && D < dist[yi+1][y])
			{
				dist[yi+1][y] = D;
				row.push({D, yi+1, y});
			}
 
			if(yf != x + 1 && D < dist[yf-1][y])
			{
				dist[yf-1][y] = D;
				row.push({D, yf-1, y});
			} 
		}
 
		if(xf == y + 1)
		{
			if(xi != y-1 && D < dist[x][xi+1])
			{
				dist[x][xi+1] = D;
				row.push({D, x, xi+1});
			}
 
			if(yi != x - 1 && D < dist[yi+1][y])
			{
				dist[yi+1][y] = D;
				row.push({D, yi+1, y});
			}
 
			if(yf != x + 1 && D < dist[yf-1][y])
			{
				dist[yf-1][y] = D;
				row.push({D, yf-1, y});
			} 
		}
 
		if(yi == x-1)
		{
			if(xi != y-1 && D < dist[x][xi+1])
			{
				dist[x][xi+1] = D;
				row.push({D, x, xi+1});
			}
			if(xf != y + 1 && D < dist[x][xf-1])
			{
				dist[x][xf-1] = D;
				row.push({D, x, xf-1});
			}
 
			if(yf != x + 1 && D < dist[yf-1][y])
			{
				dist[yf-1][y] = D;
				row.push({D, yf-1, y});
			} 
		}
 
		if(yf == x+1)
		{
			if(xi != y-1 && D < dist[x][xi+1])
			{
				dist[x][xi+1] = D;
				row.push({D, x, xi+1});
			}
			if(xf != y + 1 && D < dist[x][xf-1])
			{
				dist[x][xf-1] = D;
				row.push({D, x, xf-1});
			}
 
			if(yi != x - 1 && D < dist[yi+1][y])
			{
				dist[yi+1][y] = D;
				row.push({D, yi+1, y});
			}
		}
	}
}
 
int main()
{
	cin >> n >> m;
 
	memset(mat, '#', sizeof mat);
 
	for(int i = 1 ; i <= n ; ++i)
	{
		for(int j = 1 ; j <= m ; ++j)
		{
			cin >> mat[i][j];
 
			if(mat[i][j] == 'C') pi = {i, j};
			if(mat[i][j] == 'F') pf = {i, j};
		}
	}
 
	for(int i = 1 ; i <= n ; ++i)
	{
		int lasth = 0;
		for(int j = 1 ; j <= m ; ++j)
		{
			if(mat[i][j] == '#') lasth = j;
			else last[i][j].xi = lasth;
		}
		
		lasth = 0;
 
		for(int j = m ; j >= 1 ; --j)
		{
			if(mat[i][j] == '#') lasth = j;
			else last[i][j].xf = lasth;
		}
	}
 
	for(int i = 1 ; i <= m ; ++i)
	{
		int lasth = 0;
 
		for(int j = 1 ; j <= n ; ++j)
		{
			if(mat[j][i] == '#') lasth = j;
			else last[j][i].yi = lasth;
		}
 
		lasth = 0;
 
		for(int j = n ; j >= 1 ; --j)
		{
			if(mat[j][i] == '#') lasth = j;
			else last[j][i].yf = lasth;
		}
	}
 
	dijkstra(pi);
 
	if(dist[pf.F][pf.S] == inf) cout << "nemoguce\n";
	else cout << dist[pf.F][pf.S] << "\n";
	return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 640 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 640 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 640 KB Output is correct
2 Correct 2 ms 640 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 640 KB Output is correct
2 Correct 2 ms 640 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 640 KB Output is correct
2 Correct 10 ms 640 KB Output is correct
3 Correct 2 ms 768 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2176 KB Output is correct
2 Correct 4 ms 1536 KB Output is correct
3 Correct 6 ms 1664 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 2176 KB Output is correct
2 Correct 7 ms 2560 KB Output is correct
3 Correct 7 ms 1920 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 4600 KB Output is correct
2 Correct 22 ms 3272 KB Output is correct
3 Correct 16 ms 3712 KB Output is correct

Subtask #9
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 5248 KB Output is correct
2 Correct 22 ms 5624 KB Output is correct
3 Correct 23 ms 3712 KB Output is correct
4 Incorrect 19 ms 4728 KB Output isn't correct

Subtask #10
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 50 ms 6008 KB Output isn't correct
2 Halted 0 ms 0 KB -