Submission #235447

#	Time	Username	Problem	Language	Result	Execution time	Memory
235447		Atalasion	Portals (BOI14_portals)	C++14	100 / 100	803 ms	144812 KiB

portals

//khodaya khodet komak kon
#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#pragma GCC optimize ("Ofast")
#pragma GCC optimize("unroll-loops")


using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 1000 + 10;
const ll MOD = 1000000000 + 7;
const ll INF = 1000000010;
const ll LOG = 25;

char grid[N][N];
int dis[N][N], n, m, near[N][N];
int a[] = {0, 0, 1, -1};
int b[] = {1, -1, 0, 0};
vector<pair<pii, int>> G[N][N];
vi sat[N], sot[N];

bool isval(int x, int y){
	return (x > 0 && x <= n && y > 0 && y <= m && grid[x][y] != '#');
}

void BFS(){
	memset(near, 31, sizeof near);
	queue<pii> q;
	for (int i = 0; i <= n + 1; i++) for (int j = 0; j <= m + 1; j++){
		if (grid[i][j] == '#') near[i][j] = 0, q.push({i, j});
	}
	while (q.size()){
		pii fr = q.front();
		q.pop();
		for (int i = 0; i < 4; i++){
			if (isval(fr.F + a[i], fr.S + b[i])){
				int x = fr.F + a[i], y = fr.S + b[i];
				if (near[x][y] > near[fr.F][fr.S] + 1){
					near[x][y] = near[fr.F][fr.S] + 1;
					q.push({x, y});
				}
			}
		}
	}
}

void DJ(int x, int y){
	memset(dis, 31, sizeof dis);
	dis[x][y] = 0;
	set<pair<int, pii>> st;
	st.insert({0, {x, y}});
	while (st.size()){
		pair<int, pii> fr = *st.begin();
		st.erase(st.begin());
		for (auto u:G[fr.S.F][fr.S.S]){
			if (dis[u.F.F][u.F.S] > fr.F + u.S){
				st.erase({dis[u.F.F][u.F.S], {u.F.F, u.F.S}});
				dis[u.F.F][u.F.S] = fr.F + u.S;
				st.insert({dis[u.F.F][u.F.S], {u.F.F, u.F.S}});
			}
		}
	}
}

int32_t main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	int s1, s2, f1, f2;
	for (int i = 0; i <= m + 1; i++) grid[0][i] = '#', grid[n + 1][i] = '#';
	for (int i = 0; i <= n + 1; i++) grid[i][0] = '#', grid[i][m + 1] = '#';
	for (int i = 1; i <= m; i++) sot[i].pb(0), sot[i].pb(n + 1);
	for( int i = 1; i <= n; i++)sat[i].pb(0), sat[i].pb(m + 1);
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= m; j++){
			cin >> grid[i][j];
			if (grid[i][j] == '#'){
				sat[i].pb(j);
				sot[j].pb(i);
			}
			if (grid[i][j] == 'S') s1 = i, s2 = j;
			if (grid[i][j] == 'C') f1 = i, f2 = j;
		}
	} 
	for (int i = 1; i <= n; i++) sort(all(sat[i]));
	for (int i = 1; i <= m; i++) sort(all(sot[i]));
	BFS();
	for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++){
		if (grid[i][j] != '#'){
			for (int k = 0; k < 4; k++){
				if (isval(i + a[k], j + b[k])){
					G[i][j].pb({{i + a[k], j + b[k]}, 1});
				}
			}
			int x = lower_bound(all(sat[i]), j) - sat[i].begin();
			G[i][j].pb({{i, sat[i][x] - 1}, near[i][j]});
			G[i][j].pb({{i, sat[i][x - 1] + 1}, near[i][j]});
			x = lower_bound(all(sot[j]), i) - sot[j].begin();
			G[i][j].pb({{sot[j][x] - 1, j}, near[i][j]});
			G[i][j].pb({{sot[j][x - 1] + 1, j}, near[i][j]});
		}
	}
	DJ(s1, s2);
	cout << dis[f1][f2];








	return 0;
}

Compilation message (stderr)

portals.cpp: In function 'int32_t main()':
portals.cpp:110:4: warning: 's2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  DJ(s1, s2);
  ~~^~~~~~~~
portals.cpp:111:20: warning: 'f1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  cout << dis[f1][f2];
                    ^
portals.cpp:111:20: warning: 'f2' may be used uninitialized in this function [-Wmaybe-uninitialized]
portals.cpp:110:4: warning: 's1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  DJ(s1, s2);
  ~~^~~~~~~~

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