oj.uz

Submission #773266

# Submission time Handle Problem Language Result Execution time Memory
773266 2023-07-04T18:05:57 Z trnthienphc2003 Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 710 ms 143136 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
#define fore(i, a, b) for (int i = (a), _b = (b); i < _b; ++i)
#define fort(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define fordt(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define forde(i, a, b) for (int i = (a), _b = (b); i > _b; --i)
#define trav(a, x) for (auto& a : x)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
 
using namespace std;
using namespace __gnu_pbds;
 
template<class A, class B> bool maxi(A &a, const B &b) {return (a < b) ? (a = b, true):false;};
template<class A, class B> bool mini(A &a, const B &b) {return (a > b) ? (a = b, true):false;};
 
typedef int64_t i64;
typedef pair<int,int> _ii;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
constexpr int maxn=2e5+7;
constexpr i64 oo=1e9+7;
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
char c[4007][4007];
int n, m, dp[4007][4007];
 
bool in(int x, int y) {
    return x >= 1 && x <= n && y >= 1 && y <= m && c[x][y] != '.';
}
 
struct Node {
    int x, y, val;
    Node(int x, int y, int val): x(x), y(y), val(val) {}
};
 
void solve() {
   cin >> n >> m;
 
   deque <Node> dq;
   fort(i, 1, n) fort(j, 1, m) {
        dp[i][j] = oo;
        cin >> c[i][j];
   }
 
   dq.push_back({1, 1, 1});
   dp[1][1] = 1;
 
   while(dq.size()) {
        auto [x, y, val] = dq.front(); dq.pop_front();
        if(val > dp[x][y]) continue;
        fore(i, 0, 4) {
            int nX = x + dx[i], nY = y + dy[i];
            if(!in(nX, nY)) continue;
 
            int cost = (c[nX][nY] != c[x][y] ? 1 : 0);
            if(dp[nX][nY] > dp[x][y] + cost) {
                dp[nX][nY] = dp[x][y] + cost;
                if(cost) dq.push_back(Node(nX, nY, dp[nX][nY]));
                else dq.push_front(Node(nX, nY, dp[nX][nY]));
 
                // cout << x << " " << y <<  " : " << nX << " " << nY << " - " << cost << endl;
                // cout << dp[x][y] << " --- " << dp[nX][nY] << endl;
            }
        }
   }
 
    int ans = 0;
    fort(i, 1, n) fort(j, 1, m) {
        if(dp[i][j] < oo) maxi(ans, dp[i][j]);
    }
    cout << ans;
}
 
#define NAME "test."
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    if(fopen(NAME"inp", "r")) {
        freopen(NAME"inp", "r", stdin);
        freopen(NAME"out", "w", stdout);
    }
 
    int t=1;
    while(t--) solve();
}

Compilation message

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

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 5264 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 7 ms 5076 KB Output is correct
5 Correct 3 ms 2900 KB Output is correct
6 Correct 0 ms 468 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 3 ms 2516 KB Output is correct
11 Correct 2 ms 2132 KB Output is correct
12 Correct 6 ms 3040 KB Output is correct
13 Correct 3 ms 2900 KB Output is correct
14 Correct 3 ms 2900 KB Output is correct
15 Correct 12 ms 5204 KB Output is correct
16 Correct 14 ms 5264 KB Output is correct
17 Correct 9 ms 4948 KB Output is correct
18 Correct 9 ms 5076 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 30884 KB Output is correct
2 Correct 48 ms 16388 KB Output is correct
3 Correct 282 ms 78684 KB Output is correct
4 Correct 85 ms 29940 KB Output is correct
5 Correct 191 ms 59120 KB Output is correct
6 Correct 651 ms 98156 KB Output is correct
7 Correct 12 ms 32300 KB Output is correct
8 Correct 11 ms 30880 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 13 ms 31700 KB Output is correct
12 Correct 2 ms 1492 KB Output is correct
13 Correct 61 ms 16312 KB Output is correct
14 Correct 26 ms 11056 KB Output is correct
15 Correct 33 ms 12116 KB Output is correct
16 Correct 23 ms 6004 KB Output is correct
17 Correct 121 ms 32116 KB Output is correct
18 Correct 91 ms 31760 KB Output is correct
19 Correct 85 ms 29916 KB Output is correct
20 Correct 72 ms 27708 KB Output is correct
21 Correct 178 ms 61200 KB Output is correct
22 Correct 194 ms 59128 KB Output is correct
23 Correct 248 ms 49396 KB Output is correct
24 Correct 179 ms 60592 KB Output is correct
25 Correct 491 ms 78728 KB Output is correct
26 Correct 410 ms 143136 KB Output is correct
27 Correct 523 ms 104636 KB Output is correct
28 Correct 710 ms 98156 KB Output is correct
29 Correct 701 ms 98588 KB Output is correct
30 Correct 665 ms 98772 KB Output is correct
31 Correct 579 ms 63692 KB Output is correct
32 Correct 444 ms 101676 KB Output is correct