oj.uz

Submission #480361

# Submission time Handle Problem Language Result Execution time Memory
480361 2021-10-15T19:19:01 Z nafis_shifat Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 827 ms 139052 KB 
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int mxn=4000+5;
const int inf=1e9;
char a[mxn][mxn];
int dist[mxn][mxn];
int vis[mxn][mxn];
int di[]={0,0,-1,1};
int dj[]={-1,1,0,0};
int n, m ;

bool valid(int i, int j) {
    return 1 <= i && i <= n && 1 <= j && j <= m; 
}
int main() {
    cin >> n >> m;


    for(int i = 1; i <= n; i++) {
        scanf("%s", a[i] + 1);
    }   
    memset(dist, -1, sizeof dist); 

    dist[1][1] = 1;

    deque<pii> q;

    q.push_back({1, 1});
    int ans = 1;

    while(!q.empty()) {
        auto [i, j] = q.front();
        q.pop_front();

        if(vis[i][j]) continue;


        ans = max(ans, dist[i][j]);

        for(int k = 0; k < 4; k++) {
            int ii = i + di[k];
            int jj = j + dj[k];

            if(!valid(ii, jj) || a[ii][jj] == '.') continue;

            int c = (a[ii][jj] != a[i][j]);

            if(dist[ii][jj] == -1 || dist[ii][jj] > dist[i][j] + c) {
                dist[ii][jj] = dist[i][j] + c;
                if(c) q.push_back({ii, jj});
                else q.push_front({ii, jj});
            }
        }
    }

    cout<<ans<<endl;


}

Compilation message

tracks.cpp: In function 'int main()':
tracks.cpp:22:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |         scanf("%s", a[i] + 1);
      |         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 65220 KB Output is correct
2 Correct 27 ms 63048 KB Output is correct
3 Correct 27 ms 63192 KB Output is correct
4 Correct 37 ms 65292 KB Output is correct
5 Correct 32 ms 64268 KB Output is correct
6 Correct 27 ms 63172 KB Output is correct
7 Correct 28 ms 63216 KB Output is correct
8 Correct 27 ms 63308 KB Output is correct
9 Correct 29 ms 63388 KB Output is correct
10 Correct 31 ms 64076 KB Output is correct
11 Correct 30 ms 63900 KB Output is correct
12 Correct 32 ms 64332 KB Output is correct
13 Correct 29 ms 64204 KB Output is correct
14 Correct 30 ms 64288 KB Output is correct
15 Correct 37 ms 65228 KB Output is correct
16 Correct 41 ms 65184 KB Output is correct
17 Correct 41 ms 65152 KB Output is correct
18 Correct 34 ms 65368 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 78156 KB Output is correct
2 Correct 75 ms 69556 KB Output is correct
3 Correct 252 ms 94420 KB Output is correct
4 Correct 92 ms 74176 KB Output is correct
5 Correct 182 ms 83676 KB Output is correct
6 Correct 716 ms 107476 KB Output is correct
7 Correct 36 ms 78796 KB Output is correct
8 Correct 36 ms 78148 KB Output is correct
9 Correct 28 ms 63168 KB Output is correct
10 Correct 29 ms 63044 KB Output is correct
11 Correct 39 ms 78508 KB Output is correct
12 Correct 30 ms 63632 KB Output is correct
13 Correct 72 ms 69508 KB Output is correct
14 Correct 50 ms 67560 KB Output is correct
15 Correct 52 ms 67972 KB Output is correct
16 Correct 47 ms 65228 KB Output is correct
17 Correct 144 ms 75052 KB Output is correct
18 Correct 113 ms 74764 KB Output is correct
19 Correct 98 ms 74192 KB Output is correct
20 Correct 78 ms 73284 KB Output is correct
21 Correct 157 ms 84412 KB Output is correct
22 Correct 180 ms 83652 KB Output is correct
23 Correct 230 ms 80520 KB Output is correct
24 Correct 154 ms 84260 KB Output is correct
25 Correct 472 ms 94488 KB Output is correct
26 Correct 827 ms 139052 KB Output is correct
27 Correct 713 ms 114188 KB Output is correct
28 Correct 711 ms 107464 KB Output is correct
29 Correct 711 ms 106304 KB Output is correct
30 Correct 746 ms 107108 KB Output is correct
31 Correct 518 ms 86156 KB Output is correct
32 Correct 667 ms 107352 KB Output is correct