oj.uz

Submission #283152

# Submission time Handle Problem Language Result Execution time Memory
283152 2020-08-25T10:39:26 Z Atill83 Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 1084 ms 235000 KB 
#include <bits/stdc++.h>
#define ff first
#define ss second
#define endl '\n'
using namespace std;
const long long INF = (long long) 1e18;
const int mod = (int) 1e9+7;
const int MAXN = (int) 4e3+5;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
int h, w;
char g[MAXN][MAXN];
int dx[] = {-1, 0, 0, 1};
int dy[] = {0, -1, 1, 0};
bool vis[MAXN][MAXN];
queue<pii> rab, fox;
bool ic(int x, int y){
    return (x >= 0 && x < h && y >= 0 && y < w);
}


int rb();

int fx(){
    if(fox.empty()) return 0;
    while(!fox.empty()){
        pii cur = fox.front();
        fox.pop();
        for(int j = 0; j < 4; j++){
            int nx = cur.ff + dx[j], ny = cur.ss + dy[j];
            if(!ic(nx, ny)) continue;
            if(g[nx][ny] == 'R' && vis[nx][ny] == 0){
                vis[nx][ny] = 1;
                rab.push({nx, ny});
            }else if(g[nx][ny] == 'F' && vis[nx][ny] == 0){
                vis[nx][ny] = 1;
                fox.push({nx, ny});
            }
        }
    }
    return 1 + rb();
}

int rb(){
    if(rab.empty()) return 0;
    while(!rab.empty()){
        pii cur = rab.front();
        rab.pop();
        for(int j = 0; j < 4; j++){
            int nx = cur.ff + dx[j], ny = cur.ss + dy[j];
            if(!ic(nx, ny)) continue;
            if(g[nx][ny] == 'F' && vis[nx][ny] == 0){
                vis[nx][ny] = 1;
                fox.push({nx, ny});
            }else if(g[nx][ny] == 'R'&& vis[nx][ny] == 0){
                vis[nx][ny] = 1;
                rab.push({nx, ny});
            }
        }
    }
    return 1 + fx();
}



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

    #ifdef Local
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/int.txt","r",stdin);
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/out.txt","w",stdout);
    #endif

    cin>>h>>w;

    for(int i = 0; i < h; i++) cin>>g[i];
    assert(g[0][0] == g[h - 1][w - 1]);
    
    vis[0][0] = 1;
    if(g[0][0] == 'F'){
        fox.push({0, 0});
        cout<<fx()<<endl;
    }else{
        rab.push({0, 0});
        cout<<rb()<<endl;
    }


    #ifdef Local
        cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 4224 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 768 KB Output is correct
4 Correct 9 ms 4352 KB Output is correct
5 Correct 3 ms 2560 KB Output is correct
6 Correct 0 ms 512 KB Output is correct
7 Correct 1 ms 768 KB Output is correct
8 Correct 1 ms 768 KB Output is correct
9 Correct 1 ms 1152 KB Output is correct
10 Correct 3 ms 2304 KB Output is correct
11 Correct 3 ms 1920 KB Output is correct
12 Correct 7 ms 2688 KB Output is correct
13 Correct 4 ms 2560 KB Output is correct
14 Correct 3 ms 2560 KB Output is correct
15 Correct 14 ms 4224 KB Output is correct
16 Correct 17 ms 4224 KB Output is correct
17 Correct 11 ms 4096 KB Output is correct
18 Correct 9 ms 4352 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 30464 KB Output is correct
2 Correct 51 ms 10232 KB Output is correct
3 Correct 250 ms 59452 KB Output is correct
4 Correct 66 ms 15104 KB Output is correct
5 Correct 320 ms 234872 KB Output is correct
6 Correct 1084 ms 42040 KB Output is correct
7 Correct 22 ms 31872 KB Output is correct
8 Correct 21 ms 30464 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 21 ms 31232 KB Output is correct
12 Correct 2 ms 2048 KB Output is correct
13 Correct 62 ms 10232 KB Output is correct
14 Correct 32 ms 7552 KB Output is correct
15 Correct 33 ms 14840 KB Output is correct
16 Correct 25 ms 3584 KB Output is correct
17 Correct 137 ms 16476 KB Output is correct
18 Correct 108 ms 41848 KB Output is correct
19 Correct 63 ms 15104 KB Output is correct
20 Correct 62 ms 19704 KB Output is correct
21 Correct 144 ms 40148 KB Output is correct
22 Correct 317 ms 235000 KB Output is correct
23 Correct 274 ms 20168 KB Output is correct
24 Correct 173 ms 95096 KB Output is correct
25 Correct 468 ms 138724 KB Output is correct
26 Correct 534 ms 27896 KB Output is correct
27 Correct 784 ms 33400 KB Output is correct
28 Correct 1042 ms 42012 KB Output is correct
29 Correct 1022 ms 40328 KB Output is correct
30 Correct 1042 ms 38792 KB Output is correct
31 Correct 862 ms 25908 KB Output is correct
32 Correct 685 ms 32604 KB Output is correct