oj.uz

Submission #877710

# Submission time Handle Problem Language Result Execution time Memory
877710 2023-11-23T13:05:42 Z asli_bg Tracks in the Snow (BOI13_tracks) C++11
0 / 100
 2000 ms 1048576 KB 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define MOD 1000000007
 
const int MAXN=4e3+1;
 
//bool vis[MAXN][MAXN];
 
int grid[MAXN][MAXN];
 
int h,w;
 
int xyon[4]={1,0,-1,0};
int yyon[4]={0,-1,0,1};
 

bool isvalid(int x,int y){
    if(x>=h or x<0 or y>=w or y<0) return false;
    if(grid[x][y]==-1) return false;
    return true;
}

vector<vector<int>> d(MAXN,vector<int> (MAXN,0));

int ans=1;
 
void bfs(int x,int y){
    deque<pii> q;
    q.push_back({x,y});
    //vis[x][y]=true;
    d[x][y]=1;
 
    while(q.size()){
        auto el=q.front();
        q.pop_front();

        ans=max(ans,d[el.fi][el.se]);
 
        for(int i=0;i<4;i++){
            int newx=el.fi+xyon[i];
            int newy=el.se+yyon[i];
 
            if(isvalid(newx,newy) and d[newx][newy]==0){
                //vis[newx][newy]=true;

                if(grid[newx][newy]==grid[el.fi][el.se]){
                    d[newx][newy]=grid[el.fi][el.se];
                    q.push_front({newx,newy});
                }
                else{
                    d[newx][newy]=grid[el.fi][el.se]+1;
                    q.push_back({newx,newy});
                }
                //cout<<"distance of "<<newx<<'-'<<newy<<" is: "<<d[newx][newy]<<endl;
            }
 
        }

        //grid[el.fi][el.se]=!grid[el.fi][el.se];
    }
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); 
 
    cin>>h>>w;
 
    map<char,int> anim;
    anim['F']=1;
    anim['R']=0;
    anim['.']=-1;

    //cout<<d[0][2]<<endl;
 
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            char c;
            cin>>c;
            grid[i][j]=anim[c];
        }
    }
 
    bfs(0,0);
    cout<<ans<<endl;
    //cout<<d[h][w]<<endl;
 
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2081 ms 607980 KB Time limit exceeded
2 Execution timed out 2145 ms 711800 KB Time limit exceeded
3 Execution timed out 2082 ms 613628 KB Time limit exceeded
4 Runtime error 1989 ms 1048576 KB Execution killed with signal 9
5 Execution timed out 2113 ms 673432 KB Time limit exceeded
6 Execution timed out 2093 ms 690440 KB Time limit exceeded
7 Execution timed out 2101 ms 628292 KB Time limit exceeded
8 Execution timed out 2086 ms 1004008 KB Time limit exceeded
9 Runtime error 1352 ms 1048576 KB Execution killed with signal 9
10 Execution timed out 2109 ms 1037196 KB Time limit exceeded
11 Execution timed out 2078 ms 630892 KB Time limit exceeded
12 Execution timed out 2089 ms 596404 KB Time limit exceeded
13 Execution timed out 2060 ms 660488 KB Time limit exceeded
14 Execution timed out 2056 ms 660804 KB Time limit exceeded
15 Execution timed out 2070 ms 71356 KB Time limit exceeded
16 Execution timed out 2126 ms 611444 KB Time limit exceeded
17 Execution timed out 2081 ms 636860 KB Time limit exceeded
18 Execution timed out 2005 ms 1048576 KB Time limit exceeded

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2081 ms 723360 KB Time limit exceeded
2 Runtime error 1996 ms 1048576 KB Execution killed with signal 9
3 Execution timed out 2011 ms 125748 KB Time limit exceeded
4 Execution timed out 2043 ms 94032 KB Time limit exceeded
5 Incorrect 215 ms 110528 KB Output isn't correct
6 Execution timed out 2055 ms 628632 KB Time limit exceeded
7 Runtime error 1771 ms 1048576 KB Execution killed with signal 9
8 Execution timed out 2099 ms 709176 KB Time limit exceeded
9 Execution timed out 2083 ms 65424 KB Time limit exceeded
10 Runtime error 1875 ms 1048576 KB Execution killed with signal 9
11 Execution timed out 2114 ms 755032 KB Time limit exceeded
12 Incorrect 37 ms 67156 KB Output isn't correct
13 Runtime error 1954 ms 1048576 KB Execution killed with signal 9
14 Execution timed out 2097 ms 704628 KB Time limit exceeded
15 Execution timed out 2077 ms 691764 KB Time limit exceeded
16 Execution timed out 2040 ms 1048576 KB Time limit exceeded
17 Runtime error 1895 ms 1048576 KB Execution killed with signal 9
18 Execution timed out 2093 ms 702868 KB Time limit exceeded
19 Execution timed out 2012 ms 94128 KB Time limit exceeded
20 Runtime error 1947 ms 1048576 KB Execution killed with signal 9
21 Execution timed out 2085 ms 680604 KB Time limit exceeded
22 Incorrect 220 ms 110416 KB Output isn't correct
23 Execution timed out 2110 ms 691328 KB Time limit exceeded
24 Runtime error 1891 ms 1048576 KB Execution killed with signal 9
25 Execution timed out 2055 ms 125712 KB Time limit exceeded
26 Runtime error 1483 ms 1048576 KB Execution killed with signal 9
27 Runtime error 1879 ms 1048576 KB Execution killed with signal 9
28 Execution timed out 2055 ms 634188 KB Time limit exceeded
29 Execution timed out 2077 ms 655888 KB Time limit exceeded
30 Runtime error 1807 ms 1048576 KB Execution killed with signal 9
31 Execution timed out 2063 ms 1048576 KB Time limit exceeded
32 Runtime error 1676 ms 1048576 KB Execution killed with signal 9