oj.uz

Submission #443707

# Submission time Handle Problem Language Result Execution time Memory
443707 2021-07-11T15:01:42 Z BeanZ Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 965 ms 143136 KB 
// I_Love_LPL 1y0m3d
#include <bits/stdc++.h>
using namespace std;
#define ll int
#define endl '\n'
const int N = 4005;
long long mod = 1000007;
const int lim = 4e5 + 5;
const int lg = 20;
const int base = 311;
const long double eps = 1e-6;
ll nx[4] = {0, 0, 1, -1};
ll ny[4] = {1, -1, 0, 0};
char a[N][N];
ll dp[N][N];
struct viet{
    ll x, y, v;
};
ll n, m;
bool check(ll x, ll y){
    if (x < 1 || x > n || y < 1 || y > m || a[x][y] == '.') return false;
    else return true;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    if (fopen("tests.inp", "r")){
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            cin >> a[i][j];
            dp[i][j] = 1e9;
        }
    }
    deque<viet> q;
    q.push_back({1, 1, 1});
    dp[1][1] = 1;
    ll ans = 1;
    while (q.size()){
        viet x = q.front();
        ans = max(ans, x.v);
        q.pop_front();
        for (int i = 0; i < 4; i++){
            ll nwx = x.x + nx[i];
            ll nwy = x.y + ny[i];
            if (!check(nwx, nwy)) continue;
            ll cost = x.v + (a[nwx][nwy] != a[x.x][x.y]);
            if (dp[nwx][nwy] > cost){
                dp[nwx][nwy] = cost;
                if (cost == x.v) q.push_front({nwx, nwy, cost});
                else q.push_back({nwx, nwy, cost});
            }
        }
    }
    cout << ans;
}
/*
Ans:

Out:
*/

Compilation message

tracks.cpp: In function 'int main()':
tracks.cpp:28:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
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("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 5224 KB Output is correct
2 Correct 0 ms 460 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 10 ms 5124 KB Output is correct
5 Correct 4 ms 2892 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 716 KB Output is correct
8 Correct 1 ms 716 KB Output is correct
9 Correct 1 ms 1100 KB Output is correct
10 Correct 4 ms 2508 KB Output is correct
11 Correct 3 ms 2124 KB Output is correct
12 Correct 8 ms 3020 KB Output is correct
13 Correct 4 ms 2892 KB Output is correct
14 Correct 4 ms 2892 KB Output is correct
15 Correct 15 ms 5308 KB Output is correct
16 Correct 16 ms 5232 KB Output is correct
17 Correct 15 ms 4940 KB Output is correct
18 Correct 10 ms 5128 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 30740 KB Output is correct
2 Correct 67 ms 16356 KB Output is correct
3 Correct 429 ms 78704 KB Output is correct
4 Correct 121 ms 29892 KB Output is correct
5 Correct 297 ms 59096 KB Output is correct
6 Correct 941 ms 98464 KB Output is correct
7 Correct 18 ms 32204 KB Output is correct
8 Correct 16 ms 30796 KB Output is correct
9 Correct 3 ms 588 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 16 ms 31676 KB Output is correct
12 Correct 2 ms 1484 KB Output is correct
13 Correct 66 ms 16324 KB Output is correct
14 Correct 39 ms 11072 KB Output is correct
15 Correct 40 ms 12164 KB Output is correct
16 Correct 29 ms 6004 KB Output is correct
17 Correct 170 ms 32092 KB Output is correct
18 Correct 143 ms 31820 KB Output is correct
19 Correct 120 ms 29816 KB Output is correct
20 Correct 105 ms 27760 KB Output is correct
21 Correct 258 ms 61128 KB Output is correct
22 Correct 297 ms 59204 KB Output is correct
23 Correct 322 ms 49356 KB Output is correct
24 Correct 259 ms 60484 KB Output is correct
25 Correct 643 ms 78760 KB Output is correct
26 Correct 965 ms 143136 KB Output is correct
27 Correct 925 ms 105564 KB Output is correct
28 Correct 925 ms 98292 KB Output is correct
29 Correct 914 ms 94952 KB Output is correct
30 Correct 947 ms 102924 KB Output is correct
31 Correct 654 ms 63668 KB Output is correct
32 Correct 918 ms 103596 KB Output is correct