oj.uz

Submission #817808

# Submission time Handle Problem Language Result Execution time Memory
817808 2023-08-09T16:42:01 Z Boomyday Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 770 ms 162588 KB 
//
// Created by adavy on 1/31/2023.
//
// My Header
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using db = double;
using str = string; // yay python!

using ii = pair<int,int>;
using pl = pair<ll,ll>;
using pd = pair<db,db>;

using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>;
using vs = vector<str>;
using vii = vector<ii>;
using vpl = vector<pl>;
using vpd = vector<pd>;

#define tcT template<class T
#define tcTU tcT, class U

tcT> using V = vector<T>;
tcT, size_t SZ> using AR = array<T,SZ>;
tcT> using PR = pair<T,T>;

// pairs
#define mp make_pair
#define f first
#define s second



#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

#define len(x) int((x).size())
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define sor(x) sort(all(x))
#define rsz resize
#define ins insert
#define ft front()
#define bk back()
#define pb push_back
#define eb emplace_back
#define pf push_front

const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5;
const ll INF = 1e18; // not too close to LLONG_MAX
const ld PI = acos((ld)-1);
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1}; // for every grid problem!!


int main(){
    // 0-1 bfs

    int H, W; cin >> H >> W;


    vector<vi> grid;

    F0R(i, H){
        string row; cin >> row;
        vector<int> x;
        trav(c, row){
            if (c=='R') x.pb(1);
            else if (c=='F') x.pb(-1);
            else x.pb(0);
        }
        grid.pb(x);
    }

    vector<vector<bool>> vis(H,vb(W,0));
    vector<vector<int>> dist(H,vi(W));

    deque<ii> q;
    q.push_back({0,0});
    dist[0][0] = 1; // H, W
    vis[0][0] = 1;
    int ans = 1;

    while(q.size()){
        auto [x, y] = q.front(); q.pop_front();

        ans = max(ans, dist[x][y]);
        F0R(d, 4){
            int nx = x+dx[d], ny = y+dy[d];
            if(!(0<=nx && nx<H && 0<=ny && ny<W)) continue;
            if (vis[nx][ny]) continue;
            if (grid[nx][ny]==0) continue;
            vis[nx][ny] = 1;
            if (grid[nx][ny]==grid[x][y]){
                q.push_front({nx,ny});
                dist[nx][ny] = dist[x][y];
                
            }
            else if (grid[nx][ny]==-grid[x][y]){
                q.push_back({nx,ny});
                dist[nx][ny] = dist[x][y]+1;
            }
        }
    }
    cout << ans << endl;


}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 2260 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 7 ms 1712 KB Output is correct
5 Correct 4 ms 980 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 3 ms 852 KB Output is correct
11 Correct 2 ms 720 KB Output is correct
12 Correct 5 ms 980 KB Output is correct
13 Correct 3 ms 980 KB Output is correct
14 Correct 3 ms 980 KB Output is correct
15 Correct 12 ms 2380 KB Output is correct
16 Correct 14 ms 2336 KB Output is correct
17 Correct 10 ms 2260 KB Output is correct
18 Correct 7 ms 1724 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1236 KB Output is correct
2 Correct 55 ms 12872 KB Output is correct
3 Correct 401 ms 128032 KB Output is correct
4 Correct 106 ms 30380 KB Output is correct
5 Correct 249 ms 72104 KB Output is correct
6 Correct 770 ms 142028 KB Output is correct
7 Correct 3 ms 1236 KB Output is correct
8 Correct 3 ms 1236 KB Output is correct
9 Correct 3 ms 724 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 3 ms 1236 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 55 ms 12884 KB Output is correct
14 Correct 31 ms 7580 KB Output is correct
15 Correct 29 ms 8276 KB Output is correct
16 Correct 26 ms 5460 KB Output is correct
17 Correct 142 ms 32696 KB Output is correct
18 Correct 132 ms 32364 KB Output is correct
19 Correct 121 ms 30340 KB Output is correct
20 Correct 91 ms 27748 KB Output is correct
21 Correct 233 ms 74748 KB Output is correct
22 Correct 312 ms 72268 KB Output is correct
23 Correct 292 ms 62080 KB Output is correct
24 Correct 340 ms 72956 KB Output is correct
25 Correct 656 ms 128036 KB Output is correct
26 Correct 472 ms 148336 KB Output is correct
27 Correct 600 ms 162588 KB Output is correct
28 Correct 714 ms 142028 KB Output is correct
29 Correct 725 ms 139580 KB Output is correct
30 Correct 641 ms 144500 KB Output is correct
31 Correct 561 ms 82624 KB Output is correct
32 Correct 544 ms 152240 KB Output is correct