oj.uz

Submission #776249

# Submission time Handle Problem Language Result Execution time Memory
776249 2023-07-07T13:41:45 Z amine_aroua Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 653 ms 137276 KB 
#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define vl vector<long long>
#define vii vector<pair<int,int>>
#define vll vector<pair<long long,long long>>
#define pb push_back
#define ll long long
#define ld long double
#define nl '\n'
#define boost ios::sync_with_stdio(false)
#define mp make_pair
#define se second
#define fi first
#define fore(i, y) for(int i = 0; i < y; i++)
#define forr(i,x,y) for(int i = x;i<=y;i++)
#define forn(i,y,x) for(int i = y; i >= x; i--)
#define all(v) v.begin(),v.end()
#define sz(v) v.size()
#define clr(v,k) memset(v,k,sizeof(v))
#define rall(v) v.rbegin() , v.rend()
#define pii pair<int,int>
#define pll pair<ll , ll>

const ll MOD = 1e9 + 7;
const ll INF = 1e9 + 1;

ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a ;} // greatest common divisor (PGCD)
ll lcm(ll a , ll b) {return a * (b / gcd(a , b));} // least common multiple (PPCM)

// HERE IS THE SOLUTION
vii coor = {{0 , 1} , {1 , 0}  ,{-1 , 0} , {0 , -1}};
int main()
{
    cin.tie(0);
    cout.tie(0);
    boost;
    int n , m;
    cin>>n>>m;
    char grid[n][m];
    fore(i , n)
    {
        fore(j , m)
        {
            cin>>grid[i][j];
        }
    }
    int dist[n][m];
    pii cur  = {0 , 0};
    fore(i , n)
    {
        fore(j , m)
        {
            dist[i][j] = INF;
        }
    }
    dist[0][0] = 0;
    deque<pii> dq;
    dq.push_front(cur);
    while(!dq.empty())
    {
        pii node = dq.front();
        dq.pop_front();
        for(auto  p: coor)
        {
            int nx = p.fi + node.fi , ny = p.se + node.se;
            if(nx < 0 || ny < 0 || nx>=n || ny>=m || grid[nx][ny] == '.')continue;
            int w = 0;
            if(grid[nx][ny] != grid[node.fi][node.se])
                w = 1;
            if(dist[nx][ny] > dist[node.fi][node.se] + w)
            {
                dist[nx][ny] = w + dist[node.fi][node.se];
                if(w == 0)
                    dq.push_front({nx , ny});
                else
                    dq.push_back({nx , ny});
            }
        }
    }
    int ans = 0;
    fore(i , n)
    {
        fore(j , m)
        {
            if(grid[i][j] != '.')
                ans = max(ans , dist[i][j]);
        }
    }
    cout<<ans +1<<nl;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1748 KB Output is correct
2 Correct 0 ms 324 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 6 ms 1384 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 2 ms 508 KB Output is correct
12 Correct 5 ms 804 KB Output is correct
13 Correct 2 ms 724 KB Output is correct
14 Correct 3 ms 724 KB Output is correct
15 Correct 13 ms 1748 KB Output is correct
16 Correct 13 ms 1796 KB Output is correct
17 Correct 8 ms 1680 KB Output is correct
18 Correct 6 ms 1388 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 544 KB Output is correct
2 Correct 44 ms 9368 KB Output is correct
3 Correct 291 ms 94200 KB Output is correct
4 Correct 79 ms 22264 KB Output is correct
5 Correct 170 ms 53128 KB Output is correct
6 Correct 648 ms 108708 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Correct 2 ms 588 KB Output is correct
10 Correct 1 ms 508 KB Output is correct
11 Correct 1 ms 588 KB Output is correct
12 Correct 1 ms 360 KB Output is correct
13 Correct 41 ms 9488 KB Output is correct
14 Correct 28 ms 5532 KB Output is correct
15 Correct 18 ms 6172 KB Output is correct
16 Correct 22 ms 4044 KB Output is correct
17 Correct 111 ms 24096 KB Output is correct
18 Correct 81 ms 23792 KB Output is correct
19 Correct 88 ms 22264 KB Output is correct
20 Correct 66 ms 20424 KB Output is correct
21 Correct 174 ms 54844 KB Output is correct
22 Correct 151 ms 53116 KB Output is correct
23 Correct 212 ms 45796 KB Output is correct
24 Correct 159 ms 53628 KB Output is correct
25 Correct 383 ms 94284 KB Output is correct
26 Correct 559 ms 122360 KB Output is correct
27 Correct 553 ms 137276 KB Output is correct
28 Correct 649 ms 108636 KB Output is correct
29 Correct 653 ms 105828 KB Output is correct
30 Correct 620 ms 112720 KB Output is correct
31 Correct 539 ms 60868 KB Output is correct
32 Correct 580 ms 117288 KB Output is correct