oj.uz

Submission #484893

# Submission time Handle Problem Language Result Execution time Memory
484893 2021-11-05T17:33:08 Z ali22413836 Tracks in the Snow (BOI13_tracks) C++14
95.625 / 100
 574 ms 223936 KB 
#include <bits/stdc++.h>
#define  endl "\n"
using namespace std ;
typedef long long ll;
typedef long double ld ;
const int N=2e7;
const ll inf=1e18 ;
const ll mod = 1e9 + 7 ;
ll mypower(ll x, ll y){
    if(y == 0) return 1 ;
    if(y == 1) return x ;
    ll ret = mypower(x , y / 2);
    ret = (ret * ret) % mod;
    if(y % 2) ret = ( ret * x ) % mod ;
    return ret ;
}
ll n , m ;
char a[4000][4000] ;
ll vis[4000][4000] ;
ll sta , sta2 , en , en2 ;
ll di[] = {0 , 0 , 1 , -1} , di2[] = {1 , -1 , 0 , 0} ;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> m ;
    for(int i = 0 ; i < n ; i++){
        cin >> a[i] ;
    }
    deque < pair < ll , ll > > q ;
    q.push_back({sta , sta2}) ;
    sta = 0 , sta2 =  0 ;
    vis[sta][sta2] = 1 ;
    ll ans = 1 ;
    while(!q.empty()){
        pair < ll , ll > x  ;
        x = q.front() ;
        q.pop_front() ;
        ans = max(ans , vis[x.first][x.second])  ;
        ll i = x.first , j = x.second ;
        for(int k = 0 ; k < 4 ; k++){
            ll ni = i + di[k] , nj = j + di2[k] ;
            if(ni < n && ni >= 0 && nj < m && nj >= 0 && a[ni][nj] != '.' && vis[ni][nj] == 0){
                if(a[ni][nj] == a[i][j]){
                    q.push_front({ni , nj}) ;
                    vis[ni][nj] = vis[i][j]  ;
                }
                else{
                    q.push_back({ni , nj}) ;
                    vis[ni][nj] = vis[i][j] + 1 ;
                }
             }
        }
    }
    cout << ans << endl ;
    return 0 ;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 6072 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 10 ms 5768 KB Output is correct
5 Correct 3 ms 3020 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 716 KB Output is correct
8 Correct 1 ms 844 KB Output is correct
9 Correct 1 ms 1100 KB Output is correct
10 Correct 3 ms 2508 KB Output is correct
11 Correct 3 ms 2252 KB Output is correct
12 Correct 5 ms 3276 KB Output is correct
13 Correct 3 ms 3020 KB Output is correct
14 Correct 3 ms 3020 KB Output is correct
15 Correct 10 ms 5772 KB Output is correct
16 Correct 11 ms 6092 KB Output is correct
17 Correct 8 ms 5844 KB Output is correct
18 Correct 6 ms 5708 KB Output is correct

Subtask #2
65.625 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 30668 KB Output is correct
2 Correct 35 ms 16716 KB Output is correct
3 Incorrect 24 ms 17376 KB Output isn't correct
4 Correct 79 ms 42748 KB Output is correct
5 Correct 138 ms 62340 KB Output is correct
6 Correct 526 ms 166220 KB Output is correct
7 Correct 21 ms 32204 KB Output is correct
8 Correct 22 ms 30776 KB Output is correct
9 Correct 2 ms 716 KB Output is correct
10 Correct 0 ms 460 KB Output is correct
11 Correct 16 ms 31564 KB Output is correct
12 Correct 1 ms 1612 KB Output is correct
13 Correct 35 ms 16708 KB Output is correct
14 Correct 21 ms 11468 KB Output is correct
15 Correct 21 ms 15948 KB Output is correct
16 Correct 16 ms 6604 KB Output is correct
17 Correct 90 ms 32400 KB Output is correct
18 Correct 97 ms 47168 KB Output is correct
19 Correct 64 ms 42664 KB Output is correct
20 Correct 42 ms 27036 KB Output is correct
21 Correct 99 ms 53828 KB Output is correct
22 Correct 124 ms 62376 KB Output is correct
23 Correct 181 ms 49900 KB Output is correct
24 Correct 98 ms 52684 KB Output is correct
25 Incorrect 18 ms 15916 KB Output isn't correct
26 Correct 574 ms 223936 KB Output is correct
27 Correct 495 ms 173916 KB Output is correct
28 Correct 535 ms 166232 KB Output is correct
29 Correct 532 ms 162340 KB Output is correct
30 Correct 565 ms 172948 KB Output is correct
31 Correct 433 ms 106724 KB Output is correct
32 Correct 523 ms 166844 KB Output is correct