oj.uz

Submission #115981

# Submission time Handle Problem Language Result Execution time Memory
115981 2019-06-10T06:10:40 Z Mahdi_Jfri Portals (BOI14_portals) C++14
100 / 100
 984 ms 125552 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 * m + 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] != '#')
			{
	//			cout << i + 1 << " " << j + 1 << " " << d[cd(i , j)] << endl;
	//			cout << left[i][j] << " " << right[i][j] << " " << up[i][j] << " " << down[i][j] << endl;
				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:148:13: warning: 'T' may be used uninitialized in this function [-Wmaybe-uninitialized]
  cout << d[T] << endl;
             ^

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 28928 KB Output is correct
2 Correct 31 ms 29056 KB Output is correct
3 Correct 26 ms 29056 KB Output is correct
4 Correct 28 ms 28928 KB Output is correct
5 Correct 27 ms 29056 KB Output is correct
6 Correct 26 ms 29056 KB Output is correct
7 Correct 27 ms 29048 KB Output is correct
8 Correct 25 ms 29048 KB Output is correct
9 Correct 26 ms 29056 KB Output is correct
10 Correct 27 ms 28928 KB Output is correct

Subtask #2
20.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 29 ms 29092 KB Output is correct
4 Correct 28 ms 28920 KB Output is correct
5 Correct 27 ms 29056 KB Output is correct
6 Correct 28 ms 29052 KB Output is correct
7 Correct 30 ms 29056 KB Output is correct
8 Correct 29 ms 29056 KB Output is correct
9 Correct 29 ms 30072 KB Output is correct
10 Correct 28 ms 29952 KB Output is correct
11 Correct 27 ms 29816 KB Output is correct
12 Correct 27 ms 29824 KB Output is correct
13 Correct 28 ms 29824 KB Output is correct
14 Correct 27 ms 29028 KB Output is correct
15 Correct 29 ms 29952 KB Output is correct
16 Correct 27 ms 28920 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 27 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 Correct 29 ms 29052 KB Output is correct
5 Correct 41 ms 33920 KB Output is correct
6 Correct 43 ms 34040 KB Output is correct
7 Correct 45 ms 34248 KB Output is correct
8 Correct 38 ms 34296 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 28928 KB Output is correct
2 Correct 27 ms 29056 KB Output is correct
3 Correct 26 ms 29056 KB Output is correct
4 Correct 28 ms 28948 KB Output is correct
5 Correct 28 ms 29056 KB Output is correct
6 Correct 28 ms 29048 KB Output is correct
7 Correct 28 ms 29056 KB Output is correct
8 Correct 27 ms 29056 KB Output is correct
9 Correct 29 ms 29952 KB Output is correct
10 Correct 29 ms 29952 KB Output is correct
11 Correct 29 ms 29824 KB Output is correct
12 Correct 28 ms 29824 KB Output is correct
13 Correct 29 ms 29924 KB Output is correct
14 Correct 41 ms 33912 KB Output is correct
15 Correct 45 ms 34040 KB Output is correct
16 Correct 44 ms 34168 KB Output is correct
17 Correct 43 ms 34140 KB Output is correct
18 Correct 57 ms 34680 KB Output is correct
19 Correct 55 ms 35320 KB Output is correct
20 Correct 52 ms 35292 KB Output is correct
21 Correct 47 ms 34048 KB Output is correct
22 Correct 46 ms 34040 KB Output is correct
23 Correct 47 ms 34176 KB Output is correct
24 Correct 52 ms 35320 KB Output is correct
25 Correct 26 ms 28964 KB Output is correct
26 Correct 28 ms 29816 KB Output is correct
27 Correct 27 ms 28928 KB Output is correct
28 Correct 40 ms 34296 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 28928 KB Output is correct
2 Correct 28 ms 29056 KB Output is correct
3 Correct 35 ms 29192 KB Output is correct
4 Correct 28 ms 28900 KB Output is correct
5 Correct 28 ms 29048 KB Output is correct
6 Correct 28 ms 29056 KB Output is correct
7 Correct 28 ms 29056 KB Output is correct
8 Correct 26 ms 29028 KB Output is correct
9 Correct 28 ms 29952 KB Output is correct
10 Correct 28 ms 29824 KB Output is correct
11 Correct 28 ms 29944 KB Output is correct
12 Correct 28 ms 29816 KB Output is correct
13 Correct 28 ms 29824 KB Output is correct
14 Correct 42 ms 33912 KB Output is correct
15 Correct 47 ms 34048 KB Output is correct
16 Correct 46 ms 34196 KB Output is correct
17 Correct 46 ms 34176 KB Output is correct
18 Correct 49 ms 34680 KB Output is correct
19 Correct 54 ms 35328 KB Output is correct
20 Correct 50 ms 35320 KB Output is correct
21 Correct 42 ms 34040 KB Output is correct
22 Correct 64 ms 34168 KB Output is correct
23 Correct 48 ms 34176 KB Output is correct
24 Correct 517 ms 99928 KB Output is correct
25 Correct 984 ms 124928 KB Output is correct
26 Correct 755 ms 125508 KB Output is correct
27 Correct 718 ms 125552 KB Output is correct
28 Correct 426 ms 91896 KB Output is correct
29 Correct 450 ms 92940 KB Output is correct
30 Correct 500 ms 94108 KB Output is correct
31 Correct 55 ms 35320 KB Output is correct
32 Correct 728 ms 125272 KB Output is correct
33 Correct 26 ms 29056 KB Output is correct
34 Correct 28 ms 29952 KB Output is correct
35 Correct 590 ms 105884 KB Output is correct
36 Correct 27 ms 28928 KB Output is correct
37 Correct 41 ms 34296 KB Output is correct
38 Correct 383 ms 99576 KB Output is correct
39 Correct 353 ms 86408 KB Output is correct