oj.uz

Submission #1081881

# Submission time Handle Problem Language Result Execution time Memory
1081881 2024-08-30T12:29:35 Z MrPavlito Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 485 ms 162820 KB 
#include <bits/stdc++.h>
//#define int long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define sc second
#define endl "\n"
#define pii pair<int,int>

using namespace std;

const int MAXN = 4005;
const int mod7 = 1e9+7;
const long long inf = 1e9;
struct str
{
    int a,b,c;
};

vector<vector<int>> dist(MAXN, vector<int>(MAXN,inf));
deque<str> pq;


signed main()
{
    ios_base::sync_with_stdio(false),cin.tie(0), cout.tie(0);
    int tt=1;
    //cin >> tt;
    while(tt--)
    {
        int n,m;
        cin >> n >> m;
        vector<string>mat(n);
        for(int i=0; i<n; i++)cin >> mat[i];
        dist[0][0] = 0;
        pq.pb({0,0,0});
        while(!pq.empty())
        {
            auto it = pq.front();
            pq.pop_front();
            int i = it.b;
            int j = it.c;
            int d = it.a;
            if(i>0 && mat[i-1][j]!='.')
            {
                int cost = (mat[i][j] != mat[i-1][j]);
                if(dist[i-1][j] > dist[i][j] + cost)
                {
                    dist[i-1][j] = dist[i][j] + cost;
                    if(cost)pq.push_back({dist[i-1][j], i-1, j});
                    else pq.push_front({dist[i-1][j], i-1, j});
                }
            }

            if(i<n-1&& mat[i+1][j]!='.')
            {
                int cost = (mat[i][j] != mat[i+1][j]);
                if(dist[i+1][j] > dist[i][j] + cost)
                {

                    dist[i+1][j] = dist[i][j] + cost;
                    if(cost)pq.push_back({dist[i+1][j], i+1, j});
                    else pq.push_front({dist[i+1][j], i+1, j});
                }
            }

            if(j>0&& mat[i][j-1]!='.')
            {
                int cost = (mat[i][j] != mat[i][j-1]);
                if(dist[i][j-1] > dist[i][j] + cost)
                {

                    dist[i][j-1] = dist[i][j] + cost;
                    if(cost)pq.push_back({dist[i][j-1], i, j-1});
                    else pq.push_front({dist[i][j-1], i, j-1});
                }
            }
            if(j<m-1 && mat[i][j+1]!='.')
            {
                int cost = (mat[i][j] != mat[i][j+1]);
                if(dist[i][j+1] > dist[i][j] + cost)
                {
                    dist[i][j+1] = dist[i][j] + cost;
                    if(cost)pq.push_back({dist[i][j+1], i, j+1});
                    else pq.push_front({dist[i][j+1], i, j+1});

                }
            }

        }
        int mx = 0;
        for(int i = 0;i<n; i++)
        {
            for(int j=0; j<m; j++)if(dist[i][j]!=inf)mx = max(mx, dist[i][j]);
        }
        cout << mx+1 << endl;

    }
}

/*
3 4
FFRR
RFRF
RFRF
*/

Compilation message

tracks.cpp: In function 'int main()':
tracks.cpp:44:17: warning: unused variable 'd' [-Wunused-variable]
   44 |             int d = it.a;
      |                 ^

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 63832 KB Output is correct
2 Correct 36 ms 63144 KB Output is correct
3 Correct 32 ms 63268 KB Output is correct
4 Correct 34 ms 63896 KB Output is correct
5 Correct 31 ms 63316 KB Output is correct
6 Correct 31 ms 63316 KB Output is correct
7 Correct 27 ms 63324 KB Output is correct
8 Correct 31 ms 63320 KB Output is correct
9 Correct 32 ms 63316 KB Output is correct
10 Correct 38 ms 63316 KB Output is correct
11 Correct 31 ms 63404 KB Output is correct
12 Correct 31 ms 63576 KB Output is correct
13 Correct 31 ms 63492 KB Output is correct
14 Correct 35 ms 63316 KB Output is correct
15 Correct 34 ms 63832 KB Output is correct
16 Correct 38 ms 63828 KB Output is correct
17 Correct 33 ms 63944 KB Output is correct
18 Correct 34 ms 63824 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 63312 KB Output is correct
2 Correct 55 ms 66384 KB Output is correct
3 Correct 154 ms 96628 KB Output is correct
4 Correct 70 ms 70996 KB Output is correct
5 Correct 122 ms 81780 KB Output is correct
6 Correct 483 ms 115948 KB Output is correct
7 Correct 38 ms 63316 KB Output is correct
8 Correct 32 ms 63324 KB Output is correct
9 Correct 28 ms 63324 KB Output is correct
10 Correct 31 ms 63312 KB Output is correct
11 Correct 31 ms 63312 KB Output is correct
12 Correct 32 ms 63320 KB Output is correct
13 Correct 56 ms 66588 KB Output is correct
14 Correct 44 ms 65240 KB Output is correct
15 Correct 36 ms 65364 KB Output is correct
16 Correct 45 ms 64592 KB Output is correct
17 Correct 104 ms 71508 KB Output is correct
18 Correct 67 ms 71328 KB Output is correct
19 Correct 84 ms 70968 KB Output is correct
20 Correct 63 ms 70204 KB Output is correct
21 Correct 117 ms 82364 KB Output is correct
22 Correct 131 ms 81832 KB Output is correct
23 Correct 153 ms 79188 KB Output is correct
24 Correct 108 ms 82000 KB Output is correct
25 Correct 194 ms 96892 KB Output is correct
26 Correct 318 ms 162820 KB Output is correct
27 Correct 392 ms 122620 KB Output is correct
28 Correct 485 ms 116196 KB Output is correct
29 Correct 463 ms 116472 KB Output is correct
30 Correct 461 ms 117964 KB Output is correct
31 Correct 322 ms 85172 KB Output is correct
32 Correct 351 ms 119640 KB Output is correct