oj.uz

Submission #101556

# Submission time Handle Problem Language Result Execution time Memory
101556 2019-03-19T04:20:11 Z shenxy Tracks in the Snow (BOI13_tracks) C++11
7.1875 / 100
 2000 ms 31832 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;
    while (numani > 0) {
        bool visited[H][W];
        memset(visited, false, sizeof(visited));
        visited[0][0] = true;
        mygrid[0][0] = '?';
        numani -= 1;
        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
5.0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 172 ms 860 KB Output isn't correct
2 Incorrect 3 ms 256 KB Output isn't correct
3 Incorrect 3 ms 384 KB Output isn't correct
4 Correct 33 ms 640 KB Output is correct
5 Incorrect 53 ms 512 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 Incorrect 4 ms 384 KB Output isn't correct
9 Incorrect 5 ms 256 KB Output isn't correct
10 Incorrect 52 ms 508 KB Output isn't correct
11 Correct 7 ms 384 KB Output is correct
12 Incorrect 71 ms 512 KB Output isn't correct
13 Incorrect 60 ms 512 KB Output isn't correct
14 Incorrect 48 ms 512 KB Output isn't correct
15 Incorrect 315 ms 768 KB Output isn't correct
16 Incorrect 196 ms 760 KB Output isn't correct
17 Incorrect 323 ms 768 KB Output isn't correct
18 Correct 25 ms 640 KB Output is correct

Subtask #2
2.1875 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 577 ms 444 KB Output isn't correct
2 Execution timed out 2009 ms 3508 KB Time limit exceeded
3 Execution timed out 2021 ms 31604 KB Time limit exceeded
4 Execution timed out 2045 ms 10104 KB Time limit exceeded
5 Execution timed out 2024 ms 21752 KB Time limit exceeded
6 Execution timed out 2017 ms 31816 KB Time limit exceeded
7 Incorrect 405 ms 432 KB Output isn't correct
8 Incorrect 511 ms 436 KB Output isn't correct
9 Incorrect 135 ms 384 KB Output isn't correct
10 Incorrect 178 ms 508 KB Output isn't correct
11 Incorrect 150 ms 384 KB Output isn't correct
12 Incorrect 390 ms 384 KB Output isn't correct
13 Execution timed out 2033 ms 3320 KB Time limit exceeded
14 Execution timed out 2060 ms 2908 KB Time limit exceeded
15 Execution timed out 2045 ms 2940 KB Time limit exceeded
16 Execution timed out 2060 ms 1528 KB Time limit exceeded
17 Execution timed out 2043 ms 8312 KB Time limit exceeded
18 Execution timed out 2032 ms 8184 KB Time limit exceeded
19 Execution timed out 2044 ms 10108 KB Time limit exceeded
20 Execution timed out 2041 ms 9080 KB Time limit exceeded
21 Execution timed out 2087 ms 18552 KB Time limit exceeded
22 Execution timed out 2028 ms 20732 KB Time limit exceeded
23 Execution timed out 2057 ms 15608 KB Time limit exceeded
24 Execution timed out 2059 ms 18144 KB Time limit exceeded
25 Execution timed out 2058 ms 31560 KB Time limit exceeded
26 Correct 1083 ms 24580 KB Output is correct
27 Execution timed out 2054 ms 31832 KB Time limit exceeded
28 Execution timed out 2049 ms 31736 KB Time limit exceeded
29 Execution timed out 2015 ms 31728 KB Time limit exceeded
30 Execution timed out 2052 ms 31116 KB Time limit exceeded
31 Execution timed out 2048 ms 20344 KB Time limit exceeded
32 Execution timed out 2072 ms 31736 KB Time limit exceeded