oj.uz

답안 #817795

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
817795 2023-08-09T16:28:02 Z Boomyday Tracks in the Snow (BOI13_tracks) C++17
75.3125 / 100
 755 ms 172872 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.empty()){
        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];
            }
            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
25.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 13 ms 2516 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 1872 KB Output is correct
5 Correct 5 ms 980 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 300 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 796 KB Output is correct
11 Correct 2 ms 724 KB Output is correct
12 Correct 5 ms 1108 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 2632 KB Output is correct
16 Incorrect 14 ms 2516 KB Output isn't correct
17 Correct 11 ms 2500 KB Output is correct
18 Correct 8 ms 1852 KB Output is correct

Subtask #2
50.3125 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1236 KB Output is correct
2 Correct 56 ms 14296 KB Output is correct
3 Correct 482 ms 138312 KB Output is correct
4 Incorrect 108 ms 33936 KB Output isn't correct
5 Correct 256 ms 81020 KB Output is correct
6 Correct 729 ms 152336 KB Output is correct
7 Correct 3 ms 1236 KB Output is correct
8 Correct 3 ms 1236 KB Output is correct
9 Incorrect 2 ms 852 KB Output isn't correct
10 Incorrect 1 ms 596 KB Output isn't correct
11 Correct 3 ms 1212 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 56 ms 14352 KB Output is correct
14 Incorrect 33 ms 8412 KB Output isn't correct
15 Correct 30 ms 9336 KB Output is correct
16 Incorrect 14 ms 5972 KB Output isn't correct
17 Correct 144 ms 36768 KB Output is correct
18 Correct 126 ms 36284 KB Output is correct
19 Incorrect 107 ms 33944 KB Output isn't correct
20 Incorrect 67 ms 31224 KB Output isn't correct
21 Correct 249 ms 83760 KB Output is correct
22 Correct 252 ms 81020 KB Output is correct
23 Incorrect 243 ms 69832 KB Output isn't correct
24 Correct 247 ms 81844 KB Output is correct
25 Correct 659 ms 138320 KB Output is correct
26 Correct 421 ms 158624 KB Output is correct
27 Correct 606 ms 172872 KB Output is correct
28 Correct 755 ms 152432 KB Output is correct
29 Correct 725 ms 149888 KB Output is correct
30 Correct 648 ms 154708 KB Output is correct
31 Incorrect 592 ms 92596 KB Output isn't correct
32 Correct 573 ms 162560 KB Output is correct