oj.uz

Submission #1098103

# Submission time Handle Problem Language Result Execution time Memory
1098103 2024-10-09T04:38:55 Z The_Eureka Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 531 ms 138940 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define mk make_pair
#define pb push_back
#define alls(x) x.begin(), x.end()
#define sz(x) (int)(x.size())
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define rep(i, n) for (int i = 1; i <= int(n); i++)
#define inc(i, l, r, d) for (int i = l; i <= r; i += d)
#define dec(i, r, l, d) for (int i = r; i >= l; i -= d) 
#define dbg(x) cerr << #x << " = " << x << endl;
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
const ld eps = 1e-12;
const ll inf = 1e16;
const ll mod = 998244353;
const ll mod1 = 1e9 + 87;
const ll mod2 = 127397154761;
ll qpow(ll a, ll b) {if (b == 0) return 1; ll ans = qpow(a, b >> 1); ans = ans * ans % mod; if (b & 1) ans = ans * a % mod; return ans;}
using namespace std;

void IOS(string name = "") {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    if ((int)name.size()) {
        freopen((name + ".in").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }
}


const int maxn = 4005;
int m, n;
char s[maxn][maxn];
int d[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
int dis[maxn][maxn];
bool vis[maxn][maxn];

bool check(int x1, int y1) {
    return x1 > 0 && y1 > 0 && x1 <= m && y1 <= n;
}


int main() {
    IOS();
    cin >> m >> n;
    rep(i, m) {
        rep(j, n) {
            cin >> s[i][j];
        }
    }
    if (s[1][1] == '.') {
        cout << 0 << endl;
        return 0;
    }
    deque<pii> dq;
    rep(i, m) {
        rep(j, n) {
            dis[i][j] = INT_MAX - 10;
        }
    }
    dis[1][1] = true;
    dq.pb(mk(1, 1));
    vis[1][1] = true;

    while (!dq.empty()) {
        pii u = dq.front(); dq.pop_front();
        forn(k, 4) {
            int x1 = u.first + d[k][0], y1 = u.second + d[k][1];
            if (!check(x1, y1)) continue;
            if (s[x1][y1] == '.') continue;
            pii v = mk(x1, y1);
            int w = (s[x1][y1] != s[u.first][u.second]);
            if (vis[x1][y1]) continue;
            if (dis[x1][y1] > dis[u.first][u.second] + w) {
                dis[x1][y1] = dis[u.first][u.second] + w;
                vis[x1][y1] = true;
                if (w == 1) {
                    dq.pb(v);
                }
                else {
                    dq.push_front(v);
                }
            }
        }
    }

    int ans = 0;
    rep(i, m) {
        rep(j, n) {
            if (s[i][j] != '.') {
                ans = max(ans, dis[i][j]);
            }
        }
    }
    cout << ans << endl;

    return 0;
}

Compilation message

tracks.cpp: In function 'void IOS(std::string)':
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((name + ".in").c_str(), "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((name + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7260 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 7 ms 7260 KB Output is correct
5 Correct 4 ms 4296 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Correct 1 ms 1628 KB Output is correct
10 Correct 3 ms 3676 KB Output is correct
11 Correct 2 ms 2904 KB Output is correct
12 Correct 5 ms 4188 KB Output is correct
13 Correct 4 ms 4264 KB Output is correct
14 Correct 4 ms 4188 KB Output is correct
15 Correct 10 ms 7516 KB Output is correct
16 Correct 12 ms 7512 KB Output is correct
17 Correct 10 ms 7260 KB Output is correct
18 Correct 7 ms 7252 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 45912 KB Output is correct
2 Correct 41 ms 22360 KB Output is correct
3 Correct 258 ms 102692 KB Output is correct
4 Correct 84 ms 39504 KB Output is correct
5 Correct 143 ms 75400 KB Output is correct
6 Correct 510 ms 115944 KB Output is correct
7 Correct 16 ms 48216 KB Output is correct
8 Correct 19 ms 45916 KB Output is correct
9 Correct 2 ms 908 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 17 ms 47232 KB Output is correct
12 Correct 2 ms 2140 KB Output is correct
13 Correct 41 ms 22424 KB Output is correct
14 Correct 40 ms 15432 KB Output is correct
15 Correct 26 ms 16984 KB Output is correct
16 Correct 20 ms 8028 KB Output is correct
17 Correct 109 ms 42440 KB Output is correct
18 Correct 83 ms 42072 KB Output is correct
19 Correct 76 ms 39296 KB Output is correct
20 Correct 61 ms 36548 KB Output is correct
21 Correct 166 ms 78108 KB Output is correct
22 Correct 156 ms 75568 KB Output is correct
23 Correct 191 ms 63316 KB Output is correct
24 Correct 151 ms 77392 KB Output is correct
25 Correct 329 ms 102636 KB Output is correct
26 Correct 442 ms 138940 KB Output is correct
27 Correct 441 ms 120928 KB Output is correct
28 Correct 484 ms 115816 KB Output is correct
29 Correct 531 ms 113400 KB Output is correct
30 Correct 465 ms 117652 KB Output is correct
31 Correct 356 ms 81688 KB Output is correct
32 Correct 408 ms 119504 KB Output is correct