oj.uz

Submission #67039

# Submission time Handle Problem Language Result Execution time Memory
67039 2018-08-13T08:54:44 Z RezwanArefin01 Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 958 ms 297244 KB 
///usr/bin/g++ -O2 $0 -o ${0%.cpp} && echo "----------" && ./${0%.cpp}; exit;
#include <bits/stdc++.h>
using namespace std;

typedef long long ll; 
typedef pair<int, int> ii; 

const int N = 4010; 

char g[N][N]; 
int dx[] = {0, 0, 1, -1}; 
int dy[] = {1, -1, 0, 0}; 
int d[N][N], n, m; 

int main() {
    scanf("%d %d", &n, &m);
    for(int i = 0; i < n; i++) 
        scanf(" %s", g[i]); 

    deque<ii> q; 
    memset(d, 63, sizeof d); 
    q.push_back({0, 0}); 
    d[0][0] = 1 ;
    while(!q.empty()) {
        ii u = q.front(); q.pop_front(); 
        int x = u.first, y = u.second;
        for(int i = 0; i < 4; i++) {
            int xx = x + dx[i], yy = y + dy[i]; 
            if(xx >= 0 && xx < n && yy >= 0 && yy < m && g[xx][yy] != '.') {
                int c = g[x][y] != g[xx][yy];
                if(d[xx][yy] > d[x][y] + c) {
                    d[xx][yy] = d[x][y] + c;
                    if(c) q.push_back({xx, yy}); 
                    else q.push_front({xx, yy}); 
                }
            }
        }
    }
    int mx = 0; 
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) if(g[i][j] != '.') {
            mx = max(mx, d[i][j]); 
        }
    }
    printf("%d\n", mx); 
}

Compilation message

tracks.cpp: In function 'int main()':
tracks.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
tracks.cpp:18:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %s", g[i]); 
         ~~~~~^~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 65528 KB Output is correct
2 Correct 65 ms 65528 KB Output is correct
3 Correct 50 ms 65528 KB Output is correct
4 Correct 57 ms 65980 KB Output is correct
5 Correct 58 ms 65980 KB Output is correct
6 Correct 61 ms 65980 KB Output is correct
7 Correct 56 ms 65980 KB Output is correct
8 Correct 58 ms 65980 KB Output is correct
9 Correct 58 ms 65980 KB Output is correct
10 Correct 57 ms 65980 KB Output is correct
11 Correct 51 ms 65980 KB Output is correct
12 Correct 63 ms 65980 KB Output is correct
13 Correct 52 ms 65980 KB Output is correct
14 Correct 58 ms 65980 KB Output is correct
15 Correct 61 ms 66800 KB Output is correct
16 Correct 84 ms 67052 KB Output is correct
17 Correct 65 ms 67160 KB Output is correct
18 Correct 63 ms 67608 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 80444 KB Output is correct
2 Correct 113 ms 80444 KB Output is correct
3 Correct 333 ms 98432 KB Output is correct
4 Correct 147 ms 98432 KB Output is correct
5 Correct 224 ms 106964 KB Output is correct
6 Correct 916 ms 139904 KB Output is correct
7 Correct 69 ms 139904 KB Output is correct
8 Correct 71 ms 139904 KB Output is correct
9 Correct 59 ms 139904 KB Output is correct
10 Correct 55 ms 139904 KB Output is correct
11 Correct 67 ms 139904 KB Output is correct
12 Correct 58 ms 139904 KB Output is correct
13 Correct 116 ms 139904 KB Output is correct
14 Correct 77 ms 139904 KB Output is correct
15 Correct 86 ms 139904 KB Output is correct
16 Correct 80 ms 139904 KB Output is correct
17 Correct 198 ms 139904 KB Output is correct
18 Correct 173 ms 139904 KB Output is correct
19 Correct 151 ms 139904 KB Output is correct
20 Correct 111 ms 139904 KB Output is correct
21 Correct 221 ms 151264 KB Output is correct
22 Correct 222 ms 159740 KB Output is correct
23 Correct 277 ms 165480 KB Output is correct
24 Correct 212 ms 176648 KB Output is correct
25 Correct 524 ms 195932 KB Output is correct
26 Correct 772 ms 256148 KB Output is correct
27 Correct 668 ms 256148 KB Output is correct
28 Correct 958 ms 256148 KB Output is correct
29 Correct 915 ms 265784 KB Output is correct
30 Correct 823 ms 287500 KB Output is correct
31 Correct 740 ms 287500 KB Output is correct
32 Correct 858 ms 297244 KB Output is correct