oj.uz

Submission #1099381

# Submission time Handle Problem Language Result Execution time Memory
1099381 2024-10-11T08:54:54 Z YFHHFY Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 531 ms 169552 KB 
#include<bits/stdc++.h>
#define tizoboz ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define ld long double
#define pb push_back
#define int long long
#define itn int
#define ss set <int>
#define prq priority_queue <int>
#define endl '\n'
const ll MOD = 1e9 + 7;
#define md(x) (((x%MOD)+MOD)%MOD)
#define vi vector <int>
#define vl vector<ll>
#define str string 
#define mp make_pair
#define mata int32_t
#define sz size
#define lc id *2
#define rc lc +1
#define SZ(x)           (int)x.size()
#define mid (l+r)/2
#define cn cin
#define ct cout
#define sep " "
#define F first
#define X first
#define S second
#define Y second
using namespace std;
typedef pair <int , int> pii;
const ll maxn = 4e3 + 5 ;
const int Lg = 23;
const ll inf = 2e9;
const int dx[] = {-1 , 0 , 1,0}   , dy[] = {0,-1,0,1};
int n , m , d[maxn][maxn];
char a[maxn][maxn];
inline bool check (int x , int y){
    return (1 <= x && x <= n && 1 <= y && y<= m);
}
void solve (){
    cn >> n >> m;
    for (int i =1 ;i<= n ; i++){
        cn >> a[i]+1;
        for (int j = 1 ; j <= m ; j++){
            d[i][j] = inf;
        }
    }
    deque <pair <short  ,short >> q;
    q.pb(mp(1,1));
    d[1][1] = 1;
    while (SZ(q)){
        int x = q.front().F , y = q.front().S;
        q.pop_front();
        for (int i = 0 ; i < 4 ; i++){
            int xx = x + dx[i];
            int yy = y + dy[i];
            if (check(xx , yy) && a[xx][yy] != '.'){
                int val = d[x][y] + (a[x][y] != a[xx][yy]);
                if (d[xx][yy] > val){
                    d[xx][yy] = val;
                    if (a[x][y] == a[xx][yy]){
                        q.push_front(mp(xx,yy));
                    }
                    else{
                        q.pb(mp(xx,yy));
                    }
                }
            }
        }
    }
    int ans = 0;
    for (int i = 1 ; i<= n ; i++){
        for (int j = 1 ; j <= m ; j++){
            if (a[i][j] != '.'){
                ans = max (ans , d[i][j]);
            }
        }
    }
    ct << ans << endl;
}
mata main(){
    tizoboz;
    int tt = 1;
    // cn >> tt;
    while (tt--){
        solve();
    }
    return 0;
}

Compilation message

tracks.cpp: In function 'void solve()':
tracks.cpp:44:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |         cn >> a[i]+1;
      |               ~~~~^~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 6236 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 5 ms 5708 KB Output is correct
5 Correct 2 ms 3420 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 0 ms 860 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 1 ms 1116 KB Output is correct
10 Correct 3 ms 2908 KB Output is correct
11 Correct 3 ms 2396 KB Output is correct
12 Correct 6 ms 3460 KB Output is correct
13 Correct 3 ms 3420 KB Output is correct
14 Correct 2 ms 3420 KB Output is correct
15 Correct 9 ms 6236 KB Output is correct
16 Correct 9 ms 6240 KB Output is correct
17 Correct 8 ms 6132 KB Output is correct
18 Correct 9 ms 5468 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 31324 KB Output is correct
2 Correct 52 ms 23320 KB Output is correct
3 Correct 179 ms 155160 KB Output is correct
4 Correct 67 ms 47336 KB Output is correct
5 Correct 142 ms 102084 KB Output is correct
6 Correct 531 ms 162184 KB Output is correct
7 Correct 13 ms 32604 KB Output is correct
8 Correct 13 ms 31324 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 1 ms 756 KB Output is correct
11 Correct 13 ms 31996 KB Output is correct
12 Correct 1 ms 1628 KB Output is correct
13 Correct 37 ms 23388 KB Output is correct
14 Correct 21 ms 14940 KB Output is correct
15 Correct 27 ms 16540 KB Output is correct
16 Correct 17 ms 8540 KB Output is correct
17 Correct 97 ms 50936 KB Output is correct
18 Correct 69 ms 50516 KB Output is correct
19 Correct 65 ms 47196 KB Output is correct
20 Correct 42 ms 43476 KB Output is correct
21 Correct 114 ms 105448 KB Output is correct
22 Correct 130 ms 102068 KB Output is correct
23 Correct 155 ms 87032 KB Output is correct
24 Correct 108 ms 103672 KB Output is correct
25 Correct 250 ms 155216 KB Output is correct
26 Correct 233 ms 159244 KB Output is correct
27 Correct 358 ms 169552 KB Output is correct
28 Correct 529 ms 162128 KB Output is correct
29 Correct 497 ms 162644 KB Output is correct
30 Correct 468 ms 162368 KB Output is correct
31 Correct 366 ms 114768 KB Output is correct
32 Correct 333 ms 164320 KB Output is correct