oj.uz

Submission #105978

# Submission time Handle Problem Language Result Execution time Memory
105978 2019-04-16T03:31:49 Z xiaowuc1 Portals (BOI14_portals) C++14
100 / 100
 841 ms 117540 KB 
#include <algorithm>
#include <cassert>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> pipii;
typedef vector<vector<ll>> matrix;

int closestWall[1000][1000];
vector<pii> dests[1000][1000];
int dp[1000][1000];
vector<pii> locs[1000000];
string g[1000];
int r, c;
int dx[4]{-1,0,1,0};
int dy[4]{0,1,0,-1};

void relax(int x, int y) {
	// one move
	for(int k = 0; k < 4; k++) {
		int nx = x + dx[k];
		int ny = y + dy[k];
		if(nx < 0 || nx >= r || ny < 0 || ny >= c || g[nx][ny] == '#') continue;
		if(dp[nx][ny] > 1 + dp[x][y]) {
			dp[nx][ny] = 1 + dp[x][y];
			locs[dp[nx][ny]].push_back({nx, ny});
		}
	}
	// portal
	for(pii out: dests[x][y]) {
		int nt = dp[x][y] + closestWall[x][y] + 1;
		if(dp[out.first][out.second] > nt) {
			dp[out.first][out.second] = nt;
			locs[dp[out.first][out.second]].push_back({out.first, out.second});
		}
	}
}

void bfs() {
	for(int qq = 0; qq < r*c; qq++) {
		for(pii out: locs[qq]) {
			if(dp[out.first][out.second] != qq) continue;
			relax(out.first, out.second);
		}
	}
}

void solve() {
	cin >> r >> c;
	for(int i = 0; i < r; i++) cin >> g[i];
	for(int i = 0; i < r; i++) {
		for(int j = 0; j < c; j++) {
			if(g[i][j] == 'S') {
				locs[0].push_back({i, j});
			}
			else {
				dp[i][j] = 1 << 25;
			}
			closestWall[i][j] = 1 << 25;
		}
	}
	for(int j = 0; j < c; j++) {
		int currDist = 0;
		for(int i = 0; i < r; i++) {
			if(g[i][j] == '#') {
				currDist = 0;
			}
			else {
				dests[i][j].push_back({i-currDist, j});
				closestWall[i][j] = min(closestWall[i][j], currDist++);
			}
		}
	}
	for(int j = 0; j < c; j++) {
		int currDist = 0;
		for(int i = r-1; i >= 0; i--) {
			if(g[i][j] == '#') {
				currDist = 0;
			}
			else {
				dests[i][j].push_back({i+currDist, j});
				closestWall[i][j] = min(closestWall[i][j], currDist++);
			}
		}
	}
	for(int i = 0; i < r; i++) {
		int currDist = 0;
		for(int j = 0; j < c; j++) {
			if(g[i][j] == '#') {
				currDist = 0;
			}
			else {
				dests[i][j].push_back({i, j-currDist});
				closestWall[i][j] = min(closestWall[i][j], currDist++);
			}
		}
	}
	for(int i = 0; i < r; i++) {
		int currDist = 0;
		for(int j = c-1; j >= 0; j--) {
			if(g[i][j] == '#') {
				currDist = 0;
			}
			else {
				dests[i][j].push_back({i, j+currDist});
				closestWall[i][j] = min(closestWall[i][j], currDist++);
			}
		}
	}
	bfs();
	for(int i = 0; i < r; i++) {
		for(int j = 0; j < c; j++) {
			if(g[i][j] == 'C') {
				cout << dp[i][j] << endl;
				return;
			}
		}
	}
}


int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
	/*
  int t;
  cin >> t;
  for(int i = 1; i <= t; i++) {
    cout << "Case #" << i << ": ";
    solve();
  }
	*/
	solve();
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 47480 KB Output is correct
2 Correct 46 ms 47480 KB Output is correct
3 Correct 45 ms 47480 KB Output is correct
4 Correct 53 ms 47356 KB Output is correct
5 Correct 51 ms 47480 KB Output is correct
6 Correct 50 ms 47356 KB Output is correct
7 Correct 50 ms 47360 KB Output is correct
8 Correct 50 ms 47352 KB Output is correct
9 Correct 50 ms 47352 KB Output is correct
10 Correct 51 ms 47352 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 47428 KB Output is correct
2 Correct 50 ms 47488 KB Output is correct
3 Correct 47 ms 47352 KB Output is correct
4 Correct 49 ms 47356 KB Output is correct
5 Correct 51 ms 47452 KB Output is correct
6 Correct 48 ms 47356 KB Output is correct
7 Correct 53 ms 47480 KB Output is correct
8 Correct 51 ms 47480 KB Output is correct
9 Correct 51 ms 47864 KB Output is correct
10 Correct 49 ms 47864 KB Output is correct
11 Correct 47 ms 47864 KB Output is correct
12 Correct 48 ms 47868 KB Output is correct
13 Correct 49 ms 47868 KB Output is correct
14 Correct 46 ms 47324 KB Output is correct
15 Correct 50 ms 47864 KB Output is correct
16 Correct 48 ms 47360 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 47428 KB Output is correct
2 Correct 51 ms 47352 KB Output is correct
3 Correct 47 ms 47488 KB Output is correct
4 Correct 53 ms 47560 KB Output is correct
5 Correct 70 ms 50468 KB Output is correct
6 Correct 62 ms 50432 KB Output is correct
7 Correct 63 ms 50552 KB Output is correct
8 Correct 64 ms 51192 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 47284 KB Output is correct
2 Correct 44 ms 47352 KB Output is correct
3 Correct 47 ms 47348 KB Output is correct
4 Correct 48 ms 47352 KB Output is correct
5 Correct 49 ms 47352 KB Output is correct
6 Correct 54 ms 47352 KB Output is correct
7 Correct 51 ms 47352 KB Output is correct
8 Correct 50 ms 47352 KB Output is correct
9 Correct 51 ms 47992 KB Output is correct
10 Correct 53 ms 47992 KB Output is correct
11 Correct 51 ms 47864 KB Output is correct
12 Correct 49 ms 47864 KB Output is correct
13 Correct 51 ms 47864 KB Output is correct
14 Correct 62 ms 50428 KB Output is correct
15 Correct 62 ms 50552 KB Output is correct
16 Correct 64 ms 50552 KB Output is correct
17 Correct 62 ms 50552 KB Output is correct
18 Correct 62 ms 50808 KB Output is correct
19 Correct 62 ms 51448 KB Output is correct
20 Correct 70 ms 51448 KB Output is correct
21 Correct 61 ms 50500 KB Output is correct
22 Correct 61 ms 50424 KB Output is correct
23 Correct 62 ms 50552 KB Output is correct
24 Correct 64 ms 51448 KB Output is correct
25 Correct 46 ms 47480 KB Output is correct
26 Correct 52 ms 47864 KB Output is correct
27 Correct 57 ms 47356 KB Output is correct
28 Correct 66 ms 51068 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 47360 KB Output is correct
2 Correct 54 ms 47552 KB Output is correct
3 Correct 49 ms 47480 KB Output is correct
4 Correct 60 ms 47352 KB Output is correct
5 Correct 57 ms 47480 KB Output is correct
6 Correct 56 ms 47356 KB Output is correct
7 Correct 49 ms 47480 KB Output is correct
8 Correct 54 ms 47428 KB Output is correct
9 Correct 53 ms 47864 KB Output is correct
10 Correct 53 ms 47992 KB Output is correct
11 Correct 51 ms 47864 KB Output is correct
12 Correct 58 ms 47760 KB Output is correct
13 Correct 49 ms 47864 KB Output is correct
14 Correct 92 ms 50368 KB Output is correct
15 Correct 71 ms 50552 KB Output is correct
16 Correct 66 ms 50680 KB Output is correct
17 Correct 61 ms 50552 KB Output is correct
18 Correct 68 ms 50780 KB Output is correct
19 Correct 74 ms 51320 KB Output is correct
20 Correct 82 ms 51448 KB Output is correct
21 Correct 64 ms 50552 KB Output is correct
22 Correct 68 ms 50412 KB Output is correct
23 Correct 72 ms 50552 KB Output is correct
24 Correct 552 ms 98704 KB Output is correct
25 Correct 841 ms 116072 KB Output is correct
26 Correct 741 ms 117240 KB Output is correct
27 Correct 723 ms 117112 KB Output is correct
28 Correct 486 ms 93432 KB Output is correct
29 Correct 501 ms 93692 KB Output is correct
30 Correct 546 ms 94456 KB Output is correct
31 Correct 63 ms 51320 KB Output is correct
32 Correct 797 ms 117540 KB Output is correct
33 Correct 45 ms 47356 KB Output is correct
34 Correct 46 ms 47864 KB Output is correct
35 Correct 604 ms 102392 KB Output is correct
36 Correct 45 ms 47360 KB Output is correct
37 Correct 57 ms 51064 KB Output is correct
38 Correct 579 ms 112228 KB Output is correct
39 Correct 508 ms 87128 KB Output is correct