oj.uz

Submission #959440

# Submission time Handle Problem Language Result Execution time Memory
959440 2024-04-08T08:19:06 Z AtinaR Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 1149 ms 252236 KB 
#include <bits/stdc++.h>

using namespace std;
const long long MAX=4001;
long long n,m;
char mat[MAX][MAX];
long long di[4]={0,0,-1,1};
long long dj[4]={1,-1,0,0};
long long vis[MAX][MAX];
bool valid_move(long long i, long long j)
{
    if(i<0 || i>=n || j<0 || j>=m || vis[i][j]!=0 || mat[i][j]=='.')return false;
    return true;
}
int main()
{
    cin>>n>>m;
    for(long long i=0; i<n; i++)
    {
        for(long long j=0; j<m; j++)
        {
            cin>>mat[i][j];
        }
    }
    deque<pair<long long,long long> > q;
    long long res=0;
    q.push_back({0,0});
    memset(vis,0,sizeof(vis));
    vis[0][0]=1;
    while(q.size())
    {
        pair<long long,long long> curr=q.front();
        q.pop_front();
        res=max(res,vis[curr.first][curr.second]);
        for(long long k=0; k<4; k++)
        {
            long long newi=curr.first+di[k];
            long long newj=curr.second+dj[k];
            if(!valid_move(newi,newj))continue;
            if(mat[newi][newj]==mat[curr.first][curr.second])
            {
                q.push_front({newi,newj});
                vis[newi][newj]=vis[curr.first][curr.second];
            }
            else
            {
                 q.push_back({newi,newj});
                 vis[newi][newj]=vis[curr.first][curr.second]+1;
            }
        }
    }
    cout<<res<<endl;
    return 0;
}
/*
5 8
FFR.....
.FRRR...
.FFFFF..
..RRRFFR
.....FFF*/

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 128180 KB Output is correct
2 Correct 49 ms 125772 KB Output is correct
3 Correct 52 ms 127684 KB Output is correct
4 Correct 53 ms 128080 KB Output is correct
5 Correct 51 ms 126800 KB Output is correct
6 Correct 43 ms 127824 KB Output is correct
7 Correct 42 ms 125764 KB Output is correct
8 Correct 42 ms 127624 KB Output is correct
9 Correct 48 ms 126036 KB Output is correct
10 Correct 46 ms 127716 KB Output is correct
11 Correct 54 ms 127812 KB Output is correct
12 Correct 56 ms 126768 KB Output is correct
13 Correct 55 ms 127904 KB Output is correct
14 Correct 58 ms 126904 KB Output is correct
15 Correct 97 ms 128080 KB Output is correct
16 Correct 140 ms 127984 KB Output is correct
17 Correct 58 ms 128092 KB Output is correct
18 Correct 52 ms 128280 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 140644 KB Output is correct
2 Correct 136 ms 133276 KB Output is correct
3 Correct 678 ms 157024 KB Output is correct
4 Correct 213 ms 137808 KB Output is correct
5 Correct 455 ms 146196 KB Output is correct
6 Correct 1100 ms 184176 KB Output is correct
7 Correct 55 ms 141396 KB Output is correct
8 Correct 52 ms 140628 KB Output is correct
9 Correct 51 ms 127824 KB Output is correct
10 Correct 48 ms 125780 KB Output is correct
11 Correct 52 ms 141136 KB Output is correct
12 Correct 48 ms 127824 KB Output is correct
13 Correct 138 ms 133480 KB Output is correct
14 Correct 91 ms 130644 KB Output is correct
15 Correct 90 ms 130644 KB Output is correct
16 Correct 80 ms 128296 KB Output is correct
17 Correct 260 ms 137884 KB Output is correct
18 Correct 240 ms 137636 KB Output is correct
19 Correct 211 ms 137804 KB Output is correct
20 Correct 198 ms 137300 KB Output is correct
21 Correct 417 ms 146844 KB Output is correct
22 Correct 427 ms 146088 KB Output is correct
23 Correct 443 ms 143668 KB Output is correct
24 Correct 408 ms 146800 KB Output is correct
25 Correct 903 ms 156832 KB Output is correct
26 Correct 957 ms 252236 KB Output is correct
27 Correct 1054 ms 200072 KB Output is correct
28 Correct 1122 ms 184296 KB Output is correct
29 Correct 1149 ms 178916 KB Output is correct
30 Correct 1084 ms 188508 KB Output is correct
31 Correct 729 ms 149072 KB Output is correct
32 Correct 1008 ms 189620 KB Output is correct