oj.uz

Submission #1081872

# Submission time Handle Problem Language Result Execution time Memory
1081872 2024-08-30T12:24:39 Z MrPavlito Tracks in the Snow (BOI13_tracks) C++17
82.5 / 100
 2000 ms 160316 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 {
        if(a.a == b.a)
        {
            if(a.b == b.b)return a.c<b.c;
            return a.b<b.b;
        }
        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;
            int d = it->a;
            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;

    }
}

/*
3 4
FFRR
RFRF
RFRF
*/

Compilation message

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

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 64308 KB Output is correct
2 Correct 37 ms 63316 KB Output is correct
3 Correct 31 ms 63324 KB Output is correct
4 Correct 54 ms 64592 KB Output is correct
5 Correct 36 ms 63312 KB Output is correct
6 Correct 32 ms 63316 KB Output is correct
7 Correct 38 ms 63352 KB Output is correct
8 Correct 34 ms 63324 KB Output is correct
9 Correct 31 ms 63312 KB Output is correct
10 Correct 35 ms 63312 KB Output is correct
11 Correct 37 ms 63744 KB Output is correct
12 Correct 44 ms 63568 KB Output is correct
13 Correct 36 ms 63316 KB Output is correct
14 Correct 34 ms 63324 KB Output is correct
15 Correct 61 ms 63832 KB Output is correct
16 Correct 76 ms 64080 KB Output is correct
17 Correct 48 ms 63832 KB Output is correct
18 Correct 61 ms 64704 KB Output is correct

Subtask #2
52.5 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 63324 KB Output is correct
2 Correct 130 ms 66644 KB Output is correct
3 Correct 342 ms 96792 KB Output is correct
4 Correct 158 ms 70996 KB Output is correct
5 Correct 192 ms 81748 KB Output is correct
6 Execution timed out 2070 ms 148564 KB Time limit exceeded
7 Correct 29 ms 63320 KB Output is correct
8 Correct 31 ms 63484 KB Output is correct
9 Correct 30 ms 63576 KB Output is correct
10 Correct 30 ms 63316 KB Output is correct
11 Correct 33 ms 63312 KB Output is correct
12 Correct 29 ms 63324 KB Output is correct
13 Correct 177 ms 66640 KB Output is correct
14 Correct 106 ms 65080 KB Output is correct
15 Correct 45 ms 65360 KB Output is correct
16 Correct 87 ms 64808 KB Output is correct
17 Correct 343 ms 71764 KB Output is correct
18 Correct 86 ms 71444 KB Output is correct
19 Correct 149 ms 71000 KB Output is correct
20 Correct 159 ms 70176 KB Output is correct
21 Correct 248 ms 82500 KB Output is correct
22 Correct 229 ms 81732 KB Output is correct
23 Correct 631 ms 79656 KB Output is correct
24 Correct 210 ms 82112 KB Output is correct
25 Correct 308 ms 96916 KB Output is correct
26 Execution timed out 2041 ms 88872 KB Time limit exceeded
27 Execution timed out 2051 ms 108140 KB Time limit exceeded
28 Execution timed out 2094 ms 147600 KB Time limit exceeded
29 Execution timed out 2092 ms 160316 KB Time limit exceeded
30 Execution timed out 2088 ms 153308 KB Time limit exceeded
31 Execution timed out 2019 ms 87528 KB Time limit exceeded
32 Execution timed out 2017 ms 102512 KB Time limit exceeded