oj.uz

Submission #238178

# Submission time Handle Problem Language Result Execution time Memory
238178 2020-06-10T06:40:59 Z MrRobot_28 Portal (COCI17_portal) C++17
120 / 120
 106 ms 10616 KB 
#include<bits/stdc++.h>
using namespace std;

signed main() {
//	ios_base::sync_with_stdio(false);
//	cin.tie(NULL);
//	cout.tie(NULL);
	int n,  m;
	cin >> n >> m;
	vector <vector <char> > A(n, vector <char> (m));
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < m; j++)
		{
			cin >> A[i][j];
		}
	}
	vector <vector <vector <pair <int, int> > > > go_to(4, vector <vector <pair <int, int> > > (n, vector <pair <int, int> > (m)));
	int x, y, x1, y1;
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < m; j++)
		{
			if(A[i][j] == 'C')
			{
				x = i;
				y = j;
			}
			if(A[i][j] == 'F')
			{
				x1 = i;
				y1 = j;
			}
			if(A[i][j] != '#')
			{
				if(A[i - 1][j] != '#')
				{
					go_to[0][i][j] = go_to[0][i - 1][j];
				}
				else
				{
					go_to[0][i][j] = {i, j};
				}
				if(A[i][j - 1] != '#')
				{
					go_to[1][i][j] = go_to[1][i][j - 1];
				}
				else
				{
					go_to[1][i][j] = {i, j};
				}
			}
		}
	}
	for(int i = n - 1; i >= 0; i--)
	{
		for(int j = m - 1; j >= 0; j--)
		{
			if(A[i][j] != '#')
			{
				if(A[i + 1][j] != '#')
				{
					go_to[2][i][j] = go_to[2][i + 1][j];
				}
				else
				{
					go_to[2][i][j] = {i, j};
				}
				if(A[i][j + 1] != '#')
				{
					go_to[3][i][j] = go_to[3][i][j +1 ];
				}
				else
				{
					go_to[3][i][j] = {i, j};
				}
			}
		}
	}
	vector <vector <int> > dist(n, vector <int> (m, 1e9));
	dist[x][y] = 0;
	priority_queue<pair <int, pair <int, int> > > s;
	s.push({0, {x, y}});
	while(s.size() != 0)
	{
		pair <int, int> v =s.top().second;
		if(dist[v.first][v.second] != -s.top().first)
		{
			s.pop();
			continue;
		}
		s.pop();
		int xa = v.first;
		int ya = v.second;
		if(xa > 0 && dist[xa - 1][ya] > dist[xa][ya] + 1 && A[xa - 1][ya] != '#')
		{
			dist[xa - 1][ya] = dist[xa][ya] + 1;
			s.push({-dist[xa - 1][ya], {xa - 1, ya}});
		}
		if(ya > 0 && dist[xa][ya - 1] > dist[xa][ya] + 1 && A[xa][ya - 1] != '#')
		{
			dist[xa][ya - 1] = dist[xa][ya] + 1;
			s.push({-dist[xa][ya - 1], {xa, ya - 1}});
		}
		if(xa < n - 1 && dist[xa + 1][ya] > dist[xa][ya] + 1 && A[xa + 1][ya] != '#')
		{
			dist[xa + 1][ya] = dist[xa][ya] + 1;
			s.push({-dist[xa + 1][ya], {xa + 1, ya}});
		}
		if(ya < m - 1 && dist[xa][ya + 1] > dist[xa][ya] + 1 && A[xa][ya + 1] != '#')
		{
			dist[xa][ya + 1] = dist[xa][ya] + 1;
			s.push({-dist[xa][ya + 1], {xa, ya + 1}});
		}
		for(int i = 0; i < 4; i++)
		{
			for(int j = 0; j < 4; j++)
			{
				if(i == j){
					continue;
				}
				int d = fabs(xa - go_to[i][xa][ya].first) + fabs(ya - go_to[i][xa][ya].second) + 1;
				int tox = go_to[j][xa][ya].first;
				int toy = go_to[j][xa][ya].second;
				if(dist[tox][toy] > dist[xa][ya] + d)
				{
					dist[tox][toy] = dist[xa][ya] + d;
					s.push({-dist[tox][toy], {tox, toy}});
				}
			}
		}
	}
	if(dist[x1][y1] == 1e9)
	{
		cout << "nemoguce";
	}
	else
	{
		cout << dist[x1][y1];
	}
    return 0;
}

Compilation message

portal.cpp: In function 'int main()':
portal.cpp:133:16: warning: 'y1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  if(dist[x1][y1] == 1e9)
                ^
portal.cpp:133:12: warning: 'x1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  if(dist[x1][y1] == 1e9)
            ^

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 256 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 372 KB Output is correct
2 Correct 4 ms 384 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1152 KB Output is correct
2 Correct 7 ms 1152 KB Output is correct
3 Correct 11 ms 1408 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 2816 KB Output is correct
2 Correct 10 ms 2432 KB Output is correct
3 Correct 15 ms 1792 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 6632 KB Output is correct
2 Correct 40 ms 5040 KB Output is correct
3 Correct 30 ms 4096 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 9336 KB Output is correct
2 Correct 31 ms 8712 KB Output is correct
3 Correct 50 ms 6524 KB Output is correct
4 Correct 51 ms 5376 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 10616 KB Output is correct
2 Correct 35 ms 10496 KB Output is correct
3 Correct 78 ms 10488 KB Output is correct
4 Correct 77 ms 10488 KB Output is correct