oj.uz

Submission #715912

# Submission time Handle Problem Language Result Execution time Memory
715912 2023-03-28T12:10:20 Z Farbod Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 1618 ms 1042932 KB 
/*
*  In the name of God
*
*  Author: Farbod Doost
*  Last Modified: Tue, 28 Mar 2023 (15:39:56)
*
*/
#include <bits/stdc++.h>
using namespace std;

const int N = 4005;

int n, m;
bool vis[N][N];
char a[N][N];

int T = 0;
deque <pair <short int, short int>> vec;

bool t = 0;
short int dx[] = {-1, 0, 1, 0},
          dy[] = {0, -1, 0, 1};

bool f(char a, char b)
{
    if (t)
        return a != b;
    return a == b;
}

bool val(short int &i, short int &j)
{
    return i >= 0 && i < n && j >= 0 && j < m && a[i][j] != '.' && !vis[i][j] && f(a[i][j], a[0][0]);
}

void dfs(short int x = 0, short int y = 0)
{
    vis[x][y] = 1, vec.push_back({x, y});
    for (short int i = 0; i < 4; i++) {
        short int nx = x + dx[i], ny = y + dy[i];
        if (val(nx, ny))
            dfs(nx, ny);
    }

    return;
}

signed main()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> n >> m;
    for (short int i = 0; i < n; i++)
        for (short int j = 0; j < m; j++)
            cin >> a[i][j];

    dfs();

    while (vec.size()) {
        int tmp = vec.size();

        t = 1 - t;
        for (int j = 0; j < vec.size(); j++) {
            short int x = vec[j].first, y = vec[j].second;
            for (short int i = 0; i < 4; i++) {
                short int nx = x + dx[i], ny = y + dy[i];
                if (val(nx, ny))
                    vec.push_back({nx, ny}), vis[nx][ny] = 1;
            }
        }

        while (tmp--)
            vec.pop_front();
        T++;
    }

    cout << T;

    return 0;
}

Compilation message

tracks.cpp: In function 'int main()':
tracks.cpp:63:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<std::pair<short int, short int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         for (int j = 0; j < vec.size(); j++) {
      |                         ~~^~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 4436 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 12 ms 6484 KB Output is correct
5 Correct 6 ms 2660 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 852 KB Output is correct
9 Correct 1 ms 1108 KB Output is correct
10 Correct 4 ms 2272 KB Output is correct
11 Correct 4 ms 2644 KB Output is correct
12 Correct 8 ms 2784 KB Output is correct
13 Correct 5 ms 2644 KB Output is correct
14 Correct 5 ms 2652 KB Output is correct
15 Correct 18 ms 4436 KB Output is correct
16 Correct 20 ms 4496 KB Output is correct
17 Correct 14 ms 4268 KB Output is correct
18 Correct 16 ms 6484 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 30548 KB Output is correct
2 Correct 83 ms 10440 KB Output is correct
3 Correct 484 ms 39948 KB Output is correct
4 Correct 120 ms 16328 KB Output is correct
5 Correct 318 ms 28156 KB Output is correct
6 Correct 1595 ms 178460 KB Output is correct
7 Correct 17 ms 31944 KB Output is correct
8 Correct 17 ms 30472 KB Output is correct
9 Correct 3 ms 852 KB Output is correct
10 Correct 2 ms 728 KB Output is correct
11 Correct 19 ms 31364 KB Output is correct
12 Correct 2 ms 1492 KB Output is correct
13 Correct 86 ms 10508 KB Output is correct
14 Correct 60 ms 7772 KB Output is correct
15 Correct 41 ms 8488 KB Output is correct
16 Correct 37 ms 3784 KB Output is correct
17 Correct 241 ms 17524 KB Output is correct
18 Correct 121 ms 17268 KB Output is correct
19 Correct 120 ms 16540 KB Output is correct
20 Correct 104 ms 15240 KB Output is correct
21 Correct 264 ms 29348 KB Output is correct
22 Correct 289 ms 28156 KB Output is correct
23 Correct 465 ms 23108 KB Output is correct
24 Correct 248 ms 29148 KB Output is correct
25 Correct 529 ms 39940 KB Output is correct
26 Correct 1618 ms 1042932 KB Output is correct
27 Correct 1245 ms 550268 KB Output is correct
28 Correct 1535 ms 171016 KB Output is correct
29 Correct 1529 ms 174416 KB Output is correct
30 Correct 1327 ms 145800 KB Output is correct
31 Correct 1103 ms 27216 KB Output is correct
32 Correct 999 ms 84628 KB Output is correct