oj.uz

Submission #101598

# Submission time Handle Problem Language Result Execution time Memory
101598 2019-03-19T04:58:29 Z shenxy Tracks in the Snow (BOI13_tracks) C++11
17.6042 / 100
 2000 ms 110552 KB 
#include <cstdio>
#include <algorithm>
#include <deque>
#include <cstring>
#include <utility>
using namespace std;
typedef pair<int, int> coord;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
const int INF = 1000000000;
int main() {
    int H, W, ans = 0;
    scanf("%d %d", &H, &W);
    char mygrid[H][W];
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            scanf(" %c", &mygrid[i][j]);
        }
    }
    int visited[H][W];
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            visited[i][j] = INF;
        }
    }
    visited[0][0] = 0;
    deque<coord> bfsq;
    bfsq.push_back(coord(0, 0));
    while (!bfsq.empty()) {
        coord k = bfsq.front();
        bfsq.pop_front();
        for (int i = 0; i < 4; i++) {
            if (k.first + dx[i] >= 0 && k.first + dx[i] < H && k.second + dy[i] >= 0 && k.second + dy[i] < W) {
                if (mygrid[k.first + dx[i]][k.second + dy[i]] == mygrid[k.first][k.second]) {
                    if (visited[k.first + dx[i]][k.second + dy[i]] == INF) {
                        visited[k.first + dx[i]][k.second + dy[i]] = visited[k.first][k.second];
                        bfsq.push_front(coord(k.first + dx[i], k.second + dy[i]));
                    }
                } else if (mygrid[k.first + dx[i]][k.second + dy[i]] != '.') {
                    if (visited[k.first + dx[i]][k.second + dy[i]] == INF) {
                        visited[k.first + dx[i]][k.second + dy[i]] = visited[k.first][k.second] + 1;
                        bfsq.push_back(coord(k.first + dx[i], k.second + dy[i]));
                    }
                }
            }
        }
    }
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            ans = max(ans, visited[i][j]);
        }
    }
    printf("%d", ans + 1);
    return 0;
}

Compilation message

tracks.cpp: In function 'int main()':
tracks.cpp:13:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &H, &W);
     ~~~~~^~~~~~~~~~~~~~~~~
tracks.cpp:17:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf(" %c", &mygrid[i][j]);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.66666666667 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 1528 KB Output isn't correct
2 Incorrect 2 ms 384 KB Output isn't correct
3 Incorrect 3 ms 256 KB Output isn't correct
4 Correct 17 ms 1280 KB Output is correct
5 Incorrect 9 ms 768 KB Output isn't correct
6 Incorrect 2 ms 256 KB Output isn't correct
7 Incorrect 2 ms 256 KB Output isn't correct
8 Correct 2 ms 384 KB Output is correct
9 Incorrect 2 ms 384 KB Output isn't correct
10 Incorrect 8 ms 640 KB Output isn't correct
11 Correct 8 ms 640 KB Output is correct
12 Incorrect 13 ms 740 KB Output isn't correct
13 Incorrect 9 ms 768 KB Output isn't correct
14 Incorrect 12 ms 768 KB Output isn't correct
15 Incorrect 28 ms 1536 KB Output isn't correct
16 Incorrect 37 ms 1528 KB Output isn't correct
17 Incorrect 24 ms 1532 KB Output isn't correct
18 Correct 19 ms 1408 KB Output is correct

Subtask #2
10.9375 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 640 KB Output isn't correct
2 Incorrect 140 ms 7928 KB Output isn't correct
3 Incorrect 1256 ms 78704 KB Output isn't correct
4 Incorrect 286 ms 18808 KB Output isn't correct
5 Incorrect 749 ms 44372 KB Output isn't correct
6 Execution timed out 2067 ms 92176 KB Time limit exceeded
7 Incorrect 5 ms 512 KB Output isn't correct
8 Incorrect 7 ms 512 KB Output isn't correct
9 Incorrect 8 ms 640 KB Output isn't correct
10 Incorrect 4 ms 512 KB Output isn't correct
11 Incorrect 7 ms 580 KB Output isn't correct
12 Incorrect 4 ms 384 KB Output isn't correct
13 Incorrect 143 ms 8016 KB Output isn't correct
14 Incorrect 84 ms 4728 KB Output isn't correct
15 Incorrect 77 ms 5112 KB Output isn't correct
16 Incorrect 61 ms 3484 KB Output isn't correct
17 Incorrect 383 ms 20184 KB Output isn't correct
18 Incorrect 317 ms 19836 KB Output isn't correct
19 Incorrect 318 ms 18776 KB Output isn't correct
20 Incorrect 285 ms 17172 KB Output isn't correct
21 Incorrect 778 ms 46008 KB Output isn't correct
22 Incorrect 751 ms 44472 KB Output isn't correct
23 Incorrect 835 ms 38276 KB Output isn't correct
24 Incorrect 726 ms 44716 KB Output isn't correct
25 Incorrect 1407 ms 78640 KB Output isn't correct
26 Correct 1490 ms 110552 KB Output is correct
27 Correct 1754 ms 96928 KB Output is correct
28 Correct 1868 ms 92040 KB Output is correct
29 Correct 1850 ms 89764 KB Output is correct
30 Correct 1671 ms 94304 KB Output is correct
31 Incorrect 1452 ms 51064 KB Output isn't correct
32 Incorrect 1904 ms 95608 KB Output isn't correct