oj.uz

Submission #877706

# Submission time Handle Problem Language Result Execution time Memory
877706 2023-11-23T13:03:04 Z asli_bg Tracks in the Snow (BOI13_tracks) C++11
0 / 100
 2000 ms 1048580 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]=='.') 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 2064 ms 544628 KB Time limit exceeded
2 Execution timed out 2054 ms 639916 KB Time limit exceeded
3 Execution timed out 2115 ms 596788 KB Time limit exceeded
4 Execution timed out 2107 ms 1048580 KB Time limit exceeded
5 Execution timed out 2131 ms 594472 KB Time limit exceeded
6 Execution timed out 2100 ms 654644 KB Time limit exceeded
7 Execution timed out 2066 ms 596820 KB Time limit exceeded
8 Execution timed out 2088 ms 1021628 KB Time limit exceeded
9 Runtime error 1385 ms 1048576 KB Execution killed with signal 9
10 Execution timed out 2071 ms 1001356 KB Time limit exceeded
11 Execution timed out 2122 ms 635812 KB Time limit exceeded
12 Execution timed out 2069 ms 596504 KB Time limit exceeded
13 Execution timed out 2044 ms 577904 KB Time limit exceeded
14 Execution timed out 2086 ms 589292 KB Time limit exceeded
15 Execution timed out 2043 ms 71872 KB Time limit exceeded
16 Execution timed out 2085 ms 558192 KB Time limit exceeded
17 Execution timed out 2114 ms 585644 KB Time limit exceeded
18 Execution timed out 2011 ms 1048576 KB Time limit exceeded

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2063 ms 124868 KB Time limit exceeded
2 Execution timed out 2098 ms 1015824 KB Time limit exceeded
3 Execution timed out 2045 ms 183412 KB Time limit exceeded
4 Execution timed out 2061 ms 98196 KB Time limit exceeded
5 Incorrect 414 ms 174980 KB Output isn't correct
6 Execution timed out 2080 ms 631744 KB Time limit exceeded
7 Runtime error 1807 ms 1048576 KB Execution killed with signal 9
8 Execution timed out 2099 ms 124752 KB Time limit exceeded
9 Execution timed out 2032 ms 65616 KB Time limit exceeded
10 Runtime error 1927 ms 1048576 KB Execution killed with signal 9
11 Execution timed out 2068 ms 700164 KB Time limit exceeded
12 Incorrect 35 ms 67412 KB Output isn't correct
13 Execution timed out 2123 ms 1034960 KB Time limit exceeded
14 Execution timed out 2096 ms 653544 KB Time limit exceeded
15 Execution timed out 2060 ms 644356 KB Time limit exceeded
16 Execution timed out 2111 ms 1048576 KB Time limit exceeded
17 Runtime error 1983 ms 1048576 KB Execution killed with signal 9
18 Execution timed out 2069 ms 658672 KB Time limit exceeded
19 Execution timed out 2056 ms 98380 KB Time limit exceeded
20 Runtime error 1906 ms 1048576 KB Execution killed with signal 9
21 Execution timed out 2094 ms 673256 KB Time limit exceeded
22 Incorrect 395 ms 176036 KB Output isn't correct
23 Execution timed out 2109 ms 668204 KB Time limit exceeded
24 Runtime error 1955 ms 1048576 KB Execution killed with signal 9
25 Execution timed out 2029 ms 180684 KB Time limit exceeded
26 Runtime error 1497 ms 1048576 KB Execution killed with signal 9
27 Runtime error 1991 ms 1048576 KB Execution killed with signal 9
28 Execution timed out 2069 ms 646932 KB Time limit exceeded
29 Execution timed out 2095 ms 674936 KB Time limit exceeded
30 Runtime error 1793 ms 1048576 KB Execution killed with signal 9
31 Execution timed out 2076 ms 1048576 KB Time limit exceeded
32 Runtime error 1632 ms 1048576 KB Execution killed with signal 9