oj.uz

Submission #880557

# Submission time Handle Problem Language Result Execution time Memory
880557 2023-11-29T16:17:17 Z JakobZorz Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 781 ms 44496 KB 
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
#include<limits.h>
#include<math.h>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<iomanip>
#include<cstring>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using namespace std;
//const int MOD=1e9+7;
//typedef pair<ll,ll>Point;
//typedef pair<ll,ll>Line;
//#define x first
//#define y second

queue<pair<int,int>>fq,rq;
bool vis[4000][4000];
string arr[4000];
int w,h;

void t(int x,int y){
    if(x<0||x>=w||y<0||y>=h)
        return;
    if(vis[x][y])
        return;
    vis[x][y]=true;
    if(arr[y][x]=='F')
        fq.push({x,y});
    if(arr[y][x]=='R')
        rq.push({x,y});
}

void solve(){
    cin>>h>>w;
    for(int i=0;i<h;i++)
        cin>>arr[i];
    
    bool is_f=arr[0][0]=='F';
    vis[0][0]=true;
    if(is_f)
        fq.push({0,0});
    else
        rq.push({0,0});
    
    int res=0;
    while(true){
        if(is_f){
            if(fq.empty())
                break;
            
            while(!fq.empty()){
                auto curr=fq.front();
                fq.pop();
                t(curr.first-1,curr.second);
                t(curr.first+1,curr.second);
                t(curr.first,curr.second-1);
                t(curr.first,curr.second+1);
            }
            
        }else{
            if(rq.empty())
                break;
            
            while(!rq.empty()){
                auto curr=rq.front();
                rq.pop();
                t(curr.first-1,curr.second);
                t(curr.first+1,curr.second);
                t(curr.first,curr.second-1);
                t(curr.first,curr.second+1);
            }
        }
        is_f=!is_f;
        res++;
    }
    cout<<res<<"\n";
}

int main(){
    ios::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL);
    //freopen("bank.in","r",stdin);freopen("bank.out","w",stdout);
    int t=1;//cin>>t;
    while(t--)solve();
    return 0;
}

/*
 
5 8
FFR.....
.FRRR...
.FFFFF..
..RRRFFR
.....FFF
 
 */

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 2648 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 5 ms 1884 KB Output is correct
5 Correct 2 ms 1628 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 2 ms 1628 KB Output is correct
11 Correct 2 ms 1456 KB Output is correct
12 Correct 5 ms 1884 KB Output is correct
13 Correct 2 ms 1784 KB Output is correct
14 Correct 2 ms 1628 KB Output is correct
15 Correct 9 ms 2652 KB Output is correct
16 Correct 10 ms 2652 KB Output is correct
17 Correct 7 ms 2776 KB Output is correct
18 Correct 5 ms 1880 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 36 ms 7020 KB Output is correct
3 Correct 190 ms 33716 KB Output is correct
4 Correct 57 ms 12120 KB Output is correct
5 Correct 138 ms 22044 KB Output is correct
6 Correct 774 ms 44496 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 7 ms 15708 KB Output is correct
10 Correct 7 ms 16216 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 1116 KB Output is correct
13 Correct 41 ms 7120 KB Output is correct
14 Correct 24 ms 5212 KB Output is correct
15 Correct 16 ms 5724 KB Output is correct
16 Correct 18 ms 7516 KB Output is correct
17 Correct 95 ms 12636 KB Output is correct
18 Correct 46 ms 12636 KB Output is correct
19 Correct 48 ms 12312 KB Output is correct
20 Correct 42 ms 11864 KB Output is correct
21 Correct 109 ms 22384 KB Output is correct
22 Correct 125 ms 21852 KB Output is correct
23 Correct 220 ms 20976 KB Output is correct
24 Correct 105 ms 21764 KB Output is correct
25 Correct 224 ms 33892 KB Output is correct
26 Correct 401 ms 27472 KB Output is correct
27 Correct 561 ms 35600 KB Output is correct
28 Correct 713 ms 44416 KB Output is correct
29 Correct 781 ms 42772 KB Output is correct
30 Correct 611 ms 41184 KB Output is correct
31 Correct 531 ms 24636 KB Output is correct
32 Correct 462 ms 34640 KB Output is correct