Submission #394781

#	Time	Username	Problem	Language	Result	Execution time	Memory
394781		Nima_Naderi	Portals (BOI14_portals)	C++14	100 / 100	768 ms	219004 KiB

portals

//In the name of GOD
#include<bits/stdc++.h>
using namespace std;

//typedef long long ll;
typedef int ll;
const ll MXN = 1e6 + 5;
const ll MXK = 1e3 + 5;
const ll INF = 1e9;
ll n, m;
ll gin[MXN], Q[MXN], dis[MXN], nxt[4][MXN];
string s[MXK];
vector<ll> adj[MXN], lvl[MXN];
vector<pair<ll, ll>> G[MXN];
vector<pair<ll, ll>> dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
bool wall[4][MXN], vis[MXN];
inline ll Id(ll i, ll j){
	return i * m + j + 1;
}
inline bool check(ll x, ll y){
	return (0 <= x && x < n && 0 <= y && y < m);
}
void BFS0(){
	ll L = 0, R = -1;
	for(int i = 1; i <= n * m; i ++){
		if(!gin[i]) vis[i] = 1, Q[++ R] = i;
	}
	while(L < R){
		ll u = Q[L ++];
		for(auto v : adj[u]){
			if(!vis[v]){
				gin[v] = gin[u] + 1;
				Q[++ R] = v; vis[v] = 1;
			}
		}
	}
}
ll DIJ(ll src, ll snk){
	memset(vis, 0, sizeof vis);
	memset(dis, 31, sizeof dis);
	dis[src] = 0; lvl[0].push_back(src);
	for(int d = 0; d < MXN; d ++){
		for(auto u : lvl[d]){
			if(vis[u]) continue;
			if(u == snk) return d;
			vis[u] = 1;
			for(auto Pr : G[u]){
				ll v, w; tie(v, w) = Pr;
				if(!vis[v] && w + d < dis[v]){
					dis[v] = w + d;
					lvl[dis[v]].push_back(v);
				}
			}	
		}
	}
	return -1;
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
	cin >> n >> m; ll src, snk;
	for(int i = 0; i < n; i ++) cin >> s[i];
	for(int i = 0; i < n; i ++){
		for(int j = 0; j < m; j ++){
			ll u = Id(i, j); gin[u] = INF;
			if(s[i][j] == '#') continue;
			if(s[i][j] == 'S') src = Id(i, j);
			if(s[i][j] == 'C') snk = Id(i, j);
			for(int d = 0; d < 4; d ++){
				ll ip = i + dir[d].first, jp = j + dir[d].second;
				if(!check(ip, jp) || s[ip][jp] == '#') wall[d][u] = 1, gin[u] = 0;
				else adj[u].push_back(Id(ip, jp));	
			}
		}
	}
	for(int i = 0; i < n; i ++){
		for(int j = 0; j < m; j ++){
			if(s[i][j] == '#') continue;
			ll u = Id(i, j);
			nxt[2][u] = (wall[2][u] ? u : nxt[2][Id(i, j - 1)]);
		}
		for(int j = m - 1; ~j; j --){
			if(s[i][j] == '#') continue;
			ll u = Id(i, j);
			nxt[0][u] = (wall[0][u] ? u : nxt[0][Id(i, j + 1)]);
		}
	}
	for(int j = 0; j < m; j ++){
		for(int i = 0; i < n; i ++){
			if(s[i][j] == '#') continue;
			ll u = Id(i, j);
			nxt[3][u] = (wall[3][u] ? u : nxt[3][Id(i - 1, j)]);
		}
		for(int i = n - 1; ~i; i --){
			if(s[i][j] == '#') continue;
			ll u = Id(i, j);
			nxt[1][u] = (wall[1][u] ? u : nxt[1][Id(i + 1, j)]);
		}
	}
	BFS0();
	for(int i = 0; i < n; i ++){
		for(int j = 0; j < m; j ++){
			ll u = Id(i, j), v;
			for(int d = 0; d < 4; d  ++){
				v = nxt[d][u];
				if(v != u && v != Id(i + dir[d].first, j + dir[d].second)) G[u].push_back({v, gin[u] + 1});
			}
			for(auto v : adj[u]){
				G[u].push_back({v, 1});
			}
		}
	}
	cout << DIJ(src, snk) << '\n';
	return 0;
}
// N.N_2004
// THIS IS THE PAYOFF

Compilation message (stderr)

portals.cpp: In function 'int main()':
portals.cpp:112:27: warning: 'src' may be used uninitialized in this function [-Wmaybe-uninitialized]
  112 |  cout << DIJ(src, snk) << '\n';
      |                           ^~~~
portals.cpp:112:27: warning: 'snk' may be used uninitialized in this function [-Wmaybe-uninitialized]

• Subtask 1: 11 / 11
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 19 / 19
• Subtask 5: 30 / 30