oj.uz

Submission #115971

# Submission time Handle Problem Language Result Execution time Memory
115971 2019-06-10T05:58:14 Z Mahdi_Jfri Portals (BOI14_portals) C++14
20 / 100
 46 ms 34296 KB 
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define left leftt
#define right wrong

const int maxn = 1e3 + 20;
const int maxm = maxn * maxn + 20;
const int dx[] = {0 , 0 , 1 ,-1};
const int dy[] = {1 ,-1 , 0 , 0}; 

int d[maxm] , n , m , up[maxn][maxn] , left[maxn][maxn] , down[maxn][maxn] , right[maxn][maxn];

vector<pair<int , int> > adj[maxm];

string s[maxn];

int cd(int x , int y)
{
	return x * n + y;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m;
	for(int i = 0; i < n; i++)
		cin >> s[i];

	queue<int> q;
	memset(d , 63 , sizeof d);
	for(int x = 0; x < n; x++)
		for(int y = 0; y < m; y++)
		{
			if(s[x][y] == '#')
				continue;

			for(int i = 0; i < 4; i++)
			{
				int nx = x + dx[i] , ny = y + dy[i];
				if(0 <= nx && nx < n && 0 <= ny && ny < m && s[nx][ny] != '#')
					adj[cd(x , y)].pb({cd(nx , ny) , 1});
			}

			if(adj[cd(x , y)].size() != 4)
				q.push(cd(x , y)) , d[cd(x , y)] = 1;
		}

	while(!q.empty())
	{
		int v = q.front();
		q.pop();

		for(auto e : adj[v])
		{
			int u = e.first;
			if(d[u] > d[v] + 1)
				d[u] = d[v] + 1 , q.push(u);
		}
	}

	for(int x = 0; x < n; x++)
	{
		for(int y = 0; y < m; y++)
		{
			if(!y || s[x][y - 1] == '#')
				left[x][y] = cd(x , y);
			else 
				left[x][y] = left[x][y - 1];
		}

		for(int y = m - 1; y >= 0; y--)
		{
			if(y + 1 >= m || s[x][y + 1] == '#')
				right[x][y] = cd(x , y);
			else
				right[x][y] = right[x][y + 1];
		}
	}

	for(int y = 0; y < m; y++)
	{
		for(int x = 0; x < n; x++)
		{
			if(!x || s[x - 1][y] == '#')
				up[x][y] = cd(x , y);
			else
				up[x][y] = up[x - 1][y];
		}

		for(int x = n - 1; x >= 0; x--)
		{
			if(x + 1 >= n || s[x + 1][y] == '#')
				down[x][y] = cd(x , y);
			else
				down[x][y] = down[x + 1][y];
		}
	}

	int S , T;
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
			if(s[i][j] != '#')
			{
				adj[cd(i , j)].pb({right[i][j] , d[cd(i , j)]});
				adj[cd(i , j)].pb({left[i][j] , d[cd(i , j)]});
				adj[cd(i , j)].pb({up[i][j] , d[cd(i , j)]});
				adj[cd(i , j)].pb({down[i][j] , d[cd(i , j)]});

				if(s[i][j] == 'S')
					S = cd(i , j);
				if(s[i][j] == 'C')
					T = cd(i , j);
			}

	memset(d , 63 , sizeof d);
	d[S] = 0;
	set<pair<int , int> > st;
	st.insert({d[S] , S});

	while(!st.empty())
	{
		int v = st.begin() -> second;
		int W = st.begin() -> first;
		st.erase(st.begin());

		if(d[v] != W)
			continue;

		for(auto e : adj[v])
		{
			int w = e.second , u = e.first;
			if(d[u] > d[v] + w)
			{
				d[u] = d[v] + w;
				st.insert({d[u] , u});
			}
		}
	}

	cout << d[T] << endl;
}

Compilation message

portals.cpp: In function 'int main()':
portals.cpp:146:13: warning: 'T' may be used uninitialized in this function [-Wmaybe-uninitialized]
  cout << d[T] << endl;
             ^

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 28928 KB Output is correct
2 Correct 26 ms 29056 KB Output is correct
3 Correct 26 ms 29048 KB Output is correct
4 Incorrect 27 ms 28920 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 28928 KB Output is correct
2 Correct 26 ms 29056 KB Output is correct
3 Correct 26 ms 29028 KB Output is correct
4 Incorrect 26 ms 28928 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 28928 KB Output is correct
2 Correct 27 ms 28948 KB Output is correct
3 Correct 27 ms 29164 KB Output is correct
4 Correct 28 ms 29056 KB Output is correct
5 Correct 44 ms 34036 KB Output is correct
6 Correct 45 ms 34040 KB Output is correct
7 Correct 46 ms 34168 KB Output is correct
8 Correct 43 ms 34296 KB Output is correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 28968 KB Output is correct
2 Correct 28 ms 29056 KB Output is correct
3 Correct 33 ms 29048 KB Output is correct
4 Incorrect 28 ms 28920 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 28928 KB Output is correct
2 Correct 36 ms 29056 KB Output is correct
3 Correct 28 ms 29056 KB Output is correct
4 Incorrect 29 ms 28928 KB Output isn't correct
5 Halted 0 ms 0 KB -