oj.uz

Submission #877702

# Submission time Handle Problem Language Result Execution time Memory
877702 2023-11-23T13:01:32 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]=='.') 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.empty()){
        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 2076 ms 623164 KB Time limit exceeded
2 Execution timed out 2069 ms 693092 KB Time limit exceeded
3 Execution timed out 2066 ms 640728 KB Time limit exceeded
4 Execution timed out 2009 ms 1048576 KB Time limit exceeded
5 Execution timed out 2090 ms 626740 KB Time limit exceeded
6 Execution timed out 2072 ms 685924 KB Time limit exceeded
7 Execution timed out 2065 ms 610316 KB Time limit exceeded
8 Execution timed out 2102 ms 1048576 KB Time limit exceeded
9 Runtime error 1364 ms 1048576 KB Execution killed with signal 9
10 Execution timed out 2109 ms 1044168 KB Time limit exceeded
11 Execution timed out 2090 ms 659964 KB Time limit exceeded
12 Execution timed out 2103 ms 631256 KB Time limit exceeded
13 Execution timed out 2079 ms 628348 KB Time limit exceeded
14 Execution timed out 2054 ms 599048 KB Time limit exceeded
15 Execution timed out 2047 ms 71760 KB Time limit exceeded
16 Execution timed out 2090 ms 617792 KB Time limit exceeded
17 Execution timed out 2074 ms 630976 KB Time limit exceeded
18 Execution timed out 2126 ms 1048316 KB Time limit exceeded

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2013 ms 124760 KB Time limit exceeded
2 Execution timed out 2096 ms 1018468 KB Time limit exceeded
3 Execution timed out 2063 ms 183696 KB Time limit exceeded
4 Execution timed out 2007 ms 98384 KB Time limit exceeded
5 Incorrect 372 ms 174832 KB Output isn't correct
6 Execution timed out 2124 ms 699456 KB Time limit exceeded
7 Runtime error 1967 ms 1048576 KB Execution killed with signal 9
8 Execution timed out 2065 ms 124804 KB Time limit exceeded
9 Execution timed out 2009 ms 65404 KB Time limit exceeded
10 Runtime error 1921 ms 1048576 KB Execution killed with signal 9
11 Execution timed out 2093 ms 760880 KB Time limit exceeded
12 Incorrect 32 ms 67408 KB Output isn't correct
13 Execution timed out 2096 ms 1048576 KB Time limit exceeded
14 Execution timed out 2108 ms 697196 KB Time limit exceeded
15 Execution timed out 2073 ms 692900 KB Time limit exceeded
16 Runtime error 1966 ms 1048576 KB Execution killed with signal 9
17 Runtime error 1873 ms 1048576 KB Execution killed with signal 9
18 Execution timed out 2061 ms 706244 KB Time limit exceeded
19 Execution timed out 2106 ms 98384 KB Time limit exceeded
20 Runtime error 1877 ms 1048576 KB Execution killed with signal 9
21 Execution timed out 2043 ms 699584 KB Time limit exceeded
22 Incorrect 395 ms 174948 KB Output isn't correct
23 Execution timed out 2086 ms 682868 KB Time limit exceeded
24 Runtime error 1899 ms 1048576 KB Execution killed with signal 9
25 Execution timed out 2092 ms 180820 KB Time limit exceeded
26 Runtime error 1661 ms 1048576 KB Execution killed with signal 9
27 Execution timed out 2104 ms 999864 KB Time limit exceeded
28 Execution timed out 2072 ms 674320 KB Time limit exceeded
29 Execution timed out 2077 ms 692556 KB Time limit exceeded
30 Runtime error 1803 ms 1048576 KB Execution killed with signal 9
31 Execution timed out 2067 ms 1048576 KB Time limit exceeded
32 Runtime error 1645 ms 1048576 KB Execution killed with signal 9