oj.uz

Submission #862294

# Submission time Handle Problem Language Result Execution time Memory
862294 2023-10-18T02:32:22 Z Truly_ Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 488 ms 122492 KB 
#define nametask "tracks"
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define SZ(a) (int) a.size()
#define FOR(i, a, b) for (int i = a; i <= b; i++)
#define FOD(i, b, a) for (int i = b; i >= a; i--)

using namespace std;
typedef long long ll;
typedef pair <int, int> pi;
const pi dir[] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
const int N = 4005;

int n, m;
char a[N][N];
int d[N][N];

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

signed main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    if (fopen(nametask".inp", "r")){
        freopen(nametask".inp", "r", stdin);
        freopen(nametask".out", "w", stdout);
    }
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            cin >> a[i][j];
        }
    }
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++) d[i][j] = 0;
    }
    int ans = 1;
    deque <pi> dq;
    d[1][1] = 1;
    dq.push_back(mp(1, 1));
    while (!dq.empty()){
        pi top = dq.front();
        ans = max(ans, d[top.fi][top.se]);
        dq.pop_front();
        for (int i = 0; i < 4; i++){
            int u = top.fi + dir[i].fi, v = top.se + dir[i].se;
            if (ok(u, v) && (a[u][v] != '.') && (d[u][v] == 0)){
                if (a[u][v] == a[top.fi][top.se]){
                    d[u][v] = d[top.fi][top.se];
                    dq.push_front(mp(u, v));
                }
                else {
                    d[u][v] = d[top.fi][top.se] + 1;
                    dq.push_back(mp(u, v));
                }
            }
        }
    }
    cout << ans;
    return 0;
}

Compilation message

tracks.cpp: In function 'int main()':
tracks.cpp:29:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         freopen(nametask".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
tracks.cpp:30:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |         freopen(nametask".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12892 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 6 ms 12892 KB Output is correct
5 Correct 3 ms 10588 KB Output is correct
6 Correct 1 ms 4440 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 2 ms 6492 KB Output is correct
11 Correct 2 ms 6492 KB Output is correct
12 Correct 5 ms 10812 KB Output is correct
13 Correct 3 ms 10584 KB Output is correct
14 Correct 3 ms 10588 KB Output is correct
15 Correct 9 ms 12868 KB Output is correct
16 Correct 10 ms 12892 KB Output is correct
17 Correct 8 ms 12632 KB Output is correct
18 Correct 6 ms 12892 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 78428 KB Output is correct
2 Correct 34 ms 27100 KB Output is correct
3 Correct 241 ms 78784 KB Output is correct
4 Correct 60 ms 41616 KB Output is correct
5 Correct 175 ms 62420 KB Output is correct
6 Correct 487 ms 92484 KB Output is correct
7 Correct 9 ms 78680 KB Output is correct
8 Correct 8 ms 78428 KB Output is correct
9 Correct 2 ms 4700 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 9 ms 78428 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 34 ms 27228 KB Output is correct
14 Correct 20 ms 21088 KB Output is correct
15 Correct 18 ms 22872 KB Output is correct
16 Correct 16 ms 10844 KB Output is correct
17 Correct 83 ms 43480 KB Output is correct
18 Correct 63 ms 43464 KB Output is correct
19 Correct 63 ms 41812 KB Output is correct
20 Correct 53 ms 37340 KB Output is correct
21 Correct 135 ms 64212 KB Output is correct
22 Correct 163 ms 62032 KB Output is correct
23 Correct 166 ms 54220 KB Output is correct
24 Correct 137 ms 64216 KB Output is correct
25 Correct 352 ms 78804 KB Output is correct
26 Correct 308 ms 122492 KB Output is correct
27 Correct 388 ms 107384 KB Output is correct
28 Correct 488 ms 92644 KB Output is correct
29 Correct 483 ms 93516 KB Output is correct
30 Correct 469 ms 99116 KB Output is correct
31 Correct 357 ms 66900 KB Output is correct
32 Correct 354 ms 96756 KB Output is correct