Submission #442548

#	Time	Username	Problem	Language	Result	Execution time	Memory
442548		hivakarami	Portals (BOI14_portals)	C++14	70 / 100	1109 ms	201624 KiB

portals

#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 + 2;
const int inf = 1e6 + 10;
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])
				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])
				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])
				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])
				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++)
		{
			if(!a[i][j])
				continue;
			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 / 11
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 19 / 19
• Subtask 5: 0 / 30