oj.uz

Submission #675787

# Submission time Handle Problem Language Result Execution time Memory
675787 2022-12-27T22:20:11 Z NONTAC Tracks in the Snow (BOI13_tracks) C++11
100 / 100
 1439 ms 118952 KB 
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> ii;

int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int n, m;
char grid[4002][4002];
int d[4002][4002];
int ans = 0;

bool same(char c1, char c2)
{
    if(c1 != c2) return true;
    return false;
}

void bfs(int si, int sj)
{
    deque<ii> dq;
    d[si][sj] = 1;
    dq.push_front(ii(si, sj));
    while(!dq.empty()){
        int ui = dq.front().first, uj = dq.front().second;
        dq.pop_front();
        ans = max(ans, d[ui][uj]);
        for(int i = 0; i < 4; i++){
            int vi = ui + dx[i], vj = uj + dy[i];
            int w = same(grid[ui][uj], grid[vi][vj]);
            if(vi < 1 || vi > n || vj < 1 || vj > m) continue;
            if(d[vi][vj] == 0 && grid[vi][vj] != '.'){
                d[vi][vj] = d[ui][uj] + w;
                if(w == 0){
                    dq.push_front(ii(vi, vj));
                }
                else{
                    dq.push_back(ii(vi, vj));
                }
            }
        }
    }
}

int main()
{
    //freopen("test.in","r",stdin);
    //freopen("test.out","w",stdout);

    cin>>n>>m;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin>>grid[i][j];
        }
    }

    bfs(1, 1);

    cout<<ans;

    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 5132 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 15 ms 4936 KB Output is correct
5 Correct 8 ms 2916 KB Output is correct
6 Correct 0 ms 468 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 2 ms 1108 KB Output is correct
10 Correct 6 ms 2388 KB Output is correct
11 Correct 4 ms 2004 KB Output is correct
12 Correct 10 ms 2900 KB Output is correct
13 Correct 7 ms 2772 KB Output is correct
14 Correct 7 ms 2868 KB Output is correct
15 Correct 22 ms 4948 KB Output is correct
16 Correct 23 ms 5168 KB Output is correct
17 Correct 21 ms 4876 KB Output is correct
18 Correct 15 ms 4948 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 30656 KB Output is correct
2 Correct 118 ms 13464 KB Output is correct
3 Correct 963 ms 57544 KB Output is correct
4 Correct 242 ms 29008 KB Output is correct
5 Correct 551 ms 44420 KB Output is correct
6 Correct 1340 ms 91812 KB Output is correct
7 Correct 18 ms 32084 KB Output is correct
8 Correct 18 ms 30676 KB Output is correct
9 Correct 5 ms 608 KB Output is correct
10 Correct 2 ms 320 KB Output is correct
11 Correct 18 ms 31444 KB Output is correct
12 Correct 3 ms 1492 KB Output is correct
13 Correct 113 ms 13484 KB Output is correct
14 Correct 66 ms 9392 KB Output is correct
15 Correct 69 ms 12128 KB Output is correct
16 Correct 49 ms 5084 KB Output is correct
17 Correct 289 ms 24704 KB Output is correct
18 Correct 261 ms 31692 KB Output is correct
19 Correct 236 ms 28928 KB Output is correct
20 Correct 214 ms 21992 KB Output is correct
21 Correct 561 ms 43604 KB Output is correct
22 Correct 546 ms 44492 KB Output is correct
23 Correct 556 ms 36124 KB Output is correct
24 Correct 550 ms 40928 KB Output is correct
25 Correct 1099 ms 78600 KB Output is correct
26 Correct 1237 ms 118952 KB Output is correct
27 Correct 1367 ms 96936 KB Output is correct
28 Correct 1439 ms 91740 KB Output is correct
29 Correct 1332 ms 89680 KB Output is correct
30 Correct 1327 ms 94340 KB Output is correct
31 Correct 870 ms 63500 KB Output is correct
32 Correct 1337 ms 94588 KB Output is correct