Submission #5958

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
5958	2014-06-06T10:30:22 Z	model_code	Portals (BOI14_portals)	C++	100 / 100	428 ms	31788 KB

portals

/**
 * A valid solution for task PORTALS.
 *
 * Author: Daumilas Ardickas
 */

#include <queue>
#include <cstdio>

using namespace std;

#define MAX_N 1000

int R, C, i, j;
char lab[MAX_N][MAX_N]; //labyrinth
int dw[MAX_N][MAX_N]; //distances to walls
int wx[MAX_N][MAX_N][2], wy[MAX_N][MAX_N][2]; //wall coordinates
int t[MAX_N][MAX_N]; //time
int cx, cy;
queue< pair<int, int> > q;
priority_queue< pair<int, pair<int, int> > > q2;

void bfs(int x, int y) {
    if (x >= 0 && y >= 0 && x < C && y < R && dw[y][x] == -1) {
        if (j < 0 || j == C || i < 0 || i == R)
            dw[y][x] = 1;
        else
            dw[y][x] = dw[j][i] + 1;
        q.push(make_pair(x, y));
    }
}

void dijkstra(int x, int y, int d) {
    if (x >= 0 && y >= 0 && x < C && y < R && (t[y][x] == -1 || t[y][x] > t[j][i] + d) && lab[y][x] != '#') {
        t[y][x] = t[j][i] + d;
        q2.push(make_pair(-t[y][x], make_pair(x, y)));
    }
}

int main() {
    scanf("%d%d", &R, &C);
    for (j = 0; j < R; j++) {
        scanf(" %s", lab[j]);
        for (i = 0; i < C; i++) {
            dw[j][i] = -1;
            t[j][i] = -1;
            switch (lab[j][i]) {
                case 'S': {t[j][i] = 0; q2.push(make_pair(0, make_pair(i, j))); break;}
                case 'C': {cx = i; cy = j; break;}
                case '#': {dw[j][i] = 0; q.push(make_pair(i, j)); break;}
            }
        }
        q.push(make_pair(-1, j));
        q.push(make_pair(C, j));
    }
    for (i = 0; i < C; i++) {
        q.push(make_pair(i, -1));
        q.push(make_pair(i, R));
    }
    
    while (q.size()) {
        i = q.front().first;
        j = q.front().second;
        q.pop();
        bfs(i, j-1);
        bfs(i, j+1);
        bfs(i-1, j);
        bfs(i+1, j);
    }
    
    for (j = 0; j < R; j++)
        for (i = 0; i < C; i++) {
            wy[j][i][0] = (j == 0 || lab[j-1][i] == '#') ? j : wy[j-1][i][0];
            wx[j][i][0] = (i == 0 || lab[j][i-1] == '#') ? i : wx[j][i-1][0];
        }
        
    for (j = R-1; j >= 0; j--)
        for (i = C-1; i >= 0; i--) {
            wy[j][i][1] = (j == R-1 || lab[j+1][i] == '#') ? j : wy[j+1][i][1];
            wx[j][i][1] = (i == C-1 || lab[j][i+1] == '#') ? i : wx[j][i+1][1];
        }
    
    while (q2.size()) {
        i = q2.top().second.first;
        j = q2.top().second.second;
        q2.pop();
	if (lab[j][i] == 'C') break;
        dijkstra(i, j-1, 1);
        dijkstra(i, j+1, 1);
        dijkstra(i-1, j, 1);
        dijkstra(i+1, j, 1);
        dijkstra(wx[j][i][0], j, dw[j][i]);
        dijkstra(wx[j][i][1], j, dw[j][i]);
        dijkstra(i, wy[j][i][0], dw[j][i]);
        dijkstra(i, wy[j][i][1], dw[j][i]);
    }
    
    printf ("%d\n", t[cy][cx]);
}

Subtask #1
11.0 / 11.0

#	Verdict	Memory	Grader output
1	Correct	25656 KB	Output is correct
2	Correct	25656 KB	Output is correct
3	Correct	25656 KB	Output is correct
4	Correct	25656 KB	Output is correct
5	Correct	25656 KB	Output is correct
6	Correct	25656 KB	Output is correct
7	Correct	25656 KB	Output is correct
8	Correct	25656 KB	Output is correct
9	Correct	25656 KB	Output is correct
10	Correct	25656 KB	Output is correct

Subtask #2
20.0 / 20.0

#	Verdict	Memory	Grader output
1	Correct	25656 KB	Output is correct
2	Correct	25656 KB	Output is correct
3	Correct	25656 KB	Output is correct
4	Correct	25656 KB	Output is correct
5	Correct	25656 KB	Output is correct
6	Correct	25656 KB	Output is correct
7	Correct	25656 KB	Output is correct
8	Correct	25656 KB	Output is correct
9	Correct	25656 KB	Output is correct
10	Correct	25656 KB	Output is correct
11	Correct	25656 KB	Output is correct
12	Correct	25656 KB	Output is correct
13	Correct	25656 KB	Output is correct
14	Correct	25656 KB	Output is correct
15	Correct	25656 KB	Output is correct
16	Correct	25656 KB	Output is correct

Subtask #3
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	25656 KB	Output is correct
2	Correct	0 ms	25656 KB	Output is correct
3	Correct	0 ms	25656 KB	Output is correct
4	Correct	0 ms	25656 KB	Output is correct
5	Correct	8 ms	25788 KB	Output is correct
6	Correct	8 ms	25788 KB	Output is correct
7	Correct	8 ms	25788 KB	Output is correct
8	Correct	4 ms	25788 KB	Output is correct

Subtask #4
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	25656 KB	Output is correct
2	Correct	0 ms	25656 KB	Output is correct
3	Correct	0 ms	25656 KB	Output is correct
4	Correct	0 ms	25656 KB	Output is correct
5	Correct	0 ms	25656 KB	Output is correct
6	Correct	0 ms	25656 KB	Output is correct
7	Correct	0 ms	25656 KB	Output is correct
8	Correct	0 ms	25656 KB	Output is correct
9	Correct	0 ms	25656 KB	Output is correct
10	Correct	0 ms	25656 KB	Output is correct
11	Correct	0 ms	25656 KB	Output is correct
12	Correct	0 ms	25656 KB	Output is correct
13	Correct	0 ms	25656 KB	Output is correct
14	Correct	4 ms	25788 KB	Output is correct
15	Correct	0 ms	25788 KB	Output is correct
16	Correct	8 ms	25788 KB	Output is correct
17	Correct	4 ms	25784 KB	Output is correct
18	Correct	8 ms	25784 KB	Output is correct
19	Correct	4 ms	25656 KB	Output is correct
20	Correct	4 ms	25656 KB	Output is correct
21	Correct	8 ms	25788 KB	Output is correct
22	Correct	4 ms	25788 KB	Output is correct
23	Correct	4 ms	25788 KB	Output is correct
24	Correct	4 ms	25656 KB	Output is correct
25	Correct	0 ms	25656 KB	Output is correct
26	Correct	0 ms	25656 KB	Output is correct
27	Correct	0 ms	25656 KB	Output is correct
28	Correct	0 ms	25788 KB	Output is correct

Subtask #5
30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	25656 KB	Output is correct
2	Correct	0 ms	25656 KB	Output is correct
3	Correct	0 ms	25656 KB	Output is correct
4	Correct	0 ms	25656 KB	Output is correct
5	Correct	0 ms	25656 KB	Output is correct
6	Correct	0 ms	25656 KB	Output is correct
7	Correct	0 ms	25656 KB	Output is correct
8	Correct	0 ms	25656 KB	Output is correct
9	Correct	0 ms	25656 KB	Output is correct
10	Correct	0 ms	25656 KB	Output is correct
11	Correct	0 ms	25656 KB	Output is correct
12	Correct	0 ms	25656 KB	Output is correct
13	Correct	0 ms	25656 KB	Output is correct
14	Correct	8 ms	25788 KB	Output is correct
15	Correct	8 ms	25788 KB	Output is correct
16	Correct	4 ms	25788 KB	Output is correct
17	Correct	8 ms	25784 KB	Output is correct
18	Correct	0 ms	25784 KB	Output is correct
19	Correct	4 ms	25656 KB	Output is correct
20	Correct	8 ms	25656 KB	Output is correct
21	Correct	4 ms	25788 KB	Output is correct
22	Correct	4 ms	25788 KB	Output is correct
23	Correct	8 ms	25788 KB	Output is correct
24	Correct	272 ms	30336 KB	Output is correct
25	Correct	428 ms	25984 KB	Output is correct
26	Correct	72 ms	25656 KB	Output is correct
27	Correct	196 ms	25852 KB	Output is correct
28	Correct	168 ms	31128 KB	Output is correct
29	Correct	204 ms	31260 KB	Output is correct
30	Correct	208 ms	31260 KB	Output is correct
31	Correct	8 ms	25656 KB	Output is correct
32	Correct	324 ms	25656 KB	Output is correct
33	Correct	0 ms	25656 KB	Output is correct
34	Correct	0 ms	25656 KB	Output is correct
35	Correct	208 ms	28192 KB	Output is correct
36	Correct	0 ms	25656 KB	Output is correct
37	Correct	0 ms	25788 KB	Output is correct
38	Correct	124 ms	31788 KB	Output is correct
39	Correct	148 ms	30732 KB	Output is correct

Submission #5958

Compilation message

Subtask #1 11.0 / 11.0

Subtask #2 20.0 / 20.0

Subtask #3 20.0 / 20.0

Subtask #4 19.0 / 19.0

Subtask #5 30.0 / 30.0

Subtask #1
11.0 / 11.0

Subtask #2
20.0 / 20.0

Subtask #3
20.0 / 20.0

Subtask #4
19.0 / 19.0

Subtask #5
30.0 / 30.0