oj.uz

Submission #916660

# Submission time Handle Problem Language Result Execution time Memory
916660 2024-01-26T08:50:46 Z May27_th Tracks in the Snow (BOI13_tracks) C++17
19.7917 / 100
 766 ms 142356 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(g[nu][nv] == '.') weight = 0;
                if(d[nu][nv] > d[u][v] + weight){
                    d[nu][nv] = d[u][v] + weight;
                    //cout << d[nu][nv] << "\n";
                    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:67:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |         freopen("poetry.in", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
tracks.cpp:68:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |         freopen("poetry.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
tracks.cpp:71:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |         freopen("A.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
tracks.cpp:72:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |         freopen("A.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.66666666667 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 12888 KB Output isn't correct
2 Incorrect 1 ms 4444 KB Output isn't correct
3 Incorrect 1 ms 4444 KB Output isn't correct
4 Correct 7 ms 12892 KB Output is correct
5 Incorrect 7 ms 10588 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 4444 KB Output is correct
9 Incorrect 2 ms 4440 KB Output isn't correct
10 Incorrect 3 ms 6748 KB Output isn't correct
11 Correct 3 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 10588 KB Output isn't correct
15 Incorrect 14 ms 13292 KB Output isn't correct
16 Incorrect 12 ms 12892 KB Output isn't correct
17 Incorrect 13 ms 12928 KB Output isn't correct
18 Correct 7 ms 12892 KB Output is correct

Subtask #2
13.125 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 78428 KB Output isn't correct
2 Incorrect 57 ms 30812 KB Output isn't correct
3 Incorrect 525 ms 142356 KB Output isn't correct
4 Incorrect 163 ms 42224 KB Output isn't correct
5 Incorrect 264 ms 98904 KB Output isn't correct
6 Correct 699 ms 92684 KB Output is correct
7 Incorrect 14 ms 78684 KB Output isn't correct
8 Incorrect 13 ms 78428 KB Output isn't correct
9 Incorrect 3 ms 4696 KB Output isn't correct
10 Incorrect 2 ms 2652 KB Output isn't correct
11 Incorrect 14 ms 78624 KB Output isn't correct
12 Incorrect 2 ms 6748 KB Output isn't correct
13 Incorrect 54 ms 30800 KB Output isn't correct
14 Incorrect 35 ms 23132 KB Output isn't correct
15 Incorrect 40 ms 25476 KB Output isn't correct
16 Incorrect 23 ms 12344 KB Output isn't correct
17 Incorrect 140 ms 53460 KB Output isn't correct
18 Incorrect 232 ms 52616 KB Output isn't correct
19 Incorrect 140 ms 42076 KB Output isn't correct
20 Incorrect 117 ms 51296 KB Output isn't correct
21 Incorrect 304 ms 101580 KB Output isn't correct
22 Incorrect 261 ms 99216 KB Output isn't correct
23 Incorrect 260 ms 72948 KB Output isn't correct
24 Incorrect 275 ms 90820 KB Output isn't correct
25 Incorrect 766 ms 116196 KB Output isn't correct
26 Correct 428 ms 122620 KB Output is correct
27 Correct 581 ms 105524 KB Output is correct
28 Correct 698 ms 92396 KB Output is correct
29 Correct 652 ms 90892 KB Output is correct
30 Correct 642 ms 96356 KB Output is correct
31 Incorrect 421 ms 66896 KB Output isn't correct
32 Incorrect 565 ms 94464 KB Output isn't correct