oj.uz

Submission #812533

# Submission time Handle Problem Language Result Execution time Memory
812533 2023-08-07T09:07:16 Z andecaandeci Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 1441 ms 888112 KB 
#include <bits/stdc++.h>
#define int long long
#define SETIO cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false);
#define REP(i,a,b)for(int i=a;i<b;i++)
#define fi first
#define se second
#define pb push_back
#define FORI(v)for(auto i:v)
#define FORJ(v)for(auto j:v)
using namespace std;
using pii=pair<int, int>;

int color[5000][5000];
bool visited[5000][5000];
int w, h;

int bfs(){
    deque<pair<pii, int>> q;
    q.pb({{0,0},1});
    int ans=1;
    while(q.size()){
        auto qt = q.front();q.pop_front();
        auto top = qt.fi;
        if(top.fi<0)continue;
        if(top.fi>=h)continue;
        if(top.se<0)continue;
        if(top.se>=w)continue;
        if(visited[top.fi][top.se])continue;
        visited[top.fi][top.se]=true;
        int cur=color[top.fi][top.se];
        if(cur==0)continue;
        #define PUSH(x, y) if(cur!=color[x][y])q.pb({{x,y},qt.se+1});else q.push_front({{x,y},qt.se});
        PUSH(top.fi+1,top.se);
        PUSH(top.fi-1,top.se);
        PUSH(top.fi,top.se+1);
        PUSH(top.fi,top.se-1);
        ans=max(ans,qt.se);
    }
    return ans;
}

#undef int
int main() {
#define int long long
    SETIO;
    cin>>h>>w;
    REP(i,0,h){
        REP(j,0,w){
            char c;cin>>c;
            if(c=='.')color[i][j]=0;
            if(c=='R')color[i][j]=1;
            if(c=='F')color[i][j]=2;
        }
    }
    memset(visited,0,sizeof visited);
    cout<<bfs()<<endl;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 29520 KB Output is correct
2 Correct 11 ms 24788 KB Output is correct
3 Correct 10 ms 24928 KB Output is correct
4 Correct 27 ms 29500 KB Output is correct
5 Correct 16 ms 26620 KB Output is correct
6 Correct 10 ms 24796 KB Output is correct
7 Correct 12 ms 24916 KB Output is correct
8 Correct 11 ms 25040 KB Output is correct
9 Correct 11 ms 25300 KB Output is correct
10 Correct 16 ms 26324 KB Output is correct
11 Correct 17 ms 26324 KB Output is correct
12 Correct 18 ms 27004 KB Output is correct
13 Correct 13 ms 26708 KB Output is correct
14 Correct 13 ms 26708 KB Output is correct
15 Correct 27 ms 29316 KB Output is correct
16 Correct 31 ms 29476 KB Output is correct
17 Correct 27 ms 28988 KB Output is correct
18 Correct 22 ms 29396 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 41060 KB Output is correct
2 Correct 85 ms 43232 KB Output is correct
3 Correct 481 ms 168852 KB Output is correct
4 Correct 150 ms 62936 KB Output is correct
5 Correct 327 ms 109776 KB Output is correct
6 Correct 1437 ms 283032 KB Output is correct
7 Correct 24 ms 41556 KB Output is correct
8 Correct 20 ms 41044 KB Output is correct
9 Correct 13 ms 25680 KB Output is correct
10 Correct 11 ms 25300 KB Output is correct
11 Correct 18 ms 41172 KB Output is correct
12 Correct 14 ms 25556 KB Output is correct
13 Correct 85 ms 43316 KB Output is correct
14 Correct 53 ms 36608 KB Output is correct
15 Correct 49 ms 37628 KB Output is correct
16 Correct 44 ms 32244 KB Output is correct
17 Correct 221 ms 66096 KB Output is correct
18 Correct 170 ms 65388 KB Output is correct
19 Correct 131 ms 63020 KB Output is correct
20 Correct 115 ms 60004 KB Output is correct
21 Correct 346 ms 112596 KB Output is correct
22 Correct 362 ms 109756 KB Output is correct
23 Correct 386 ms 97956 KB Output is correct
24 Correct 315 ms 111056 KB Output is correct
25 Correct 735 ms 168652 KB Output is correct
26 Correct 1046 ms 888112 KB Output is correct
27 Correct 1309 ms 459712 KB Output is correct
28 Correct 1441 ms 282924 KB Output is correct
29 Correct 1392 ms 274172 KB Output is correct
30 Correct 1313 ms 345724 KB Output is correct
31 Correct 1006 ms 125012 KB Output is correct
32 Correct 1259 ms 368628 KB Output is correct