oj.uz

Submission #862600

# Submission time Handle Problem Language Result Execution time Memory
862600 2023-10-18T15:20:01 Z neodoomer Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 522 ms 141152 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define pi pair<int,int>
const int N=4010;
int n,m,vis[N][N],ans;
char g[N][N];
int dx[]={0,0,-1,1};
int dy[]={-1,1,0,0};
bool good (int i,int j)
{
    return (i>-1 && j>-1 && i<n && j<m && g[i][j]!='.');
}
int main()
{

    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            cin>>g[i][j];
    memset(vis,-1,sizeof vis);
    deque<pi> dq;
    dq.pb({0,0});vis[0][0]=0;
    while(!dq.empty()){
        int i=dq.front().F,j=dq.front().S;
        ans=max(ans,vis[i][j]);
        dq.pop_front();
        for(int d=0;d<4;d++)
        {
            int ni=i+dx[d],nj=j+dy[d];
            if(!good(ni,nj) || vis[ni][nj]!=-1)continue;
            int w=(g[i][j]!=g[ni][nj]? 1:0);
            vis[ni][nj]=w+vis[i][j];
            if(w)dq.pb({ni,nj});
            else dq.push_front({ni,nj});
        }
    }
    cout<<ans+1;

    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 66904 KB Output is correct
2 Correct 8 ms 64600 KB Output is correct
3 Correct 9 ms 66652 KB Output is correct
4 Correct 13 ms 67032 KB Output is correct
5 Correct 10 ms 66652 KB Output is correct
6 Correct 8 ms 64468 KB Output is correct
7 Correct 8 ms 66652 KB Output is correct
8 Correct 8 ms 66652 KB Output is correct
9 Correct 8 ms 66652 KB Output is correct
10 Correct 9 ms 66652 KB Output is correct
11 Correct 9 ms 66844 KB Output is correct
12 Correct 11 ms 66936 KB Output is correct
13 Correct 9 ms 66780 KB Output is correct
14 Correct 11 ms 66652 KB Output is correct
15 Correct 16 ms 67088 KB Output is correct
16 Correct 16 ms 66904 KB Output is correct
17 Correct 15 ms 66996 KB Output is correct
18 Correct 12 ms 67152 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 78940 KB Output is correct
2 Correct 42 ms 72276 KB Output is correct
3 Correct 237 ms 91240 KB Output is correct
4 Correct 65 ms 75856 KB Output is correct
5 Correct 159 ms 84196 KB Output is correct
6 Correct 512 ms 107588 KB Output is correct
7 Correct 11 ms 79196 KB Output is correct
8 Correct 10 ms 78940 KB Output is correct
9 Correct 9 ms 64604 KB Output is correct
10 Correct 8 ms 64604 KB Output is correct
11 Correct 10 ms 78940 KB Output is correct
12 Correct 8 ms 66904 KB Output is correct
13 Correct 46 ms 71960 KB Output is correct
14 Correct 27 ms 69712 KB Output is correct
15 Correct 26 ms 69460 KB Output is correct
16 Correct 24 ms 67420 KB Output is correct
17 Correct 94 ms 75240 KB Output is correct
18 Correct 72 ms 75116 KB Output is correct
19 Correct 65 ms 75344 KB Output is correct
20 Correct 61 ms 75260 KB Output is correct
21 Correct 145 ms 81884 KB Output is correct
22 Correct 157 ms 81492 KB Output is correct
23 Correct 174 ms 79184 KB Output is correct
24 Correct 138 ms 81488 KB Output is correct
25 Correct 368 ms 87292 KB Output is correct
26 Correct 390 ms 141152 KB Output is correct
27 Correct 453 ms 114424 KB Output is correct
28 Correct 522 ms 107576 KB Output is correct
29 Correct 506 ms 106328 KB Output is correct
30 Correct 471 ms 107472 KB Output is correct
31 Correct 382 ms 89560 KB Output is correct
32 Correct 406 ms 107496 KB Output is correct