oj.uz

Submission #1019201

# Submission time Handle Problem Language Result Execution time Memory
1019201 2024-07-10T15:17:21 Z Luvidi Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 655 ms 158784 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define fs first
#define sc second
#define pb push_back

void solve() {
    int n,m;
    cin>>n>>m;
    int a[n][m];
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            char c;
            cin>>c;
            if(c=='F')a[i][j]=0;
            else if(c=='R')a[i][j]=1;
            else a[i][j]=-1;
        }
    }
    int dist[n][m],dx[4]={-1,1,0,0},dy[4]={0,0,-1,1},ans=0;
    memset(dist,-1,sizeof(dist));
    deque<pii> dq;
    dist[0][0]=0;
    dq.push_back({0,0});
    while(!dq.empty()){
        auto[r,c]=dq.front();
        dq.pop_front();
        for(int i=0;i<4;i++){
            int r2=r+dx[i],c2=c+dy[i];
            if(r2>=0&&c2>=0&&r2<n&&c2<m){
                if(a[r2][c2]==-1||dist[r2][c2]!=-1)continue; 
                if(a[r2][c2]==a[r][c]){
                    dist[r2][c2]=dist[r][c];
                    dq.push_front({r2,c2});
                }else{
                    dist[r2][c2]=dist[r][c]+1;
                    ans=max(ans,dist[r2][c2]);
                    dq.push_back({r2,c2});
                }
            }
        }
        a[r][c]=-1;
    }
    cout<<ans+1;
}

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

    solve();
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2396 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 6 ms 1884 KB Output is correct
5 Correct 3 ms 1116 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 2 ms 860 KB Output is correct
11 Correct 2 ms 860 KB Output is correct
12 Correct 5 ms 1116 KB Output is correct
13 Correct 2 ms 1116 KB Output is correct
14 Correct 2 ms 1368 KB Output is correct
15 Correct 10 ms 2684 KB Output is correct
16 Correct 12 ms 2636 KB Output is correct
17 Correct 9 ms 2396 KB Output is correct
18 Correct 6 ms 2000 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 700 KB Output is correct
2 Correct 45 ms 14228 KB Output is correct
3 Correct 309 ms 141072 KB Output is correct
4 Correct 84 ms 33360 KB Output is correct
5 Correct 174 ms 79668 KB Output is correct
6 Correct 655 ms 154348 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 2 ms 996 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 860 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 45 ms 14172 KB Output is correct
14 Correct 24 ms 8272 KB Output is correct
15 Correct 23 ms 9052 KB Output is correct
16 Correct 20 ms 5980 KB Output is correct
17 Correct 142 ms 36108 KB Output is correct
18 Correct 86 ms 35408 KB Output is correct
19 Correct 85 ms 33364 KB Output is correct
20 Correct 66 ms 30528 KB Output is correct
21 Correct 203 ms 82256 KB Output is correct
22 Correct 174 ms 79548 KB Output is correct
23 Correct 222 ms 68432 KB Output is correct
24 Correct 182 ms 80464 KB Output is correct
25 Correct 428 ms 141296 KB Output is correct
26 Correct 287 ms 158340 KB Output is correct
27 Correct 394 ms 158784 KB Output is correct
28 Correct 632 ms 154328 KB Output is correct
29 Correct 585 ms 154704 KB Output is correct
30 Correct 528 ms 152796 KB Output is correct
31 Correct 517 ms 91084 KB Output is correct
32 Correct 375 ms 156644 KB Output is correct