oj.uz

Submission #916648

# Submission time Handle Problem Language Result Execution time Memory
916648 2024-01-26T08:31:41 Z May27_th Tracks in the Snow (BOI13_tracks) C++17
11.0417 / 100
 2000 ms 158276 KB 
#include <bits/stdc++.h>
#define int64_t long long
#define double long double
using namespace std;
using type = int64_t;
const long long mod = 1000000007, inf = 1e18;
const int base = 33;
const int N = 2e5 + 10;
const int LG = 20;

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

void Minimize(int64_t &a, int64_t b) {if(b < a) a = b;}
void Maximize(int &a, int b) {if(b > a) a = b;}
void Add(int64_t& a, int64_t b) {a = a + b; a %= mod;}
void Dec(int64_t& a, int64_t b) {a = a - b + mod; a %= mod;}

int h, w; char g[4010][4010]; int64_t d[4005][4005];
void Solve(void)
{
    cin >> h >> w;
    for(int i = 1; i <= h; i ++){
        for(int j = 1; j <= w; j ++){
            cin >> g[i][j];
        }
    }
    memset(d, 0x3f3f, sizeof(d));
    queue<pair<int, int>>q;
    d[1][1] = 1;
    q.push(make_pair(1, 1));
    while(!q.empty()){
        int u = q.front().first;
        int v = q.front().second;
        q.pop();
        for(int i = 0; i < 4; i ++){
            int nu = u + dx[i];
            int nv = v + dy[i];
            if(nu >= 1 && nv >= 1 && nu <= h && nv <= w){
                if(d[nu][nv] > d[u][v] + (g[u][v] != g[nu][nv])){
                    d[nu][nv] = d[u][v] + (g[u][v] != g[nu][nv]);
                    q.push(make_pair(nu, nv));
                }
            }
        }
    }
    int64_t ans = 0;
    for(int i = 1; i <= h; i ++){
        for(int j = 1; j <= w; j ++){
            ans = max(ans, d[i][j]);
        }
    }
    cout << ans;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    if(fopen("poetry.in", "r")){
        freopen("poetry.in", "r", stdin);
        freopen("poetry.out", "w", stdout);
    }
    if(fopen("A.inp", "r")){
        freopen("A.inp", "r", stdin);
        freopen("A.out", "w", stdout);
    }
    int tc = 1;
    //cin >> tc;
    while(tc --){
        Solve();
    }
}

Compilation message

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

Subtask #1
6.66666666667 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 165 ms 130156 KB Output isn't correct
2 Incorrect 22 ms 127836 KB Output isn't correct
3 Incorrect 21 ms 127752 KB Output isn't correct
4 Correct 36 ms 129876 KB Output is correct
5 Incorrect 30 ms 127828 KB Output isn't correct
6 Incorrect 21 ms 127836 KB Output isn't correct
7 Incorrect 21 ms 127832 KB Output isn't correct
8 Correct 21 ms 127824 KB Output is correct
9 Incorrect 21 ms 127800 KB Output isn't correct
10 Incorrect 25 ms 127836 KB Output isn't correct
11 Correct 23 ms 127836 KB Output is correct
12 Incorrect 55 ms 127960 KB Output isn't correct
13 Incorrect 29 ms 127824 KB Output isn't correct
14 Incorrect 29 ms 127828 KB Output isn't correct
15 Incorrect 73 ms 130160 KB Output isn't correct
16 Incorrect 165 ms 130128 KB Output isn't correct
17 Incorrect 87 ms 130180 KB Output isn't correct
18 Correct 38 ms 129960 KB Output is correct

Subtask #2
4.375 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 140880 KB Output isn't correct
2 Incorrect 152 ms 133500 KB Output isn't correct
3 Incorrect 913 ms 157580 KB Output isn't correct
4 Incorrect 1513 ms 138252 KB Output isn't correct
5 Incorrect 454 ms 146972 KB Output isn't correct
6 Execution timed out 2063 ms 157780 KB Time limit exceeded
7 Incorrect 29 ms 141872 KB Output isn't correct
8 Incorrect 26 ms 141256 KB Output isn't correct
9 Incorrect 27 ms 127832 KB Output isn't correct
10 Incorrect 22 ms 127828 KB Output isn't correct
11 Incorrect 26 ms 141396 KB Output isn't correct
12 Incorrect 21 ms 127836 KB Output isn't correct
13 Incorrect 146 ms 133496 KB Output isn't correct
14 Incorrect 67 ms 130644 KB Output isn't correct
15 Incorrect 164 ms 132960 KB Output isn't correct
16 Incorrect 62 ms 128340 KB Output isn't correct
17 Incorrect 414 ms 138272 KB Output isn't correct
18 Incorrect 662 ms 137996 KB Output isn't correct
19 Incorrect 1571 ms 138212 KB Output isn't correct
20 Incorrect 195 ms 137296 KB Output isn't correct
21 Incorrect 506 ms 149196 KB Output isn't correct
22 Incorrect 436 ms 146884 KB Output isn't correct
23 Incorrect 537 ms 143676 KB Output isn't correct
24 Incorrect 1272 ms 149152 KB Output isn't correct
25 Incorrect 675 ms 157420 KB Output isn't correct
26 Correct 455 ms 152552 KB Output is correct
27 Correct 557 ms 157400 KB Output is correct
28 Execution timed out 2005 ms 158276 KB Time limit exceeded
29 Execution timed out 2080 ms 157832 KB Time limit exceeded
30 Execution timed out 2029 ms 157508 KB Time limit exceeded
31 Execution timed out 2052 ms 151256 KB Time limit exceeded
32 Incorrect 1266 ms 157528 KB Output isn't correct