oj.uz

Submission #1081645

# Submission time Handle Problem Language Result Execution time Memory
1081645 2024-08-30T08:44:52 Z MrPavlito Tracks in the Snow (BOI13_tracks) C++17
27.3958 / 100
 314 ms 97144 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;
};
struct cmp {
    bool operator() (str a, str b) const {
        return a.a < b.a;
    }
};
vector<vector<int>> dist(MAXN, vector<int>(MAXN,inf));
set<str, cmp> 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.insert({0,0,0});
        while(!pq.empty())
        {
            auto it = pq.begin();
            int i = it->b;
            int j = it->c;
            pq.erase(it);
            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)
                {
                    pq.erase({dist[i-1][j], i-1, j});
                    dist[i-1][j] = dist[i][j] + cost;
                    pq.insert({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)
                {
                    pq.erase({dist[i+1][j], i+1, j});
                    dist[i+1][j] = dist[i][j] + cost;
                    pq.insert({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)
                {
                    pq.erase({dist[i][j-1], i, j-1});
                    dist[i][j-1] = dist[i][j] + cost;
                    pq.insert({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)
                {
                    pq.erase({dist[i][j+1], i, j+1});
                    dist[i][j+1] = dist[i][j] + cost;
                    pq.insert({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;

    }
}

Subtask #1
3.33333333333 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 63828 KB Output isn't correct
2 Correct 30 ms 63576 KB Output is correct
3 Incorrect 33 ms 63236 KB Output isn't correct
4 Incorrect 31 ms 63572 KB Output isn't correct
5 Incorrect 27 ms 63312 KB Output isn't correct
6 Correct 30 ms 63324 KB Output is correct
7 Incorrect 32 ms 63380 KB Output isn't correct
8 Incorrect 31 ms 63316 KB Output isn't correct
9 Incorrect 31 ms 63316 KB Output isn't correct
10 Incorrect 30 ms 63300 KB Output isn't correct
11 Incorrect 30 ms 63324 KB Output isn't correct
12 Incorrect 31 ms 63348 KB Output isn't correct
13 Incorrect 31 ms 63312 KB Output isn't correct
14 Incorrect 32 ms 63324 KB Output isn't correct
15 Incorrect 30 ms 63652 KB Output isn't correct
16 Incorrect 30 ms 63836 KB Output isn't correct
17 Incorrect 34 ms 63652 KB Output isn't correct
18 Incorrect 29 ms 63568 KB Output isn't correct

Subtask #2
24.0625 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 63316 KB Output is correct
2 Incorrect 34 ms 66388 KB Output isn't correct
3 Incorrect 68 ms 96724 KB Output isn't correct
4 Incorrect 42 ms 70992 KB Output isn't correct
5 Correct 187 ms 81804 KB Output is correct
6 Incorrect 71 ms 96592 KB Output isn't correct
7 Correct 30 ms 63316 KB Output is correct
8 Correct 33 ms 63324 KB Output is correct
9 Incorrect 31 ms 63460 KB Output isn't correct
10 Correct 31 ms 63316 KB Output is correct
11 Incorrect 32 ms 63316 KB Output isn't correct
12 Correct 32 ms 63312 KB Output is correct
13 Incorrect 35 ms 66396 KB Output isn't correct
14 Incorrect 30 ms 65112 KB Output isn't correct
15 Correct 43 ms 65364 KB Output is correct
16 Incorrect 33 ms 64680 KB Output isn't correct
17 Incorrect 43 ms 71504 KB Output isn't correct
18 Correct 78 ms 71508 KB Output is correct
19 Incorrect 38 ms 70856 KB Output isn't correct
20 Incorrect 42 ms 70224 KB Output isn't correct
21 Incorrect 56 ms 82580 KB Output isn't correct
22 Correct 186 ms 82244 KB Output is correct
23 Incorrect 50 ms 79184 KB Output isn't correct
24 Correct 144 ms 82068 KB Output is correct
25 Incorrect 72 ms 97144 KB Output isn't correct
26 Correct 314 ms 88792 KB Output is correct
27 Incorrect 68 ms 96548 KB Output isn't correct
28 Incorrect 69 ms 96716 KB Output isn't correct
29 Incorrect 74 ms 96596 KB Output isn't correct
30 Incorrect 70 ms 96168 KB Output isn't correct
31 Incorrect 60 ms 84424 KB Output isn't correct
32 Incorrect 71 ms 96564 KB Output isn't correct