oj.uz

Submission #116019

# Submission time Handle Problem Language Result Execution time Memory
116019 2019-06-10T07:59:48 Z MAMBA Portals (BOI14_portals) C++17
0 / 100
 31 ms 32528 KB 
#include <bits/stdc++.h> 

using namespace std;

#define rep(i , j , k) for (int i = j; i < (int)k; i++)
#define pb push_back
#define mt make_tuple
#define all(x) x.begin(),x.end()

typedef long long ll;
typedef pair<int , int> pii;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef complex<ld> point;
typedef pair<ld , ld> pld;
typedef vector<ll> vi;

inline void fileIO(string s) {
	//	freopen((s + ".in").c_str(), "r", stdin);
	freopen((s + ".out").c_str(), "w", stdout);
}

template<class T , class S>
inline bool smin(T &a, S b) { return (T)b < a ? a = b , 1 : 0; }
template<class T , class S>
inline bool smax(T &a, S b) { return a < (T)b ? a = b , 1 : 0; }

constexpr int N = 1000 + 10;
constexpr int MOD = 1e9 + 7;

template<typename T>
inline T mod(T &v) { return v = (v % MOD + MOD) % MOD; }
template<typename S, typename T>
inline S add(S &l, T r) { return mod(l += r); }

int r, w, L[N][N] ,U[N][N], R[N][N], D[N][N], d1[N][N] , d2[N][N];
pii s , c;
int dx[4] = {1, 0 , -1, 0};
int dy[4] = {0 , 1 , 0 , -1};
pii q[N * N];
int ql, qr;
vector<pair<int , pii>> adj[N][N];
string arr[N];

inline bool valid(int x, int y) {
	return x >= 0 && y >= 0 && x < r && y < w && arr[x][y] != '#';
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> r >> w;

	rep(i , 0 , r) {
		cin >> arr[i];
		int id = find(all(arr[i]) , 'S') - arr[i].begin();
		if (id != w)
			s = {i , id };
		id = find(all(arr[i]) , 'C') - arr[i].begin();
		if (id != w)
			c = {i , id };
	}

	rep(i , 0 , r)
		rep(j , 0 , w) { 
			if (j == 0 && arr[i][j] != '#') L[i][j] = -1;
			else L[i][j] = (arr[i][j] == '#') ? j : L[i][j - 1];
		}
	rep(i , 0 , r)
		for (int j = w - 1; ~j; j--) {
			if (j == w - 1 && arr[i][j] != '#') R[i][j] = w;
			else	R[i][j] = (arr[i][j] == '#') ? j : R[i][j + 1];
		}
	rep(i , 0 , r)
		rep(j , 0 , w) {
			if (i == 0 && arr[i][j] != '#') U[i][j] = -1;
			else
			U[i][j] = (arr[i][j] == '#') ? i : U[i - 1][j];
		}
	for (int i = r - 1; ~i; i--)
		rep(j , 0 , w) { 
			if (i == r - 1 && arr[i][j] != '#') D[i][j] = r;
			else D[i][j] = (arr[i][j] == '#') ? j : D[i + 1][j];
	}
	memset(d1, 63, sizeof(d1));
	rep(i , 0 , r)
		rep(j , 0 , w)
		if (arr[i][j] != '#' && ( 
				L[i][j] + 1 == j || 
				R[i][j] - 1 == j ||
				U[i][j] + 1 == i ||
				D[i][j] - 1 == i)) {
			d1[i][j] = 1;
			q[qr++] = {i , j};
		}

	while (ql != qr) {
		pii me = q[ql++];
		rep(i , 0 , 4) {
			int x_ = me.first + dx[i];
			int y_ = me.second + dy[i];
			if (valid(x_ , y_) && d1[me.first][me.second] + 1 < d1[x_][y_]) {
				d1[x_][y_] = d1[me.first][me.second] + 1;
				q[qr++] = {x_ , y_};
			}
		}
	}

	rep(i , 0 , r) {
		rep(j , 0 , w) {
			rep(z , 0 , 4) {
				int x = i + dx[z];
				int y = j + dy[z];
				if (valid(x , y)) adj[i][j].pb({1 , {x , y}});
			}
		//	cout << d1[i][j] << ' ';
			adj[i][j].pb({d1[i][j] , {i , L[i][j] + 1}});
			adj[i][j].pb({d1[i][j] , {i , R[i][j] - 1}});
			adj[i][j].pb({d1[i][j] , {U[i][j] + 1 , j}});
			adj[i][j].pb({d1[i][j] , {D[i][j] - 1 , j}});
		}
	//	cout << endl;
}

	memset(d2, 63, sizeof(d2));

	d2[s.first][s.second] = 0;
	set<pair<int , pii>> st;
	st.insert({0 , {s.first , s.second}});
	while (!st.empty()) {
		int x , y;
		tie(x , y) = st.begin()->second;
		st.erase(st.begin());
		for (auto e : adj[x][y]) {
			int x_ = e.second.first;
			int y_ = e.second.second;
			if (d2[x][y] + e.first < d2[x_][y_]) {
				st.erase({d2[x_][y_] , {x_ , y_}});
				d2[x_][y_] = d2[x][y] + e.first;
				st.insert({d2[x_][y_] , {x_ , y_}});
			}
		}
	}	

	cout << d2[c.first][c.second] << endl;

	return 0;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 32376 KB Output is correct
2 Correct 28 ms 32416 KB Output is correct
3 Correct 28 ms 32504 KB Output is correct
4 Incorrect 29 ms 32384 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 32376 KB Output is correct
2 Correct 29 ms 32512 KB Output is correct
3 Correct 28 ms 32504 KB Output is correct
4 Incorrect 31 ms 32384 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 32376 KB Output is correct
2 Correct 28 ms 32504 KB Output is correct
3 Correct 29 ms 32528 KB Output is correct
4 Incorrect 29 ms 32504 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 32384 KB Output is correct
2 Correct 28 ms 32504 KB Output is correct
3 Correct 28 ms 32512 KB Output is correct
4 Incorrect 28 ms 32384 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 32380 KB Output is correct
2 Correct 28 ms 32512 KB Output is correct
3 Correct 29 ms 32512 KB Output is correct
4 Incorrect 29 ms 32400 KB Output isn't correct
5 Halted 0 ms 0 KB -