oj.uz

Submission #203434

# Submission time Handle Problem Language Result Execution time Memory
203434 2020-02-20T16:03:30 Z mdn2002 Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 1413 ms 121356 KB 
#include<bits/stdc++.h>
using namespace std;
char a[4050][4050];
int n,m,dis[4050][4050],xx[]={1,-1,0,0},yy[]={0,0,1,-1},ans;
int main()
{
    cin>>n>>m;
    for(int i=0; i<n; i++)cin>>a[i];
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)dis[i][j]=1e9;
    }
    deque<pair<int,int> >dq;
    dq.push_front({0,0});
    dis[0][0]=1;
    while(dq.size())
    {
        pair<int,int>pr=dq.front();
        dq.pop_front();
        int ox=pr.first,oy=pr.second;
        for(int i=0; i<4; i++)
        {
            int x=ox+xx[i],y=oy+yy[i];
            if(0<=x&&x<n&&0<=y&&y<m&&a[x][y]!='.')
            {
                int pls=0;
                if(a[ox][oy]!=a[x][y])pls++;
                if(dis[x][y]>dis[ox][oy]+pls)
                {
                    dis[x][y]=dis[ox][oy]+pls;
                    if(pls)dq.push_back({x,y});
                    else dq.push_front({x,y});
                }
            }
        }
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(a[i][j]!='.')ans=max(ans,dis[i][j]);
        }
    }
    cout<<ans;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 5496 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 5 ms 760 KB Output is correct
4 Correct 20 ms 5240 KB Output is correct
5 Correct 11 ms 3064 KB Output is correct
6 Correct 5 ms 504 KB Output is correct
7 Correct 5 ms 760 KB Output is correct
8 Correct 5 ms 764 KB Output is correct
9 Correct 6 ms 1144 KB Output is correct
10 Correct 10 ms 2680 KB Output is correct
11 Correct 9 ms 2168 KB Output is correct
12 Correct 15 ms 3064 KB Output is correct
13 Correct 12 ms 3064 KB Output is correct
14 Correct 11 ms 3064 KB Output is correct
15 Correct 29 ms 5624 KB Output is correct
16 Correct 31 ms 5496 KB Output is correct
17 Correct 26 ms 5368 KB Output is correct
18 Correct 20 ms 5240 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 31096 KB Output is correct
2 Correct 126 ms 17912 KB Output is correct
3 Correct 927 ms 81912 KB Output is correct
4 Correct 253 ms 32124 KB Output is correct
5 Correct 531 ms 61560 KB Output is correct
6 Correct 1396 ms 95620 KB Output is correct
7 Correct 23 ms 32504 KB Output is correct
8 Correct 24 ms 31100 KB Output is correct
9 Correct 10 ms 792 KB Output is correct
10 Correct 7 ms 504 KB Output is correct
11 Correct 23 ms 31864 KB Output is correct
12 Correct 6 ms 1656 KB Output is correct
13 Correct 122 ms 17912 KB Output is correct
14 Correct 73 ms 12024 KB Output is correct
15 Correct 75 ms 13224 KB Output is correct
16 Correct 57 ms 6648 KB Output is correct
17 Correct 303 ms 34428 KB Output is correct
18 Correct 270 ms 34168 KB Output is correct
19 Correct 247 ms 32248 KB Output is correct
20 Correct 211 ms 29944 KB Output is correct
21 Correct 552 ms 63620 KB Output is correct
22 Correct 532 ms 61816 KB Output is correct
23 Correct 569 ms 52216 KB Output is correct
24 Correct 525 ms 62840 KB Output is correct
25 Correct 1154 ms 81356 KB Output is correct
26 Correct 935 ms 121356 KB Output is correct
27 Correct 1242 ms 107668 KB Output is correct
28 Correct 1413 ms 94736 KB Output is correct
29 Correct 1391 ms 93064 KB Output is correct
30 Correct 1301 ms 96896 KB Output is correct
31 Correct 1094 ms 65360 KB Output is correct
32 Correct 1169 ms 95760 KB Output is correct