oj.uz

Submission #1107045

# Submission time Handle Problem Language Result Execution time Memory
1107045 2024-10-31T12:59:34 Z TgX_2 Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 610 ms 238632 KB 
/*-----------------------------
        Author : TgX.2
       11Ti - K28 - CHV
-----------------------------*/

#include <bits/stdc++.h>
using   namespace std;

#ifdef TGX 
#include "debug.h"
#else 
#define debug(...)
#endif 

#define FOR(i, a, b)       for (int i = (a), _b = (b); i <= _b; i += 1)
#define FORD(i, a, b)      for (int i = (a), _b = (b); i >= _b; i -= 1)

#define fi                 first
#define se                 second
#define pb                 push_back
#define len(x)             (int)((x).size())
#define all(x)             (x).begin(), (x).end()

#define _                  << " " <<
#define __                 << "\n"
#define ___                << " "

#define ______________TgX______________ main()
#define int                long long
#define intmax             1e9
#define intmin            -1e9
#define llongmax           1e18
#define llongmin          -1e18
#define memo(a, val)       memset((a), (val), sizeof((a)))

struct custom {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
template<class T1, class T2> using cmap = unordered_map<T1, T2, custom>;

template<typename T1, typename T2> 
bool mini(T1 &a, T2 b)
    {if (a > b) a = b; else return 0; return 1;}

template<typename T1, typename T2> 
bool maxi(T1 &a, T2 b)
    {if (a < b) a = b; else return 0; return 1;}
/*-----------------------------*/

const int dx[5] = {0, 1, 0, -1};
const int dy[5] = {1, 0, -1, 0};

const int maxn = 4007;
int n, m, dis[maxn][maxn];
char a[maxn][maxn];


void process() {
    cin >> n >> m;
    FOR(i, 1, n) FOR(j, 1, m)
        cin >> a[i][j];

    deque<pair<int, int>> q;
    q.push_back({1, 1});

    int ans = 0;

    dis[1][1] = 1;
    while(!q.empty()) {
        pair<int, int> top = q.front(); q.pop_front();
        int x = top.fi, y = top.se;
        maxi(ans, dis[x][y]);

        FOR(i, 0, 3) {
            int xx = x + dx[i];
            int yy = y + dy[i];

            if (xx < 1 or xx > n or yy < 1 or yy > m or a[xx][yy] == '.') continue;

            if (dis[xx][yy] == 0) {
                if (a[xx][yy] == a[x][y]) {
                    dis[xx][yy] = dis[x][y];
                    q.push_front({xx, yy});
                } else {
                    dis[xx][yy] = dis[x][y] + 1;
                    q.push_back({xx, yy});
                }
            }
        }
    }

    cout << ans;
}



/*-----------------------------*/
______________TgX______________ {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);  
    if (fopen("temp.inp", "r")) {
        freopen("temp.inp", "r", stdin);
        freopen("temp.out", "w", stdout);
    }
    process();
    cerr << "Time: " << 1.0 * clock() / CLOCKS_PER_SEC << " s." __ ;
}


/*==============================+
|INPUT                          |
--------------------------------|

================================+
|OUTPUT                         |
--------------------------------|

===============================*/

Compilation message

tracks.cpp:28:41: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   28 | #define ______________TgX______________ main()
      |                                         ^~~~
tracks.cpp:108:1: note: in expansion of macro '______________TgX______________'
  108 | ______________TgX______________ {
      | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
tracks.cpp: In function 'int main()':
tracks.cpp:112:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |         freopen("temp.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
tracks.cpp:113:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |         freopen("temp.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 8528 KB Output is correct
2 Correct 1 ms 2552 KB Output is correct
3 Correct 1 ms 4688 KB Output is correct
4 Correct 7 ms 8128 KB Output is correct
5 Correct 5 ms 6224 KB Output is correct
6 Correct 1 ms 2516 KB Output is correct
7 Correct 2 ms 4688 KB Output is correct
8 Correct 1 ms 4688 KB Output is correct
9 Correct 1 ms 4944 KB Output is correct
10 Correct 3 ms 5712 KB Output is correct
11 Correct 3 ms 5728 KB Output is correct
12 Correct 5 ms 6372 KB Output is correct
13 Correct 3 ms 6224 KB Output is correct
14 Correct 3 ms 6224 KB Output is correct
15 Correct 10 ms 8272 KB Output is correct
16 Correct 11 ms 8572 KB Output is correct
17 Correct 9 ms 8272 KB Output is correct
18 Correct 7 ms 8184 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 32604 KB Output is correct
2 Correct 44 ms 21556 KB Output is correct
3 Correct 234 ms 91656 KB Output is correct
4 Correct 74 ms 49224 KB Output is correct
5 Correct 177 ms 73552 KB Output is correct
6 Correct 580 ms 185752 KB Output is correct
7 Correct 13 ms 33360 KB Output is correct
8 Correct 13 ms 32760 KB Output is correct
9 Correct 2 ms 2640 KB Output is correct
10 Correct 1 ms 2384 KB Output is correct
11 Correct 13 ms 32848 KB Output is correct
12 Correct 2 ms 5200 KB Output is correct
13 Correct 37 ms 21584 KB Output is correct
14 Correct 23 ms 14928 KB Output is correct
15 Correct 22 ms 19140 KB Output is correct
16 Correct 20 ms 9564 KB Output is correct
17 Correct 93 ms 38780 KB Output is correct
18 Correct 81 ms 53320 KB Output is correct
19 Correct 73 ms 49224 KB Output is correct
20 Correct 58 ms 33864 KB Output is correct
21 Correct 158 ms 65280 KB Output is correct
22 Correct 170 ms 73544 KB Output is correct
23 Correct 178 ms 59720 KB Output is correct
24 Correct 158 ms 63560 KB Output is correct
25 Correct 369 ms 157300 KB Output is correct
26 Correct 558 ms 238632 KB Output is correct
27 Correct 543 ms 208452 KB Output is correct
28 Correct 610 ms 185668 KB Output is correct
29 Correct 568 ms 180456 KB Output is correct
30 Correct 543 ms 191548 KB Output is correct
31 Correct 387 ms 120168 KB Output is correct
32 Correct 475 ms 191212 KB Output is correct