oj.uz

Submission #817807

# Submission time Handle Problem Language Result Execution time Memory
817807 2023-08-09T16:40:44 Z Boomyday Tracks in the Snow (BOI13_tracks) C++17
75.3125 / 100
 801 ms 162520 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<H)) 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];
                ans = max(ans, dist[nx][ny]);
            }
            else if (grid[nx][ny]==-grid[x][y]){
                q.push_back({nx,ny});
                dist[nx][ny] = dist[x][y]+1;
                ans = max(ans, dist[nx][ny]);
            }
        }
    }
    cout << ans << endl;


}

Subtask #1
25.0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 2464 KB Output isn't correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 7 ms 1748 KB Output is correct
5 Correct 3 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 Incorrect 1 ms 340 KB Output isn't correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 3 ms 852 KB Output is correct
11 Correct 2 ms 596 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 2384 KB Output is correct
16 Incorrect 15 ms 2332 KB Output isn't correct
17 Correct 10 ms 2260 KB Output is correct
18 Correct 7 ms 1748 KB Output is correct

Subtask #2
50.3125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1236 KB Output is correct
2 Correct 56 ms 12872 KB Output is correct
3 Correct 407 ms 128028 KB Output is correct
4 Incorrect 110 ms 30292 KB Output isn't correct
5 Correct 269 ms 72132 KB Output is correct
6 Correct 794 ms 141988 KB Output is correct
7 Correct 3 ms 1236 KB Output is correct
8 Correct 4 ms 1236 KB Output is correct
9 Incorrect 2 ms 724 KB Output isn't correct
10 Incorrect 1 ms 596 KB Output isn't correct
11 Correct 3 ms 1204 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 60 ms 12876 KB Output is correct
14 Incorrect 32 ms 7496 KB Output isn't correct
15 Correct 29 ms 8364 KB Output is correct
16 Incorrect 13 ms 5332 KB Output isn't correct
17 Correct 155 ms 32704 KB Output is correct
18 Correct 122 ms 32368 KB Output is correct
19 Incorrect 109 ms 30372 KB Output isn't correct
20 Incorrect 64 ms 27744 KB Output isn't correct
21 Correct 257 ms 74724 KB Output is correct
22 Correct 268 ms 72320 KB Output is correct
23 Incorrect 267 ms 62072 KB Output isn't correct
24 Correct 236 ms 72908 KB Output is correct
25 Correct 728 ms 128032 KB Output is correct
26 Correct 458 ms 148340 KB Output is correct
27 Correct 617 ms 162520 KB Output is correct
28 Correct 801 ms 142024 KB Output is correct
29 Correct 747 ms 139576 KB Output is correct
30 Correct 707 ms 144312 KB Output is correct
31 Incorrect 628 ms 82620 KB Output isn't correct
32 Correct 581 ms 152244 KB Output is correct