oj.uz

Submission #916652

# Submission time Handle Problem Language Result Execution time Memory
916652 2024-01-26T08:41:32 Z May27_th Tracks in the Snow (BOI13_tracks) C++17
19.7917 / 100
 776 ms 122564 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]; int 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];
            d[i][j] = 1e9;
        }
    }
    deque<pair<int, int>>q;
    d[1][1] = 1;
    q.push_front(make_pair(1, 1));
    while(!q.empty()){
        int u = q.front().first;
        int v = q.front().second;
        q.pop_front();
        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){
                int weight = (g[u][v] != g[nu][nv]);
                if(d[nu][nv] > d[u][v] + weight){
                    d[nu][nv] = d[u][v] + weight;
                    if(weight == 1) q.push_back(make_pair(nu, nv));
                    else q.push_front(make_pair(nu, nv));
                }
            }
        }
    }
    int ans = 0;
    for(int i = 1; i <= h; i ++){
        for(int j = 1; j <= w; j ++){
            //cout << d[i][j] << " ";
            ans = max(ans, d[i][j]);
        }
        //cout << "\n";
    }
    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:65:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |         freopen("poetry.in", "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("poetry.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
tracks.cpp:69:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |         freopen("A.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
tracks.cpp:70:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |         freopen("A.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.66666666667 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 12892 KB Output isn't correct
2 Incorrect 1 ms 4440 KB Output isn't correct
3 Incorrect 1 ms 4444 KB Output isn't correct
4 Correct 7 ms 12812 KB Output is correct
5 Incorrect 5 ms 10844 KB Output isn't correct
6 Incorrect 1 ms 4444 KB Output isn't correct
7 Incorrect 1 ms 4444 KB Output isn't correct
8 Correct 1 ms 4440 KB Output is correct
9 Incorrect 1 ms 4440 KB Output isn't correct
10 Incorrect 3 ms 6748 KB Output isn't correct
11 Correct 2 ms 6492 KB Output is correct
12 Incorrect 6 ms 10588 KB Output isn't correct
13 Incorrect 5 ms 10844 KB Output isn't correct
14 Incorrect 5 ms 10708 KB Output isn't correct
15 Incorrect 13 ms 13144 KB Output isn't correct
16 Incorrect 11 ms 12892 KB Output isn't correct
17 Incorrect 11 ms 12904 KB Output isn't correct
18 Correct 7 ms 12888 KB Output is correct

Subtask #2
13.125 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 78492 KB Output isn't correct
2 Incorrect 55 ms 30876 KB Output isn't correct
3 Incorrect 506 ms 121920 KB Output isn't correct
4 Incorrect 132 ms 42220 KB Output isn't correct
5 Incorrect 240 ms 99264 KB Output isn't correct
6 Correct 630 ms 92632 KB Output is correct
7 Incorrect 15 ms 78680 KB Output isn't correct
8 Incorrect 14 ms 78424 KB Output isn't correct
9 Incorrect 3 ms 4700 KB Output isn't correct
10 Incorrect 1 ms 2652 KB Output isn't correct
11 Incorrect 13 ms 78408 KB Output isn't correct
12 Incorrect 2 ms 6748 KB Output isn't correct
13 Incorrect 56 ms 30812 KB Output isn't correct
14 Incorrect 30 ms 23120 KB Output isn't correct
15 Incorrect 38 ms 25392 KB Output isn't correct
16 Incorrect 22 ms 12380 KB Output isn't correct
17 Incorrect 139 ms 53428 KB Output isn't correct
18 Incorrect 202 ms 52708 KB Output isn't correct
19 Incorrect 140 ms 42068 KB Output isn't correct
20 Incorrect 118 ms 46676 KB Output isn't correct
21 Incorrect 301 ms 91336 KB Output isn't correct
22 Incorrect 252 ms 99428 KB Output isn't correct
23 Incorrect 261 ms 72948 KB Output isn't correct
24 Incorrect 248 ms 89192 KB Output isn't correct
25 Incorrect 776 ms 116564 KB Output isn't correct
26 Correct 399 ms 122564 KB Output is correct
27 Correct 531 ms 105764 KB Output is correct
28 Correct 630 ms 92464 KB Output is correct
29 Correct 664 ms 90816 KB Output is correct
30 Correct 583 ms 96652 KB Output is correct
31 Incorrect 403 ms 66904 KB Output isn't correct
32 Incorrect 518 ms 94612 KB Output isn't correct