oj.uz

Submission #250619

# Submission time Handle Problem Language Result Execution time Memory
250619 2020-07-18T14:21:35 Z opukittpceno_hhr Portals (BOI14_portals) C++17
100 / 100
 876 ms 127608 KB 
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>
#include <chrono>
#include <random>
#include <functional>

using namespace std;

const int N = 1010;
const int INF = 1e9 + 239;
const vector<int> dx = {1, -1, 0, 0};
const vector<int> dy = {0, 0, 1, -1};

int n, m;
int a[N][N];

int d[N * N];
vector<pair<int, int>> g[N * N];

int ok(int i, int j) {
	return 0 <= i && i < n && 0 <= j && j < m && !a[i][j];
}

int get(int i, int j) {
	return i * m + j;
}

void dij(int st) {
	fill(d, d + n * m, INF);
	d[st] = 0;
	set<pair<int, int>> s;
	s.insert({d[st], st});
	while (!s.empty()) {
		int v = s.begin()->second;
		s.erase(s.begin());
		for (auto [u, w] : g[v]) {
			if (d[u] > d[v] + w) {
				s.erase({d[u], u});
				d[u] = d[v] + w;
				s.insert({d[u], u});
			}
		}
	}
}

int cu[N][N];
int cd[N][N];
int cl[N][N];
int cr[N][N];

void init() {
	for (int i = 0; i < n; i++) {
		cl[i][0] = 0;
		for (int j = 1; j < m; j++) {
			if (!a[i][j]) {
				cl[i][j] = 1 + cl[i][j - 1];
			} else {
				cl[i][j] = 0;
			}
		}
		cr[i][m - 1] = 0;
		for (int j = m - 2; j >= 0; j--) {
			if (!a[i][j]) {
				cr[i][j] = 1 + cr[i][j + 1];
			} else {
				cr[i][j] = 0;
			}
		}
	}
	for (int j = 0; j < m; j++) {
		cu[0][j] = 0;
		for (int i = 1; i < n; i++) {
			if (!a[i][j]) {
				cu[i][j] = 1 + cu[i - 1][j]; 
			} else {
				cu[i][j] = 0;
			}
		}
		cd[n - 1][j] = 0;
		for (int i = n - 2; i >= 0; i--) {
			if (!a[i][j]) {
				cd[i][j] = 1 + cd[i + 1][j];
			} else {
				cd[i][j] = 0;
			}
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (!a[i][j]) {
				cl[i][j]--;
				cr[i][j]--;
				cu[i][j]--;
				cd[i][j]--;
			}
		}
	}
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> m;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			a[i][j] = 1;
		}
	}
	int si = -1;
	int sj = -1;
	int ci = -1;
	int cj = -1;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			char c;
			cin >> c;
			a[i][j] = (c == '#');
			if (c == 'S') {
				si = i;
				sj = j;
			}
			if (c == 'C') {
				ci = i;
				cj = j;
			}
		}
	}
	n += 2;
	m += 2;
	init();
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (a[i][j]) continue;
			int mn = min({cu[i][j], cd[i][j], cl[i][j], cr[i][j]});
			g[get(i, j)].push_back({get(i - cu[i][j], j), 1 + mn});
			g[get(i, j)].push_back({get(i + cd[i][j], j), 1 + mn});
			g[get(i, j)].push_back({get(i, j - cl[i][j]), 1 + mn});
			g[get(i, j)].push_back({get(i, j + cr[i][j]), 1 + mn});
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			for (int k = 0; k < 4; k++) {
				if (ok(i, j) && ok(i + dx[k], j + dy[k])) {
					g[get(i, j)].push_back({get(i + dx[k], j + dy[k]), 1});
				}
			}
		}
	}
	dij(get(si, sj));
	cout << d[get(ci, cj)] << endl;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 28288 KB Output is correct
2 Correct 16 ms 28544 KB Output is correct
3 Correct 16 ms 28544 KB Output is correct
4 Correct 19 ms 28416 KB Output is correct
5 Correct 15 ms 28544 KB Output is correct
6 Correct 17 ms 28544 KB Output is correct
7 Correct 18 ms 28544 KB Output is correct
8 Correct 18 ms 28500 KB Output is correct
9 Correct 19 ms 28416 KB Output is correct
10 Correct 16 ms 28416 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28288 KB Output is correct
2 Correct 18 ms 28544 KB Output is correct
3 Correct 15 ms 28544 KB Output is correct
4 Correct 18 ms 28416 KB Output is correct
5 Correct 15 ms 28544 KB Output is correct
6 Correct 18 ms 28544 KB Output is correct
7 Correct 16 ms 28544 KB Output is correct
8 Correct 16 ms 28544 KB Output is correct
9 Correct 19 ms 29312 KB Output is correct
10 Correct 18 ms 29312 KB Output is correct
11 Correct 17 ms 29312 KB Output is correct
12 Correct 20 ms 29312 KB Output is correct
13 Correct 21 ms 29312 KB Output is correct
14 Correct 18 ms 28416 KB Output is correct
15 Correct 20 ms 29312 KB Output is correct
16 Correct 18 ms 28408 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 28416 KB Output is correct
2 Correct 16 ms 28544 KB Output is correct
3 Correct 20 ms 28536 KB Output is correct
4 Correct 15 ms 28544 KB Output is correct
5 Correct 32 ms 33536 KB Output is correct
6 Correct 31 ms 33656 KB Output is correct
7 Correct 32 ms 33700 KB Output is correct
8 Correct 35 ms 33784 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28288 KB Output is correct
2 Correct 15 ms 28544 KB Output is correct
3 Correct 18 ms 28544 KB Output is correct
4 Correct 18 ms 28416 KB Output is correct
5 Correct 18 ms 28544 KB Output is correct
6 Correct 18 ms 28544 KB Output is correct
7 Correct 18 ms 28544 KB Output is correct
8 Correct 18 ms 28544 KB Output is correct
9 Correct 20 ms 29312 KB Output is correct
10 Correct 22 ms 29312 KB Output is correct
11 Correct 16 ms 29312 KB Output is correct
12 Correct 20 ms 29312 KB Output is correct
13 Correct 18 ms 29312 KB Output is correct
14 Correct 29 ms 33536 KB Output is correct
15 Correct 31 ms 33584 KB Output is correct
16 Correct 35 ms 33784 KB Output is correct
17 Correct 32 ms 33784 KB Output is correct
18 Correct 37 ms 34176 KB Output is correct
19 Correct 39 ms 34816 KB Output is correct
20 Correct 40 ms 34816 KB Output is correct
21 Correct 29 ms 33536 KB Output is correct
22 Correct 35 ms 33536 KB Output is correct
23 Correct 32 ms 33656 KB Output is correct
24 Correct 40 ms 34808 KB Output is correct
25 Correct 17 ms 28416 KB Output is correct
26 Correct 20 ms 29312 KB Output is correct
27 Correct 17 ms 28416 KB Output is correct
28 Correct 31 ms 33776 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 28288 KB Output is correct
2 Correct 18 ms 28544 KB Output is correct
3 Correct 19 ms 28544 KB Output is correct
4 Correct 16 ms 28464 KB Output is correct
5 Correct 16 ms 28544 KB Output is correct
6 Correct 16 ms 28544 KB Output is correct
7 Correct 16 ms 28544 KB Output is correct
8 Correct 16 ms 28544 KB Output is correct
9 Correct 18 ms 29312 KB Output is correct
10 Correct 21 ms 29312 KB Output is correct
11 Correct 18 ms 29312 KB Output is correct
12 Correct 20 ms 29312 KB Output is correct
13 Correct 18 ms 29312 KB Output is correct
14 Correct 33 ms 33528 KB Output is correct
15 Correct 32 ms 33656 KB Output is correct
16 Correct 32 ms 33792 KB Output is correct
17 Correct 33 ms 33784 KB Output is correct
18 Correct 34 ms 34176 KB Output is correct
19 Correct 38 ms 34816 KB Output is correct
20 Correct 36 ms 34816 KB Output is correct
21 Correct 29 ms 33536 KB Output is correct
22 Correct 35 ms 33536 KB Output is correct
23 Correct 32 ms 33656 KB Output is correct
24 Correct 477 ms 101880 KB Output is correct
25 Correct 876 ms 127100 KB Output is correct
26 Correct 679 ms 127608 KB Output is correct
27 Correct 641 ms 127608 KB Output is correct
28 Correct 369 ms 93816 KB Output is correct
29 Correct 416 ms 94972 KB Output is correct
30 Correct 441 ms 96024 KB Output is correct
31 Correct 37 ms 34816 KB Output is correct
32 Correct 679 ms 127384 KB Output is correct
33 Correct 16 ms 28416 KB Output is correct
34 Correct 16 ms 29396 KB Output is correct
35 Correct 492 ms 107772 KB Output is correct
36 Correct 21 ms 28408 KB Output is correct
37 Correct 28 ms 33880 KB Output is correct
38 Correct 365 ms 101412 KB Output is correct
39 Correct 309 ms 88312 KB Output is correct