oj.uz

Submission #675333

# Submission time Handle Problem Language Result Execution time Memory
675333 2022-12-27T04:22:16 Z vjudge1 Portals (BOI14_portals) C++14
20 / 100
 6 ms 3412 KB 
#include <bits/stdc++.h>
using namespace std;

int R, C, i, j;
char lab[1005][1005];
int wx[1005][1005][2], wy[1005][1005][2];
int t[1005][1005];
int cx, cy;
queue< pair<int, int> > q;

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

int main()
{
    cin >> R >> C;

    for(int j = 0; j < R; j++)
    {
        for(int i = 0; i < C; i++) cin >> lab[j][i];

        for(int i = 0; i < C; i++)
        {
            t[j][i] = -1;
           if(lab[j][i] == 'S') {t[j][i] = 0; q.push(make_pair(i, j));}
           if(lab[j][i] == 'C') {cx = i; cy = j;}

        }
    }

    for(int j = 0; j < R; j++)
    for(int 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(int j = R-1; j >= 0; j--)
    for(int 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 (q.size() && t[cy][cx] == -1)
    {
        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);
        if (wx[j][i][0] == i || wx[j][i][1] == i || wy[j][i][0] == j || wy[j][i][1] == j)
        {
            bfs(wx[j][i][0], j);
            bfs(wx[j][i][1], j);
            bfs(i, wy[j][i][0]);
            bfs(i, wy[j][i][1]);
        }
    }

    cout << t[cy][cx];
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Incorrect 1 ms 340 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 980 KB Output is correct
10 Incorrect 1 ms 980 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

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

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 980 KB Output is correct
10 Incorrect 1 ms 980 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 980 KB Output is correct
10 Incorrect 1 ms 980 KB Output isn't correct
11 Halted 0 ms 0 KB -