oj.uz

Submission #534894

# Submission time Handle Problem Language Result Execution time Memory
534894 2022-03-09T05:59:24 Z aadit_ambadkar Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 533 ms 143000 KB 
/*
    This code belongs to Aadit Ambadkar
    Date: 2022-03-07 21:34:47
    Problem: tis
*/
#include <bits/stdc++.h>
using namespace::std;
 
typedef long long ll;
#define F0R(i, n) for (int i = 0; i < n; i++)
#define R0F(i, n) for (int i = n-1; i >= 0; i--)
#define FOR(i, a, n) for (int i = a; i < n; i++)
#define pb push_back
#define fastio ios::sync_with_stdio(0); cin.tie(0)
#define MOD 1000000007
#define FF first
#define SS second
 
int n, m;
int board[4005][4005];
bool vis[4005][4005];
 
int main() {
    fastio;
    cin >> n >> m;
    F0R(i, n) {
        string s;
        cin >> s;
        F0R(j, m) {
            if (s[j]=='F') board[i][j]=1;
            else if (s[j]=='R') board[i][j]=2;
            else board[i][j]=0;
            vis[i][j]=false;
        }
    }
    // F0R(i, n) {
    //     F0R(j, m) {
    //         cout << board[i][j] << " ";
    //     }
    //     cout << "\n";
    // }
    // cout << "\n";
    deque<pair<int, pair<int, int>>> pq;
    pq.push_front({1, {0, 0}});
    vis[0][0]=true;
    int ans = 0;
    while (!pq.empty()) {
        auto p = pq.front(); pq.pop_front();
        int g = p.FF, u = p.SS.FF, v = p.SS.SS;
        // if (vis[u][v]) continue;
        // cout << u << " " << v << " " << g << "\n";
        ans = max(ans, g);
        vis[u][v]=true;
        if (u < n-1 && !vis[u+1][v] && board[u+1][v]!=0) {
            vis[u+1][v]=true;
            if (board[u][v]==board[u+1][v]) pq.push_front({g, {u+1, v}});
            else pq.push_back({g+1, {u+1, v}});
        }
        if (v < m-1 && !vis[u][v+1] && board[u][v+1]!=0) {
            vis[u][v+1]=true;
            if (board[u][v]==board[u][v+1]) pq.push_front({g, {u, v+1}});
            else pq.push_back({g+1, {u, v+1}});
        }
        if (u > 0 && !vis[u-1][v] && board[u-1][v]!=0) {
            vis[u-1][v]=true;
            if (board[u][v]==board[u-1][v]) pq.push_front({g, {u-1, v}});
            else pq.push_back({g+1, {u-1, v}});
        }
        if (v > 0 && !vis[u][v-1] && board[u][v-1]!=0) {
            vis[u][v-1]=true;
            if (board[u][v]==board[u][v-1]) pq.push_front({g, {u, v-1}});
            else pq.push_back({g+1, {u, v-1}});
        }
    }
    cout << ans;
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 5196 KB Output is correct
2 Correct 0 ms 460 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 7 ms 5168 KB Output is correct
5 Correct 3 ms 2892 KB Output is correct
6 Correct 0 ms 460 KB Output is correct
7 Correct 1 ms 716 KB Output is correct
8 Correct 1 ms 716 KB Output is correct
9 Correct 1 ms 1100 KB Output is correct
10 Correct 3 ms 2508 KB Output is correct
11 Correct 2 ms 2124 KB Output is correct
12 Correct 4 ms 2892 KB Output is correct
13 Correct 2 ms 2892 KB Output is correct
14 Correct 2 ms 2892 KB Output is correct
15 Correct 10 ms 5312 KB Output is correct
16 Correct 10 ms 5196 KB Output is correct
17 Correct 8 ms 5068 KB Output is correct
18 Correct 7 ms 5068 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 30856 KB Output is correct
2 Correct 38 ms 16408 KB Output is correct
3 Correct 184 ms 78772 KB Output is correct
4 Correct 54 ms 29880 KB Output is correct
5 Correct 147 ms 59128 KB Output is correct
6 Correct 513 ms 99612 KB Output is correct
7 Correct 17 ms 32204 KB Output is correct
8 Correct 14 ms 30796 KB Output is correct
9 Correct 2 ms 588 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 20 ms 31632 KB Output is correct
12 Correct 1 ms 1484 KB Output is correct
13 Correct 39 ms 16332 KB Output is correct
14 Correct 23 ms 11136 KB Output is correct
15 Correct 20 ms 12228 KB Output is correct
16 Correct 17 ms 6028 KB Output is correct
17 Correct 92 ms 32216 KB Output is correct
18 Correct 74 ms 31796 KB Output is correct
19 Correct 56 ms 29980 KB Output is correct
20 Correct 47 ms 27716 KB Output is correct
21 Correct 127 ms 61072 KB Output is correct
22 Correct 139 ms 59192 KB Output is correct
23 Correct 170 ms 49380 KB Output is correct
24 Correct 129 ms 60584 KB Output is correct
25 Correct 394 ms 78656 KB Output is correct
26 Correct 307 ms 143000 KB Output is correct
27 Correct 461 ms 129936 KB Output is correct
28 Correct 508 ms 99492 KB Output is correct
29 Correct 533 ms 95920 KB Output is correct
30 Correct 482 ms 105412 KB Output is correct
31 Correct 389 ms 63712 KB Output is correct
32 Correct 399 ms 114624 KB Output is correct