oj.uz

Submission #885039

# Submission time Handle Problem Language Result Execution time Memory
885039 2023-12-08T20:43:33 Z tigar Tracks in the Snow (BOI13_tracks) C++14
97.8125 / 100
 1596 ms 1048576 KB 
#include <bits/stdc++.h>

using namespace std;

int w, h, ans;
char snow[4001][4001];
int check[4001][4001];
queue<pair< pair<int, int>, int> >ord;
int brr=1;

void dfs(int x, int y, int br)
{
    //cout<<br<<"\n";
    if(x-1>0)
    {
        if(snow[x-1][y]==snow[x][y] and check[x-1][y]==0){check[x-1][y]=br; dfs(x-1, y, br);}
        else if(snow[x-1][y]!='.')
        {
            if(check[x-1][y]==0){ord.push({{x-1, y}, br+1});}
        }
        else if(snow[x-1][y]=='.')check[x-1][y]=-1;
    }
    if(x+1<=h)
    {
        if(snow[x][y]==snow[x+1][y] and check[x+1][y]==0){check[x+1][y]=br; dfs(x+1, y, br);}
        else if(snow[x+1][y]!='.')
        {
            if(check[x+1][y]==0){ord.push({{x+1, y}, br+1});}
        }
        else if(snow[x+1][y]=='.')check[x+1][y]=-1;
    }
    if(y-1>0)
    {
        if(snow[x][y]==snow[x][y-1] and check[x][y-1]==0){check[x][y-1]=br; dfs(x, y-1, br);}
        else if(snow[x][y-1]!='.')
        {
            if(check[x][y-1]==0){ord.push({{x, y-1}, br+1});}
        }
        else if(snow[x][y-1]=='.')check[x][y-1]=-1;
    }
    if(y+1<=w)
    {
        if(snow[x][y]==snow[x][y+1] and check[x][y+1]==0){check[x][y+1]=br; dfs(x, y+1, br);}
        else if(snow[x][y+1]!='.')
        {
            if(check[x][y+1]==0){ord.push({{x, y+1}, br+1});}
        }
        else if(snow[x][y+1]=='.')check[x][y+1]=-1;
    }
    return;
}

int main()
{
    cin>>h>>w;
    for(int i=1; i<=h; i++)
    {
        for(int j=1; j<=w; j++)cin>>snow[i][j];
    }
    ord.push({{1, 1}, 1});
    while(!ord.empty())
    {
        int xx=ord.front().first.first, yy=ord.front().first.second, bb=ord.front().second;
        ord.pop();
        if(!check[xx][yy])
        {
            check[xx][yy]=bb;
            dfs(xx, yy, bb);
            ans=max(ans, bb);
        }
    }
    //for(int i=1; i<=h; i++){for(int j=1; j<=w; j++)cout<<check[i][j]; cout<<endl;}
    cout<<ans;
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 9052 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 11 ms 9632 KB Output is correct
5 Correct 4 ms 3932 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2908 KB Output is correct
10 Correct 4 ms 5212 KB Output is correct
11 Correct 4 ms 4444 KB Output is correct
12 Correct 7 ms 4120 KB Output is correct
13 Correct 5 ms 3932 KB Output is correct
14 Correct 4 ms 3816 KB Output is correct
15 Correct 16 ms 7772 KB Output is correct
16 Correct 18 ms 9308 KB Output is correct
17 Correct 13 ms 10076 KB Output is correct
18 Correct 11 ms 9564 KB Output is correct

Subtask #2
67.8125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 32860 KB Output is correct
2 Correct 75 ms 22608 KB Output is correct
3 Correct 618 ms 86356 KB Output is correct
4 Correct 145 ms 41040 KB Output is correct
5 Correct 383 ms 71000 KB Output is correct
6 Correct 1043 ms 226444 KB Output is correct
7 Correct 11 ms 33624 KB Output is correct
8 Correct 10 ms 33108 KB Output is correct
9 Correct 4 ms 4956 KB Output is correct
10 Correct 2 ms 2396 KB Output is correct
11 Correct 10 ms 33288 KB Output is correct
12 Correct 2 ms 3164 KB Output is correct
13 Correct 74 ms 22612 KB Output is correct
14 Correct 43 ms 17356 KB Output is correct
15 Correct 40 ms 15444 KB Output is correct
16 Correct 34 ms 10588 KB Output is correct
17 Correct 191 ms 40240 KB Output is correct
18 Correct 158 ms 38436 KB Output is correct
19 Correct 151 ms 41240 KB Output is correct
20 Correct 136 ms 29520 KB Output is correct
21 Correct 356 ms 63060 KB Output is correct
22 Correct 379 ms 70928 KB Output is correct
23 Correct 358 ms 57616 KB Output is correct
24 Correct 344 ms 68504 KB Output is correct
25 Correct 670 ms 94724 KB Output is correct
26 Runtime error 1212 ms 1048576 KB Execution killed with signal 9
27 Correct 1383 ms 836520 KB Output is correct
28 Correct 1036 ms 226496 KB Output is correct
29 Correct 1027 ms 219196 KB Output is correct
30 Correct 1146 ms 407132 KB Output is correct
31 Correct 719 ms 77212 KB Output is correct
32 Correct 1596 ms 741196 KB Output is correct