oj.uz

Submission #1020592

# Submission time Handle Problem Language Result Execution time Memory
1020592 2024-07-12T07:22:05 Z NguyenPhucThang Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 643 ms 139108 KB 
#include <bits/stdc++.h>
#define forr(i, a, b) for (int i = (a); i <= (b); i++)
#define ford(i, a, b) for (int i = (a); i >= (b); i--)
#define forf(i, a, b) for (int i = (a); i < (b); i++)
#define fi first
#define se second
#define pb push_back
#define all(v) v.begin(), v.end()
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vii vector<pii>
#define mask(i) (1LL << (i))
#define bit(x, i) (((x) >> (i)) & 1)
#define bp __builtin_popcountll
#define file "test"

using namespace std;
const int base = 31;
const ll mod = 1e9 + 7;
const ll oo = 1e18;
const int N = 4005;

char a[N][N];
int d[N][N];
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

int main()
{
   ios_base::sync_with_stdio(0);
   cin.tie(0);

   int m, n;
   cin >> m >> n;
   forr(i, 1, m) forr(j, 1, n) cin >> a[i][j];

   memset(d, 63, sizeof d);

   deque<pii> dq;
   dq.push_back({1, 1});

   d[1][1] = 1;

   int res = 0;

   while (!dq.empty()){
      pii u = dq.front();
      dq.pop_front();
      res = max(res, d[u.fi][u.se]);
      forr(i, 0, 3){
         int x = u.fi + dx[i], y = u.se + dy[i];
         if (1 <= x && x <= m && 1 <= y && y <= n && a[x][y] != '.'){
            if (d[u.fi][u.se] < d[x][y] && a[u.fi][u.se] == a[x][y]){
               dq.push_front({x, y});
               d[x][y] = d[u.fi][u.se];
            } 
            else if (d[u.fi][u.se] + 1 < d[x][y] && a[u.fi][u.se] != a[x][y]){
               dq.push_back({x, y});
               d[x][y] = d[u.fi][u.se] + 1;
            }
         }
      }
   }  
   
   cout << res;

   return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 65360 KB Output is correct
2 Correct 31 ms 63472 KB Output is correct
3 Correct 31 ms 63320 KB Output is correct
4 Correct 35 ms 65372 KB Output is correct
5 Correct 34 ms 64348 KB Output is correct
6 Correct 31 ms 63324 KB Output is correct
7 Correct 36 ms 63316 KB Output is correct
8 Correct 31 ms 63420 KB Output is correct
9 Correct 29 ms 63612 KB Output is correct
10 Correct 35 ms 64080 KB Output is correct
11 Correct 31 ms 64064 KB Output is correct
12 Correct 33 ms 64336 KB Output is correct
13 Correct 32 ms 64340 KB Output is correct
14 Correct 32 ms 64584 KB Output is correct
15 Correct 39 ms 65424 KB Output is correct
16 Correct 41 ms 65188 KB Output is correct
17 Correct 42 ms 65468 KB Output is correct
18 Correct 36 ms 65360 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 78164 KB Output is correct
2 Correct 70 ms 69460 KB Output is correct
3 Correct 273 ms 94452 KB Output is correct
4 Correct 98 ms 74068 KB Output is correct
5 Correct 186 ms 83564 KB Output is correct
6 Correct 641 ms 108964 KB Output is correct
7 Correct 34 ms 78932 KB Output is correct
8 Correct 35 ms 78172 KB Output is correct
9 Correct 41 ms 63236 KB Output is correct
10 Correct 30 ms 63060 KB Output is correct
11 Correct 33 ms 78416 KB Output is correct
12 Correct 30 ms 63824 KB Output is correct
13 Correct 73 ms 69460 KB Output is correct
14 Correct 57 ms 67664 KB Output is correct
15 Correct 51 ms 68052 KB Output is correct
16 Correct 53 ms 65272 KB Output is correct
17 Correct 146 ms 75016 KB Output is correct
18 Correct 113 ms 74852 KB Output is correct
19 Correct 100 ms 74144 KB Output is correct
20 Correct 97 ms 73344 KB Output is correct
21 Correct 187 ms 84424 KB Output is correct
22 Correct 196 ms 83616 KB Output is correct
23 Correct 268 ms 80468 KB Output is correct
24 Correct 171 ms 84140 KB Output is correct
25 Correct 316 ms 94288 KB Output is correct
26 Correct 497 ms 139108 KB Output is correct
27 Correct 495 ms 120064 KB Output is correct
28 Correct 643 ms 108940 KB Output is correct
29 Correct 620 ms 106048 KB Output is correct
30 Correct 583 ms 112364 KB Output is correct
31 Correct 476 ms 86100 KB Output is correct
32 Correct 484 ms 118400 KB Output is correct