oj.uz

Submission #880548

# Submission time Handle Problem Language Result Execution time Memory
880548 2023-11-29T16:06:59 Z JakobZorz Tracks in the Snow (BOI13_tracks) C++14
56.6667 / 100
 748 ms 91728 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];
vector<string>arr;
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[x][y]=='F')
        fq.push({x,y});
    if(arr[x][y]=='R')
        rq.push({x,y});
}

void solve(){
    cin>>h>>w;
    arr=vector<string>(h);
    for(string&i:arr)
        cin>>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
21.6666666667 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 5208 KB Execution killed with signal 11
2 Correct 0 ms 476 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 4 ms 2140 KB Output is correct
5 Correct 2 ms 1628 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Runtime error 1 ms 1116 KB Execution killed with signal 11
9 Correct 1 ms 860 KB Output is correct
10 Correct 2 ms 1368 KB Output is correct
11 Correct 2 ms 1372 KB Output is correct
12 Runtime error 4 ms 3036 KB Execution killed with signal 11
13 Correct 2 ms 1628 KB Output is correct
14 Correct 2 ms 1696 KB Output is correct
15 Correct 8 ms 2908 KB Output is correct
16 Runtime error 4 ms 5196 KB Execution killed with signal 11
17 Runtime error 7 ms 5120 KB Execution killed with signal 11
18 Correct 4 ms 2136 KB Output is correct

Subtask #2
35.0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 604 KB Output isn't correct
2 Correct 33 ms 8560 KB Output is correct
3 Correct 156 ms 47960 KB Output is correct
4 Runtime error 39 ms 27220 KB Execution killed with signal 11
5 Correct 115 ms 30036 KB Output is correct
6 Correct 748 ms 58060 KB Output is correct
7 Incorrect 1 ms 604 KB Output isn't correct
8 Incorrect 1 ms 804 KB Output isn't correct
9 Incorrect 0 ms 604 KB Output isn't correct
10 Incorrect 0 ms 348 KB Output isn't correct
11 Incorrect 1 ms 604 KB Output isn't correct
12 Correct 1 ms 1100 KB Output is correct
13 Correct 33 ms 8560 KB Output is correct
14 Runtime error 22 ms 10588 KB Execution killed with signal 11
15 Correct 12 ms 6236 KB Output is correct
16 Incorrect 2 ms 2140 KB Output isn't correct
17 Correct 97 ms 16532 KB Output is correct
18 Correct 49 ms 16212 KB Output is correct
19 Runtime error 39 ms 27220 KB Execution killed with signal 11
20 Incorrect 6 ms 7592 KB Output isn't correct
21 Incorrect 94 ms 30672 KB Output isn't correct
22 Correct 121 ms 30040 KB Output is correct
23 Incorrect 144 ms 23896 KB Output isn't correct
24 Incorrect 98 ms 29856 KB Output isn't correct
25 Correct 266 ms 47952 KB Output is correct
26 Correct 388 ms 38736 KB Output is correct
27 Correct 520 ms 49660 KB Output is correct
28 Correct 702 ms 57924 KB Output is correct
29 Correct 710 ms 56636 KB Output is correct
30 Runtime error 162 ms 91728 KB Execution killed with signal 11
31 Runtime error 42 ms 57936 KB Execution killed with signal 11
32 Correct 488 ms 49064 KB Output is correct