oj.uz

Submission #442544

# Submission time Handle Problem Language Result Execution time Memory
442544 2021-07-08T07:31:44 Z hivakarami Portals (BOI14_portals) C++14
70 / 100
 1000 ms 236456 KB 
#include<bits/stdc++.h>

 
using namespace std;
 
typedef long long int ll;
typedef long double ld;
#define f first
#define s second
#define pb push_back
#define pii pair<int, int>

 
const int N = 1000 + 5;
const int inf = 1e8;
const ll mod = 924844033;
const int lg = 20;


int n, m;
int dis[N][N], d[N][N];
pii U[N][N], D[N][N], L[N][N], R[N][N];
set<pair<int, pii>> s;
vector<pair<pii, int>> adj[N][N];
bool a[N][N];

inline void dij()
{
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < m; j++)
		{
			s.insert({dis[i][j], {i, j}});
		}
	}
	
	
	while(s.size())
	{
		int i = s.begin()->s.f, j = s.begin()->s.s;
		s.erase(s.begin());
		
		for(auto it : adj[i][j])
		{
			int x = it.f.f, y = it.f.s, w = it.s; 
			if(dis[x][y] > w + dis[i][j])
			{
				s.erase({dis[x][y], {x, y}});
				dis[x][y] = dis[i][j] + w;
				s.insert({dis[x][y], {x, y}});
			}
		}
	}
	
}


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


	cin >> n >> m;
	pii C;
	for(int i = 0; i < n; i++)
	{
		string tmp;
		cin >> tmp;
		for(int j = 0; j < m; j++)
		{
			
			dis[i][j] = d[i][j] = inf;
			if(tmp[j] == 'S')
				dis[i][j] = 0;
			else if(tmp[j] == 'C')
				C = {i, j};
				
			a[i][j] = (tmp[j] != '#');	
		}
	}
	
	
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < m; j++)
		{
			if(j == 0 || a[i][j-1] == 0)
				U[i][j] = {i, j};
			else
				U[i][j] = U[i][j-1];
				
				
			d[i][j] = min(d[i][j], j - U[i][j].s);	
		}
		
		
		for(int j = m-1; j >= 0; j--)
		{
			if(j == m-1 || a[i][j+1] == 0)
				D[i][j] = {i, j};
			else
				D[i][j] = D[i][j+1];
				
			d[i][j] = min(d[i][j], D[i][j].s - j);		
		}
	}
	
	
	for(int j = 0; j < m; j++)
	{
		//cout << j << '\n';	
		for(int i = 0; i < n; i++)
		{
			if(i == 0 || a[i-1][j] == 0)
				L[i][j] = {i, j};
			else
				L[i][j] = L[i-1][j];
			
			d[i][j] = min(d[i][j], i - L[i][j].f);
				
		}
		
		for(int i = n-1; i >= 0; i--)
		{	
			if(i == n-1 || a[i+1][j] == 0)
				R[i][j] = {i, j};
			else
				R[i][j] = R[i+1][j];
			
			d[i][j] = min(d[i][j], R[i][j].f - i);
		}
	}
	
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < m; j++)
		{
			
			adj[i][j].pb({U[i][j], d[i][j] + 1});
			adj[i][j].pb({D[i][j], d[i][j] + 1});
			adj[i][j].pb({L[i][j], d[i][j] + 1});
			adj[i][j].pb({R[i][j], d[i][j] + 1});
			
			if(i > 0 && a[i-1][j])
				adj[i][j].pb({{i-1, j}, 1});
			
			if(j > 0 && a[i][j-1])
				adj[i][j].pb({{i, j-1}, 1});
				
			if(i < n-1 && a[i+1][j])
				adj[i][j].pb({{i+1, j}, 1});
			
			if(j < m-1 && a[i][j+1])
				adj[i][j].pb({{i, j+1}, 1});
				
				
			//cout << i << ' ' << j << endl;	
				
		}
	}
	
	
	dij();
	
	cout << dis[C.f][C.s];
		


	return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 24012 KB Output is correct
2 Correct 18 ms 24284 KB Output is correct
3 Correct 16 ms 24300 KB Output is correct
4 Correct 18 ms 24092 KB Output is correct
5 Correct 16 ms 24304 KB Output is correct
6 Correct 17 ms 24524 KB Output is correct
7 Correct 16 ms 24268 KB Output is correct
8 Correct 16 ms 24260 KB Output is correct
9 Correct 16 ms 24124 KB Output is correct
10 Correct 18 ms 24124 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 24048 KB Output is correct
2 Correct 16 ms 24304 KB Output is correct
3 Correct 16 ms 24308 KB Output is correct
4 Correct 16 ms 24148 KB Output is correct
5 Correct 19 ms 24292 KB Output is correct
6 Correct 16 ms 24268 KB Output is correct
7 Correct 16 ms 24260 KB Output is correct
8 Correct 16 ms 24268 KB Output is correct
9 Correct 19 ms 25708 KB Output is correct
10 Correct 18 ms 25700 KB Output is correct
11 Correct 19 ms 25804 KB Output is correct
12 Correct 19 ms 25824 KB Output is correct
13 Correct 18 ms 25708 KB Output is correct
14 Correct 16 ms 24144 KB Output is correct
15 Correct 18 ms 25736 KB Output is correct
16 Correct 16 ms 24044 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 24052 KB Output is correct
2 Correct 16 ms 24268 KB Output is correct
3 Correct 19 ms 24336 KB Output is correct
4 Correct 17 ms 24304 KB Output is correct
5 Correct 54 ms 37116 KB Output is correct
6 Correct 54 ms 37192 KB Output is correct
7 Correct 55 ms 37140 KB Output is correct
8 Correct 50 ms 37204 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 24012 KB Output is correct
2 Correct 16 ms 24268 KB Output is correct
3 Correct 16 ms 24260 KB Output is correct
4 Correct 16 ms 24104 KB Output is correct
5 Correct 16 ms 24268 KB Output is correct
6 Correct 16 ms 24220 KB Output is correct
7 Correct 16 ms 24244 KB Output is correct
8 Correct 17 ms 24304 KB Output is correct
9 Correct 18 ms 25804 KB Output is correct
10 Correct 20 ms 25708 KB Output is correct
11 Correct 19 ms 25828 KB Output is correct
12 Correct 18 ms 25804 KB Output is correct
13 Correct 19 ms 25828 KB Output is correct
14 Correct 54 ms 37184 KB Output is correct
15 Correct 54 ms 37160 KB Output is correct
16 Correct 58 ms 37204 KB Output is correct
17 Correct 54 ms 37040 KB Output is correct
18 Correct 66 ms 37168 KB Output is correct
19 Correct 64 ms 37188 KB Output is correct
20 Correct 64 ms 37128 KB Output is correct
21 Correct 63 ms 37144 KB Output is correct
22 Correct 54 ms 37088 KB Output is correct
23 Correct 55 ms 37196 KB Output is correct
24 Correct 59 ms 37204 KB Output is correct
25 Correct 16 ms 24176 KB Output is correct
26 Correct 18 ms 25712 KB Output is correct
27 Correct 17 ms 24092 KB Output is correct
28 Correct 58 ms 37192 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 24012 KB Output is correct
2 Correct 16 ms 24304 KB Output is correct
3 Correct 16 ms 24268 KB Output is correct
4 Correct 17 ms 24140 KB Output is correct
5 Correct 16 ms 24232 KB Output is correct
6 Correct 16 ms 24244 KB Output is correct
7 Correct 16 ms 24268 KB Output is correct
8 Correct 16 ms 24268 KB Output is correct
9 Correct 18 ms 25736 KB Output is correct
10 Correct 18 ms 25772 KB Output is correct
11 Correct 19 ms 25700 KB Output is correct
12 Correct 19 ms 25832 KB Output is correct
13 Correct 18 ms 25712 KB Output is correct
14 Correct 62 ms 37108 KB Output is correct
15 Correct 56 ms 37188 KB Output is correct
16 Correct 59 ms 37200 KB Output is correct
17 Correct 54 ms 37032 KB Output is correct
18 Correct 56 ms 37080 KB Output is correct
19 Correct 62 ms 37200 KB Output is correct
20 Correct 61 ms 37184 KB Output is correct
21 Correct 67 ms 37140 KB Output is correct
22 Correct 66 ms 37124 KB Output is correct
23 Correct 57 ms 37168 KB Output is correct
24 Execution timed out 1103 ms 236456 KB Time limit exceeded
25 Halted 0 ms 0 KB -