oj.uz

Submission #707951

# Submission time Handle Problem Language Result Execution time Memory
707951 2023-03-10T15:01:13 Z spensa Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 1214 ms 277680 KB 
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>

int L[] = {0, 0, 1, -1};
int R[] = {1, -1, 0, 0};

const int MXN = 4020;
int arr[MXN][MXN] = {0};
int dist[MXN][MXN] = {0};
int vis[MXN][MXN] = {0};
int h, w;

bool check(int a, int b){
    if(a<1 || b<1 || a>h || b>w) return false;
    else return true;
}

int main(){
    //faster io
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin>>h>>w;
    string str;
    char c;
    int a, b, n1, n2, mx;


    for(int i=1; i<=h; i++){
        cin>>str;
        for(int j=1; j<=w; j++){
            c = str[j-1];
            if(c=='.') arr[i][j] = 0;
            else if(c=='R') arr[i][j] = 1;
            else arr[i][j] = 2;
        }
    }

    deque<pii> q;
    q.push_back({1,1});
    dist[1][1] = 1;

    while(!q.empty()){
        a = q.front().first;
        b = q.front().second;
        q.pop_front();

        for(int i=0; i<4; i++){
            n1 = a + L[i];
            n2 = b + R[i];
            if(!check(n1, n2)) continue;
            if(arr[n1][n2]==0) continue;
            if(vis[n1][n2]) continue;
            
            if(arr[a][b]==arr[n1][n2]){
                q.push_front({n1,n2});
                dist[n1][n2] = dist[a][b];
            }
            else{
                q.push_back({n1,n2});
                dist[n1][n2] = dist[a][b] + 1;
            }
                
        }

        vis[a][b] = 1;
    }

    mx = 0;

    for(int i=1; i<=h; i++){
        for(int j=1; j<=w; j++){
            // cout<<dist[i][j]<<" ";
            mx = max(mx, dist[i][j]);    
        }
        // cout<<"\n";
    }

    cout<<mx<<"\n";

}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 9420 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 976 KB Output is correct
4 Correct 13 ms 8632 KB Output is correct
5 Correct 4 ms 4692 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 2 ms 1108 KB Output is correct
9 Correct 1 ms 1620 KB Output is correct
10 Correct 5 ms 3924 KB Output is correct
11 Correct 4 ms 3376 KB Output is correct
12 Correct 10 ms 4916 KB Output is correct
13 Correct 4 ms 4692 KB Output is correct
14 Correct 5 ms 4764 KB Output is correct
15 Correct 21 ms 9044 KB Output is correct
16 Correct 30 ms 9464 KB Output is correct
17 Correct 15 ms 9044 KB Output is correct
18 Correct 15 ms 8668 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 46924 KB Output is correct
2 Correct 68 ms 29552 KB Output is correct
3 Correct 352 ms 162604 KB Output is correct
4 Correct 122 ms 68880 KB Output is correct
5 Correct 174 ms 121500 KB Output is correct
6 Correct 1214 ms 236500 KB Output is correct
7 Correct 28 ms 48952 KB Output is correct
8 Correct 22 ms 46872 KB Output is correct
9 Correct 4 ms 1076 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 22 ms 48084 KB Output is correct
12 Correct 2 ms 2388 KB Output is correct
13 Correct 71 ms 29644 KB Output is correct
14 Correct 41 ms 19800 KB Output is correct
15 Correct 32 ms 25012 KB Output is correct
16 Correct 36 ms 11484 KB Output is correct
17 Correct 172 ms 61552 KB Output is correct
18 Correct 110 ms 75112 KB Output is correct
19 Correct 101 ms 68940 KB Output is correct
20 Correct 90 ms 54180 KB Output is correct
21 Correct 196 ms 120120 KB Output is correct
22 Correct 171 ms 121428 KB Output is correct
23 Correct 322 ms 99236 KB Output is correct
24 Correct 160 ms 113980 KB Output is correct
25 Correct 490 ms 204740 KB Output is correct
26 Correct 975 ms 277680 KB Output is correct
27 Correct 1068 ms 233528 KB Output is correct
28 Correct 1211 ms 220980 KB Output is correct
29 Correct 1178 ms 218596 KB Output is correct
30 Correct 1160 ms 221448 KB Output is correct
31 Correct 1096 ms 152568 KB Output is correct
32 Correct 1205 ms 227332 KB Output is correct