oj.uz

Submission #1099383

# Submission time Handle Problem Language Result Execution time Memory
1099383 2024-10-11T08:55:28 Z YFHHFY Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 528 ms 224220 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 <int  ,int >> 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 0 ms 604 KB Output is correct
3 Correct 0 ms 860 KB Output is correct
4 Correct 5 ms 5820 KB Output is correct
5 Correct 2 ms 3420 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 0 ms 860 KB Output is correct
9 Correct 1 ms 1116 KB Output is correct
10 Correct 2 ms 2908 KB Output is correct
11 Correct 2 ms 2396 KB Output is correct
12 Correct 3 ms 3420 KB Output is correct
13 Correct 3 ms 3164 KB Output is correct
14 Correct 2 ms 3420 KB Output is correct
15 Correct 8 ms 6236 KB Output is correct
16 Correct 11 ms 6144 KB Output is correct
17 Correct 7 ms 5980 KB Output is correct
18 Correct 6 ms 6028 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 31068 KB Output is correct
2 Correct 33 ms 22604 KB Output is correct
3 Correct 154 ms 141364 KB Output is correct
4 Correct 57 ms 44636 KB Output is correct
5 Correct 120 ms 94548 KB Output is correct
6 Correct 521 ms 169136 KB Output is correct
7 Correct 12 ms 32604 KB Output is correct
8 Correct 13 ms 31052 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 13 ms 31924 KB Output is correct
12 Correct 1 ms 1628 KB Output is correct
13 Correct 30 ms 22576 KB Output is correct
14 Correct 18 ms 14684 KB Output is correct
15 Correct 14 ms 16220 KB Output is correct
16 Correct 16 ms 8536 KB Output is correct
17 Correct 83 ms 48216 KB Output is correct
18 Correct 59 ms 47440 KB Output is correct
19 Correct 57 ms 44636 KB Output is correct
20 Correct 45 ms 41304 KB Output is correct
21 Correct 102 ms 97876 KB Output is correct
22 Correct 129 ms 94544 KB Output is correct
23 Correct 152 ms 80720 KB Output is correct
24 Correct 102 ms 96080 KB Output is correct
25 Correct 226 ms 141396 KB Output is correct
26 Correct 274 ms 224220 KB Output is correct
27 Correct 441 ms 198572 KB Output is correct
28 Correct 528 ms 168880 KB Output is correct
29 Correct 518 ms 170420 KB Output is correct
30 Correct 476 ms 179816 KB Output is correct
31 Correct 346 ms 106840 KB Output is correct
32 Correct 320 ms 177500 KB Output is correct