oj.uz

Submission #46755

# Submission time Handle Problem Language Result Execution time Memory
46755 2018-04-22T19:49:44 Z Bruteforceman Portals (BOI14_portals) C++11
100 / 100
 340 ms 57764 KB 
#include "bits/stdc++.h"
using namespace std;
char s[1004][1004];
int d[1004][1004];
int dis[1004][1004];

const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};

typedef pair <int, int> pii;
const int inf = 1e9;
pii cell[4][1004][1004];
int n, m;

bool inside(int x, int y) {
	return (0 <= x && x < n) && (0 <= y && y < m);
}

struct node {
	int x, y;
	int dist;
	node () {}
	node (int x, int y, int dist) : x(x), y(y), dist(dist) {}
	bool operator < (node p) const {
		return dist > p.dist;
	}
};

int main(int argc, char const *argv[])
{
	scanf("%d %d", &n, &m);
	for(int i = 0; i < n; i++) {
		scanf("%s", s[i]);
	}
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			d[i][j] = inf;
		}
	}
	queue <pii> Q; 
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			if(s[i][j] == '#') continue;
			bool good = false;
			for(int x = 0; x < 4; x++) {
				int p = i + dx[x];
				int q = j + dy[x];
				if(!inside(p, q) || s[p][q] == '#') {
					good = true;
					break;
				}
			}
			if(good) {
				Q.push(pii(i, j));
				d[i][j] = 0;
			}
		}
	}
	while(!Q.empty()) {
		int x = Q.front().first;
		int y = Q.front().second;
		Q.pop();
		for(int i = 0; i < 4; i++) {
			int p = x + dx[i];
			int q = y + dy[i];
			if(d[p][q] > d[x][y] + 1 && s[p][q] != '#') {
				d[p][q] = d[x][y] + 1;
				Q.push(pii(p, q));
			}
		}
	}
	for(int x = 0; x < n; x++) {
		for(int y = 0; y < m; y++) {
			if(s[x][y] == '#') continue;
			if(inside(x-1, y) && s[x-1][y] != '#') {
				cell[0][x][y] = cell[0][x-1][y];
			} else cell[0][x][y] = pii(x, y);

			if(inside(x, y-1) && s[x][y-1] != '#') {
				cell[1][x][y] = cell[1][x][y-1];
			} else cell[1][x][y] = pii(x, y);
		}
	}
	for(int x = n-1; x >= 0; x--) {
		for(int y = m-1; y >= 0; y--) {
			if(s[x][y] == '#') continue;
			if(inside(x+1, y) && s[x+1][y] != '#') {
				cell[2][x][y] = cell[2][x+1][y];
			} else cell[2][x][y] = pii(x, y);

			if(inside(x, y+1) && s[x][y+1] != '#') {
				cell[3][x][y] = cell[3][x][y+1];
			} else cell[3][x][y] = pii(x, y);
		}
	}
	priority_queue <node> PQ;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			if(s[i][j] == 'S') {
				dis[i][j] = 0;
				PQ.push(node(i, j, 0));
			} else {
				dis[i][j] = inf;
			}
		}
	}
	while(!PQ.empty()) {
		node h = PQ.top();
		PQ.pop();
		for(int i = 0; i < 4; i++) {
			int x = h.x + dx[i];
			int y = h.y + dy[i];
			if(inside(x, y) && s[x][y] != '#') {
				if(dis[x][y] > 1 + dis[h.x][h.y]) {
					dis[x][y] = 1 + dis[h.x][h.y];
					PQ.push(node(x, y, dis[x][y]));
				}
			}
			int p = cell[i][h.x][h.y].first;
			int q = cell[i][h.x][h.y].second;
			if(dis[p][q] > dis[h.x][h.y] + d[h.x][h.y] + 1) {
				dis[p][q] = dis[h.x][h.y] + d[h.x][h.y] + 1;
				PQ.push(node(p, q, dis[p][q]));
			}
		}
	}
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			if(s[i][j] == 'C') {
				printf("%d\n", dis[i][j]);
			}
		}
	}
	return 0;
}

Compilation message

portals.cpp: In function 'int main(int, const char**)':
portals.cpp:31:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
portals.cpp:33:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", s[i]);
   ~~~~~^~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 616 KB Output is correct
3 Correct 6 ms 856 KB Output is correct
4 Correct 2 ms 856 KB Output is correct
5 Correct 2 ms 900 KB Output is correct
6 Correct 2 ms 908 KB Output is correct
7 Correct 3 ms 908 KB Output is correct
8 Correct 2 ms 952 KB Output is correct
9 Correct 2 ms 952 KB Output is correct
10 Correct 2 ms 952 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 952 KB Output is correct
2 Correct 2 ms 988 KB Output is correct
3 Correct 2 ms 1036 KB Output is correct
4 Correct 2 ms 1036 KB Output is correct
5 Correct 3 ms 1048 KB Output is correct
6 Correct 2 ms 1052 KB Output is correct
7 Correct 2 ms 1056 KB Output is correct
8 Correct 2 ms 1060 KB Output is correct
9 Correct 3 ms 2088 KB Output is correct
10 Correct 3 ms 2092 KB Output is correct
11 Correct 3 ms 2096 KB Output is correct
12 Correct 3 ms 2100 KB Output is correct
13 Correct 3 ms 2104 KB Output is correct
14 Correct 2 ms 2104 KB Output is correct
15 Correct 3 ms 2112 KB Output is correct
16 Correct 2 ms 2112 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2112 KB Output is correct
2 Correct 2 ms 2112 KB Output is correct
3 Correct 2 ms 2112 KB Output is correct
4 Correct 2 ms 2112 KB Output is correct
5 Correct 10 ms 7304 KB Output is correct
6 Correct 11 ms 7304 KB Output is correct
7 Correct 11 ms 7356 KB Output is correct
8 Correct 8 ms 7408 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7408 KB Output is correct
2 Correct 2 ms 7408 KB Output is correct
3 Correct 2 ms 7408 KB Output is correct
4 Correct 2 ms 7408 KB Output is correct
5 Correct 2 ms 7408 KB Output is correct
6 Correct 2 ms 7408 KB Output is correct
7 Correct 2 ms 7408 KB Output is correct
8 Correct 2 ms 7408 KB Output is correct
9 Correct 3 ms 7408 KB Output is correct
10 Correct 3 ms 7408 KB Output is correct
11 Correct 3 ms 7408 KB Output is correct
12 Correct 3 ms 7408 KB Output is correct
13 Correct 3 ms 7408 KB Output is correct
14 Correct 10 ms 7624 KB Output is correct
15 Correct 13 ms 7624 KB Output is correct
16 Correct 14 ms 7740 KB Output is correct
17 Correct 11 ms 7740 KB Output is correct
18 Correct 13 ms 7740 KB Output is correct
19 Correct 13 ms 7740 KB Output is correct
20 Correct 13 ms 7740 KB Output is correct
21 Correct 12 ms 7776 KB Output is correct
22 Correct 11 ms 7852 KB Output is correct
23 Correct 11 ms 7892 KB Output is correct
24 Correct 13 ms 7892 KB Output is correct
25 Correct 2 ms 7892 KB Output is correct
26 Correct 3 ms 7892 KB Output is correct
27 Correct 2 ms 7892 KB Output is correct
28 Correct 9 ms 7984 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7984 KB Output is correct
2 Correct 2 ms 7984 KB Output is correct
3 Correct 2 ms 7984 KB Output is correct
4 Correct 2 ms 7984 KB Output is correct
5 Correct 2 ms 7984 KB Output is correct
6 Correct 2 ms 7984 KB Output is correct
7 Correct 2 ms 7984 KB Output is correct
8 Correct 2 ms 7984 KB Output is correct
9 Correct 3 ms 7984 KB Output is correct
10 Correct 3 ms 7984 KB Output is correct
11 Correct 3 ms 7984 KB Output is correct
12 Correct 3 ms 7984 KB Output is correct
13 Correct 3 ms 7984 KB Output is correct
14 Correct 10 ms 8004 KB Output is correct
15 Correct 11 ms 8128 KB Output is correct
16 Correct 11 ms 8128 KB Output is correct
17 Correct 13 ms 8200 KB Output is correct
18 Correct 12 ms 8232 KB Output is correct
19 Correct 14 ms 8248 KB Output is correct
20 Correct 12 ms 8248 KB Output is correct
21 Correct 10 ms 8360 KB Output is correct
22 Correct 11 ms 8404 KB Output is correct
23 Correct 11 ms 8444 KB Output is correct
24 Correct 192 ms 43576 KB Output is correct
25 Correct 340 ms 44664 KB Output is correct
26 Correct 335 ms 45484 KB Output is correct
27 Correct 279 ms 46452 KB Output is correct
28 Correct 154 ms 51988 KB Output is correct
29 Correct 173 ms 51988 KB Output is correct
30 Correct 209 ms 51988 KB Output is correct
31 Correct 12 ms 51988 KB Output is correct
32 Correct 270 ms 51988 KB Output is correct
33 Correct 2 ms 51988 KB Output is correct
34 Correct 3 ms 51988 KB Output is correct
35 Correct 208 ms 53156 KB Output is correct
36 Correct 2 ms 53156 KB Output is correct
37 Correct 8 ms 53156 KB Output is correct
38 Correct 133 ms 57764 KB Output is correct
39 Correct 148 ms 57764 KB Output is correct