oj.uz

Submission #101570

# Submission time Handle Problem Language Result Execution time Memory
101570 2019-03-19T04:32:28 Z shenxy Tracks in the Snow (BOI13_tracks) C++11
47.5 / 100
 2000 ms 31944 KB 
#include <cstdio>
#include <algorithm>
#include <queue>
#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};
int main() {
    int H, W, numani = 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]);
            if (mygrid[i][j] != '.') numani += 1;
        }
    }
    char curani = mygrid[0][0];
    int ans = 0, update = 0;
    numani -= 1;
    while (numani > 0) {
        bool visited[H][W];
        memset(visited, false, sizeof(visited));
        visited[0][0] = true;
        mygrid[0][0] = '?';
        queue<coord> bfsq;
        bfsq.push(coord(0, 0));
        while (!bfsq.empty()) {
            coord k = bfsq.front();
            bfsq.pop();
            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]] == curani || mygrid[k.first + dx[i]][k.second + dy[i]] == '?') {
                        if (!visited[k.first + dx[i]][k.second + dy[i]]) {
                            visited[k.first + dx[i]][k.second + dy[i]] = true;
                            bfsq.push(coord(k.first + dx[i], k.second + dy[i]));
                            if (mygrid[k.first + dx[i]][k.second + dy[i]] != '?') {
                                mygrid[k.first + dx[i]][k.second + dy[i]] = '?';
                                numani -= 1;
                                update = 1;
                            }
                        }
                    }
                }
            }
        }
        ans += update;
        if (curani == 'F') curani = 'R';
        else curani = 'F';
    }
    printf("%d", ans);
    return 0;
}

Compilation message

tracks.cpp: In function 'int main()':
tracks.cpp:12: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:16: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
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 812 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 3 ms 256 KB Output is correct
4 Correct 26 ms 640 KB Output is correct
5 Correct 60 ms 504 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 4 ms 256 KB Output is correct
8 Correct 3 ms 256 KB Output is correct
9 Correct 4 ms 256 KB Output is correct
10 Correct 66 ms 384 KB Output is correct
11 Correct 7 ms 384 KB Output is correct
12 Correct 52 ms 512 KB Output is correct
13 Correct 75 ms 504 KB Output is correct
14 Correct 68 ms 504 KB Output is correct
15 Correct 429 ms 832 KB Output is correct
16 Correct 228 ms 816 KB Output is correct
17 Correct 435 ms 808 KB Output is correct
18 Correct 27 ms 640 KB Output is correct

Subtask #2
17.5 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1068 ms 436 KB Output is correct
2 Execution timed out 2095 ms 3320 KB Time limit exceeded
3 Execution timed out 2079 ms 31648 KB Time limit exceeded
4 Execution timed out 2095 ms 7688 KB Time limit exceeded
5 Execution timed out 2015 ms 18048 KB Time limit exceeded
6 Execution timed out 2005 ms 31676 KB Time limit exceeded
7 Correct 825 ms 428 KB Output is correct
8 Correct 1124 ms 436 KB Output is correct
9 Correct 147 ms 384 KB Output is correct
10 Correct 350 ms 400 KB Output is correct
11 Correct 279 ms 436 KB Output is correct
12 Correct 1399 ms 384 KB Output is correct
13 Execution timed out 2017 ms 3292 KB Time limit exceeded
14 Execution timed out 2087 ms 2040 KB Time limit exceeded
15 Execution timed out 2017 ms 2256 KB Time limit exceeded
16 Execution timed out 2101 ms 1624 KB Time limit exceeded
17 Execution timed out 2092 ms 8228 KB Time limit exceeded
18 Execution timed out 2011 ms 8184 KB Time limit exceeded
19 Execution timed out 2031 ms 7740 KB Time limit exceeded
20 Execution timed out 2040 ms 6952 KB Time limit exceeded
21 Execution timed out 2051 ms 18552 KB Time limit exceeded
22 Execution timed out 2048 ms 17896 KB Time limit exceeded
23 Execution timed out 2048 ms 15584 KB Time limit exceeded
24 Execution timed out 2021 ms 18064 KB Time limit exceeded
25 Execution timed out 2037 ms 31524 KB Time limit exceeded
26 Correct 1203 ms 24492 KB Output is correct
27 Execution timed out 2037 ms 31836 KB Time limit exceeded
28 Execution timed out 2044 ms 31900 KB Time limit exceeded
29 Execution timed out 2024 ms 31944 KB Time limit exceeded
30 Execution timed out 2033 ms 31300 KB Time limit exceeded
31 Execution timed out 2025 ms 20480 KB Time limit exceeded
32 Execution timed out 2033 ms 31868 KB Time limit exceeded