oj.uz

Submission #236151

# Submission time Handle Problem Language Result Execution time Memory
236151 2020-05-31T09:53:14 Z NONAME Portal (COCI17_portal) C++17
120 / 120
 39 ms 10752 KB 
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define sz(x) int(x.size())
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
#define N 100500
#define oo ll(1e16)
#define ft first
#define sd second
#define pb push_back
#define ppb pop_back
#define el '\n'
#define elf endl
#define base ll(1e9 + 7)
using namespace std;

typedef long long ll;
typedef long double ld;

queue <pair <int, pair <int, int> > > q;
ll lft[505][505], rgt[505][505], down[505][505], up[505][505], d[505][505], n, m, ex, ey;
char c[505][505];

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

	cin >> n >> m;

	for (int i = 0; i < n; i++)
	for (int j = 0; j < m; j++)
		d[i][j] = 1e9;

	for (int i = 0; i < n; i++)
	for (int j = 0; j < m; j++) {
		cin >> c[i][j];

		if (c[i][j] == 'C')
            q.push({0, {i, j}}), d[i][j] = 0;

		if (c[i][j] == 'F')
			ex = i, ey = j;
	}

	for (int i = 0; i < n; i++) {
		int lst = m;
		for (int j = m - 1; j >= 0; j--)
			if (c[i][j] == '#') lst = j - 1;
				else rgt[i][j] = lst;

		lst = 0;
		for (int j = 0; j < m; j++)
			if (c[i][j] == '#') lst = j + 1;
				else lft[i][j] = lst;
	}

	for (int j = 0; j < m; j++) {
        int lst = n;
        for (int i = n - 1; i >= 0; i--)
			if (c[i][j] == '#') lst = i - 1;
				else down[i][j] = lst;

		lst = 0;
		for (int i = 0; i < n; i++)
			if (c[i][j] == '#') lst = i + 1;
				else up[i][j] = lst;
	}

    while (!q.empty()) {
		int dist = q.front().ft, x = q.front().sd.ft, y = q.front().sd.sd;
		q.pop();

		dist = d[x][y];

        int steps[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
        for (int i = 0; i < 4; i++) {
            int cx = x + steps[i][0];
            int cy = y + steps[i][1];

            if (c[cx][cy] != '#')
				if (dist + 1 < d[cx][cy]) {
					d[cx][cy] = dist + 1;
					q.push({d[cx][cy], {cx, cy}});
				}
        }

        int rast, cx, cy;

        /// UP
        {
        	rast = x - up[x][y] + 1;

			cx = down[x][y], cy = y;
            if (dist + rast < d[cx][cy]) {
				d[cx][cy] = dist + rast;
                q.push({d[cx][cy], {cx, cy}});
            }

            cx = x, cy = lft[x][y];
			if (dist + rast < d[cx][cy]) {
				d[cx][cy] = dist + rast;
                q.push({d[cx][cy], {cx, cy}});
            }

            cx = x, cy = rgt[x][y];
            if (dist + rast < d[cx][cy]) {
				d[cx][cy] = dist + rast;
                q.push({d[cx][cy], {cx, cy}});
            }
        }

        /// DOWN
        {
			rast = down[x][y] - x + 1;

			cx = up[x][y], cy = y;
            if (dist + rast < d[cx][cy]) {
				d[cx][cy] = dist + rast;
                q.push({d[cx][cy], {cx, cy}});
            }

            cx = x, cy = lft[x][y];
			if (dist + rast < d[cx][cy]) {
				d[cx][cy] = dist + rast;
                q.push({d[cx][cy], {cx, cy}});
            }

            cx = x, cy = rgt[x][y];
            if (dist + rast < d[cx][cy]) {
				d[cx][cy] = dist + rast;
                q.push({d[cx][cy], {cx, cy}});
            }
        }

        /// LEFT
        {
			rast = y - lft[x][y] + 1;

			cx = up[x][y], cy = y;
            if (dist + rast < d[cx][cy]) {
				d[cx][cy] = dist + rast;
                q.push({d[cx][cy], {cx, cy}});
            }

            cx = down[x][y], cy = y;
			if (dist + rast < d[cx][cy]) {
				d[cx][cy] = dist + rast;
                q.push({d[cx][cy], {cx, cy}});
            }

            cx = x, cy = rgt[x][y];
            if (dist + rast < d[cx][cy]) {
				d[cx][cy] = dist + rast;
                q.push({d[cx][cy], {cx, cy}});
            }
        }

        /// RIGHT
        {
			rast = rgt[x][y] - y + 1;

			cx = up[x][y], cy = y;
            if (dist + rast < d[cx][cy]) {
				d[cx][cy] = dist + rast;
                q.push({d[cx][cy], {cx, cy}});
            }

            cx = down[x][y], cy = y;
			if (dist + rast < d[cx][cy]) {
				d[cx][cy] = dist + rast;
                q.push({d[cx][cy], {cx, cy}});
            }

            cx = x, cy = lft[x][y];
            if (dist + rast < d[cx][cy]) {
				d[cx][cy] = dist + rast;
                q.push({d[cx][cy], {cx, cy}});
            }
        }
    }

	if (d[ex][ey] == 1e9) cout << "nemoguce";
		else cout << d[ex][ey];
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 512 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 5 ms 640 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 5 ms 640 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4352 KB Output is correct
2 Correct 6 ms 2432 KB Output is correct
3 Correct 7 ms 2304 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 3456 KB Output is correct
2 Correct 8 ms 4480 KB Output is correct
3 Correct 8 ms 2816 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 8192 KB Output is correct
2 Correct 18 ms 5504 KB Output is correct
3 Correct 16 ms 6428 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 9600 KB Output is correct
2 Correct 17 ms 10624 KB Output is correct
3 Correct 20 ms 6656 KB Output is correct
4 Correct 19 ms 8576 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 10752 KB Output is correct
2 Correct 18 ms 10752 KB Output is correct
3 Correct 29 ms 10624 KB Output is correct
4 Correct 30 ms 10752 KB Output is correct