oj.uz

Submission #749471

# Submission time Handle Problem Language Result Execution time Memory
749471 2023-05-28T05:28:33 Z taitruong270 Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 805 ms 236108 KB 
/*==============================================================================================================
         __                    __                                             _____     ______    _______
        |  |                  |  |                                           /  __ \   / _____|  / ______|     
      __|  |__              __|  |__                                         |_|  | |  | |       | |  
     |__|   __|            |__|   __|                                             | |  | |____   | |_____ 
        |  |    _____   _     |  |    ____  __  __  ____    _____    _____       / /   \ ___  \  |  ___  \
        |  |   /  _  \ | |    |  |   /  _/ | | | | /  _  \ /  __ \  /  _  \     / /         | |  | |   | |
        |  |_  | |_| | | |    |  |_  | |   | |_| | | |_| | | |  | | | |_| |    / /___   ____| |  | |___| |
        \____\ \____/| |_|    \____\ |_|   \_____/ \_____/ |_|  |_| \____ |   |______| |______/  \_______/
                                                                        | |
                                                                      __/ |
                                                                     |___/  
                                        Pratice, practice, and practice
I hated every minute of training, but I said, ‘Don’t quit. Suffer now and live the rest of your life as a champion.' - Mohamed Ali 
                              You may not be the best, but must be the most effort
                                          Noi dau + Suy ngam = Tien bo 
==============================================================================================================*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const ll maxn = 200005;
const ll mod = 1e9+7;
ll n, m, depth[4005][4005], dx[]={0, 0, -1, 1}, dy[]={1, -1, 0, 0}, ans;
char c[4005][4005];

bool check(ll x, ll y)
{
  if (x>=1 && x<=n && y>=1 && y<=m && c[x][y]!='.') return true;
  return false;
}

void solve()
{
    cin>>n>>m;
    for (ll i=1; i<=n; i++)
      for (ll j=1; j<=m; j++) cin>>c[i][j];
    deque<pair<ll, ll>> dq;
    dq.push_back({1, 1});
    depth[1][1]=1;
    while (!dq.empty())
    {
      auto [x, y]=dq.front();
      ans=max(ans, depth[x][y]);
      dq.pop_front();
      for (ll i=0; i<4; i++)
      {
        ll new_x=x+dx[i], new_y=y+dy[i];
        if (check(new_x, new_y)==true && depth[new_x][new_y]==0)
        {
          if (c[x][y]==c[new_x][new_y]) 
          {
            depth[new_x][new_y]=depth[x][y];
            dq.push_front({new_x, new_y});
          }
          else 
          {
            depth[new_x][new_y]=depth[x][y]+1;
            dq.push_back({new_x, new_y});
          }
        }
      }
    }
    cout<<ans;
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    clock_t start = clock();
    solve();
    clock_t end = clock();
    cerr<<"Time: "<<fixed<<setprecision(10)<<double(end-start)/double(CLOCKS_PER_SEC)<<"\n";
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 6356 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 11 ms 6032 KB Output is correct
5 Correct 4 ms 3156 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 852 KB Output is correct
9 Correct 1 ms 1108 KB Output is correct
10 Correct 3 ms 2644 KB Output is correct
11 Correct 3 ms 2388 KB Output is correct
12 Correct 6 ms 3412 KB Output is correct
13 Correct 4 ms 3156 KB Output is correct
14 Correct 4 ms 3156 KB Output is correct
15 Correct 13 ms 6016 KB Output is correct
16 Correct 14 ms 6472 KB Output is correct
17 Correct 11 ms 6100 KB Output is correct
18 Correct 9 ms 5972 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 31000 KB Output is correct
2 Correct 55 ms 18480 KB Output is correct
3 Correct 351 ms 91216 KB Output is correct
4 Correct 114 ms 46496 KB Output is correct
5 Correct 251 ms 71116 KB Output is correct
6 Correct 789 ms 184040 KB Output is correct
7 Correct 18 ms 32420 KB Output is correct
8 Correct 17 ms 31060 KB Output is correct
9 Correct 3 ms 852 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 19 ms 31828 KB Output is correct
12 Correct 2 ms 1724 KB Output is correct
13 Correct 55 ms 18360 KB Output is correct
14 Correct 32 ms 12360 KB Output is correct
15 Correct 32 ms 16972 KB Output is correct
16 Correct 24 ms 7360 KB Output is correct
17 Correct 134 ms 36188 KB Output is correct
18 Correct 127 ms 51456 KB Output is correct
19 Correct 110 ms 46572 KB Output is correct
20 Correct 88 ms 30368 KB Output is correct
21 Correct 210 ms 63136 KB Output is correct
22 Correct 249 ms 71116 KB Output is correct
23 Correct 268 ms 57468 KB Output is correct
24 Correct 208 ms 61644 KB Output is correct
25 Correct 631 ms 157176 KB Output is correct
26 Correct 703 ms 236108 KB Output is correct
27 Correct 769 ms 200260 KB Output is correct
28 Correct 795 ms 183968 KB Output is correct
29 Correct 805 ms 178968 KB Output is correct
30 Correct 768 ms 186124 KB Output is correct
31 Correct 554 ms 116820 KB Output is correct
32 Correct 733 ms 182884 KB Output is correct