oj.uz

Submission #862324

# Submission time Handle Problem Language Result Execution time Memory
862324 2023-10-18T04:03:48 Z 8pete8 Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 1090 ms 222024 KB 
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include<bitset> 
#include<stack>
using namespace std;
#define ll long long
#define f first
//#define endl "\n"
#define s second
#define pii pair<int,int>
#define pppiii pair<pii,pii>
#define ppii pair<pii,pii>
#define all(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
const int mxn=5e5+10,mx=5e6+10,minf=-1e9;
bool vis[4004][4004];
int u[4]={0,0,1,-1};
int r[4]={1,-1,0,0},n,m;
int grid[4004][4004];
int32_t main(){
    fastio
    deque<ppii>dq;
    cin>>n>>m;
    for(int i=0;i<n;i++)for(int j=0;j<m;j++){
        char a;cin>>a;
        if(a=='.')grid[i][j]=-1;
        else if(a=='F')grid[i][j]=1;
    }
    int ans=0;
    dq.push_front({{grid[0][0],1},{0,0}});//
    while(!dq.empty()){
        int cc=dq.front().f.f,c=dq.front().f.s,cx=dq.front().s.f,cy=dq.front().s.s;
        ans=max(ans,c);
        dq.pop_front();
        vis[cx][cy]=true;
        for(int i=0;i<4;i++){
            int nx=cx+u[i],ny=cy+r[i];
            if(nx<0||nx>=n||ny<0||ny>=m)continue;
            if(vis[nx][ny])continue;
            if(grid[nx][ny]==-1)continue;
            if(grid[nx][ny]!=cc)dq.push_back({{1-cc,c+1},{nx,ny}});
            else dq.push_front({{cc,c},{nx,ny}});
        }
    }
    cout<<ans<<'\n';
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 12124 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 11 ms 12732 KB Output is correct
5 Correct 4 ms 8912 KB Output is correct
6 Correct 1 ms 4440 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 3 ms 6748 KB Output is correct
11 Correct 3 ms 6748 KB Output is correct
12 Correct 8 ms 9096 KB Output is correct
13 Correct 3 ms 8796 KB Output is correct
14 Correct 4 ms 8796 KB Output is correct
15 Correct 17 ms 12000 KB Output is correct
16 Correct 21 ms 12376 KB Output is correct
17 Correct 13 ms 11944 KB Output is correct
18 Correct 11 ms 12636 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 77980 KB Output is correct
2 Correct 60 ms 28316 KB Output is correct
3 Correct 334 ms 87188 KB Output is correct
4 Correct 81 ms 42324 KB Output is correct
5 Correct 145 ms 65360 KB Output is correct
6 Correct 1090 ms 150932 KB Output is correct
7 Correct 13 ms 78680 KB Output is correct
8 Correct 13 ms 77916 KB Output is correct
9 Correct 3 ms 4700 KB Output is correct
10 Correct 1 ms 2904 KB Output is correct
11 Correct 13 ms 78424 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 59 ms 28248 KB Output is correct
14 Correct 37 ms 20176 KB Output is correct
15 Correct 25 ms 22352 KB Output is correct
16 Correct 32 ms 9788 KB Output is correct
17 Correct 144 ms 44836 KB Output is correct
18 Correct 91 ms 44560 KB Output is correct
19 Correct 86 ms 42452 KB Output is correct
20 Correct 80 ms 39280 KB Output is correct
21 Correct 196 ms 67852 KB Output is correct
22 Correct 147 ms 65780 KB Output is correct
23 Correct 276 ms 56860 KB Output is correct
24 Correct 174 ms 67864 KB Output is correct
25 Correct 444 ms 87120 KB Output is correct
26 Correct 801 ms 222024 KB Output is correct
27 Correct 943 ms 180080 KB Output is correct
28 Correct 1089 ms 155172 KB Output is correct
29 Correct 1059 ms 151032 KB Output is correct
30 Correct 1000 ms 165088 KB Output is correct
31 Correct 790 ms 76116 KB Output is correct
32 Correct 840 ms 171468 KB Output is correct