oj.uz

Submission #530887

# Submission time Handle Problem Language Result Execution time Memory
530887 2022-02-27T04:36:12 Z hohohaha Portals (BOI14_portals) C++14
20 / 100
 25 ms 37452 KB 
#include<bits/stdc++.h> 
using namespace std; 
#define fori(i, a, b) for(int i = (int) (a); i <= (int) (b); i++) 
#define ford(i, a, b) for(int i = (int) (b); i >= (int) (a); i--) 
#define ii pair<int, int> 
#define fi first
#define se second
#define vi vector<int> 
#define eb emplace_back
#define sp ' '
#define endl '\n'
#define int long long
const int maxn = 1005, inf = LLONG_MAX / 100ll; 
int n, m, s, c; 
int grid[maxn][maxn]; 
bool adj[maxn][maxn];
int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1}; 
bool inside(int i, int j) { 
	return i >= 0 and j >= 0 and i < n and j < m; 
}
bool white(int i, int j) { 
	return inside(i, j) and !grid[i][j]; 
}
int to[maxn][maxn][4]; 
int get_to(int, int, int); 
vector<int> g[maxn * maxn]; 
int dis[maxn * maxn]; 
int get_to(int i, int j, int d) {
	if(to[i][j][d] == -1) {
		if(grid[i][j]) to[i][j][d] = -2; 
		else {
			int ti = i + dx[d], tj = j + dy[d]; 
			if(min(ti, tj) < 0 or max(ti - n, tj - m) >= 0 or grid[ti][tj]) { 
				to[i][j][d] = i * m + j; 
			}
			else to[i][j][d] = get_to(ti, tj, d); 
		}
	}
	return to[i][j][d]; 
}
signed main() { 
	ios_base::sync_with_stdio(0); 
	cin.tie(0); 
	cout.tie(0); 
	cin >> n >> m; 
	fori(i, 0, n - 1)  { 
		fori(j, 0, m - 1) { 
			char c; cin >> c; 
			if(c == '#') { 
				grid[i][j] = 1; 
			}
			else if(c == 'S') { 
				s = i * m + j; 
			}
			else if(c == 'C') { 
				::c = i * m + j; 
			}
		}
	}
	fori(i, 0, n - 1) { 
		fori(j, 0, m - 1) { 
			fori(d, 0, 3) { 
				int ti = i + dx[d], tj = j + dy[d]; 
				adj[i][j] |= !white(ti, tj); 
			}
		}
	}
	fori(i, 0, n - 1) { 
		fori(j, 0, m - 1) { 
			fori(d, 0, 3) { 
				to[i][j][d] = -1; 
			}
		}
	}
	fori(i, 0, n - 1) { 
		fori(j, 0, m - 1) { 
			fori(d, 0, 3) { 
				if(!grid[i][j]) {
					int temp = get_to(i, j, d); if(temp >= 0 and adj[i][j]) g[i * m + j].eb(temp); 
//					if(i == 3 and 	j == 2) { 
//						cout << adj[i][j] << endl << temp << endl; 
//					}
					int ti = i + dx[d], tj = j + dy[d]; 
					if(white(ti, tj) ) g[i * m + j].eb(ti * m + tj); 
				}
			}
		}
	}
	fill(dis, dis + maxn * maxn, inf); 
	dis[s] = 0; 
	queue<int> q; 
	q.emplace(s); 
	while(q.size()) { 
		int u = q.front(); q.pop(); 
//		cout << u / m << sp << u % m << sp << dis[u] << endl; 
		for(int v: g[u]) { 
			if(dis[v] > dis[u] + 1) { 
				dis[v] = dis[u] + 1; 
				q.emplace(v);
			}
		}
	}
	cout << dis[c]; 
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 31948 KB Output is correct
2 Correct 16 ms 31972 KB Output is correct
3 Correct 15 ms 31988 KB Output is correct
4 Correct 15 ms 31984 KB Output is correct
5 Correct 15 ms 31948 KB Output is correct
6 Correct 15 ms 31948 KB Output is correct
7 Correct 16 ms 31928 KB Output is correct
8 Correct 15 ms 31976 KB Output is correct
9 Correct 15 ms 31976 KB Output is correct
10 Incorrect 14 ms 31940 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 31844 KB Output is correct
2 Correct 15 ms 31988 KB Output is correct
3 Correct 14 ms 31988 KB Output is correct
4 Correct 16 ms 31996 KB Output is correct
5 Correct 16 ms 31948 KB Output is correct
6 Correct 15 ms 31980 KB Output is correct
7 Correct 17 ms 31980 KB Output is correct
8 Correct 18 ms 32044 KB Output is correct
9 Correct 16 ms 32428 KB Output is correct
10 Incorrect 16 ms 32588 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 31852 KB Output is correct
2 Correct 15 ms 31948 KB Output is correct
3 Correct 16 ms 32048 KB Output is correct
4 Correct 15 ms 31948 KB Output is correct
5 Correct 25 ms 37140 KB Output is correct
6 Correct 25 ms 37168 KB Output is correct
7 Correct 25 ms 37388 KB Output is correct
8 Correct 25 ms 37452 KB Output is correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 31848 KB Output is correct
2 Correct 16 ms 31984 KB Output is correct
3 Correct 16 ms 31948 KB Output is correct
4 Correct 15 ms 31948 KB Output is correct
5 Correct 15 ms 31984 KB Output is correct
6 Correct 17 ms 31988 KB Output is correct
7 Correct 15 ms 31948 KB Output is correct
8 Correct 15 ms 32020 KB Output is correct
9 Correct 16 ms 32396 KB Output is correct
10 Incorrect 15 ms 32588 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 31916 KB Output is correct
2 Correct 15 ms 31900 KB Output is correct
3 Correct 15 ms 31988 KB Output is correct
4 Correct 16 ms 31948 KB Output is correct
5 Correct 15 ms 32112 KB Output is correct
6 Correct 16 ms 31972 KB Output is correct
7 Correct 16 ms 31980 KB Output is correct
8 Correct 15 ms 31948 KB Output is correct
9 Correct 17 ms 32564 KB Output is correct
10 Incorrect 16 ms 32588 KB Output isn't correct
11 Halted 0 ms 0 KB -