oj.uz

Submission #877699

# Submission time Handle Problem Language Result Execution time Memory
877699 2023-11-23T12:58:00 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[5]={1,0,-1,0};
int yyon[5]={0,-1,0,1};
 
int say=0;
 
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;
 
    int all_steps=0;
 
    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;
 
}

Compilation message

tracks.cpp: In function 'int main()':
tracks.cpp:84:9: warning: unused variable 'all_steps' [-Wunused-variable]
   84 |     int all_steps=0;
      |         ^~~~~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2072 ms 613984 KB Time limit exceeded
2 Execution timed out 2088 ms 698740 KB Time limit exceeded
3 Execution timed out 2068 ms 637624 KB Time limit exceeded
4 Runtime error 1931 ms 1048576 KB Execution killed with signal 9
5 Execution timed out 2080 ms 624880 KB Time limit exceeded
6 Execution timed out 2053 ms 690872 KB Time limit exceeded
7 Execution timed out 2092 ms 641444 KB Time limit exceeded
8 Execution timed out 2062 ms 1048576 KB Time limit exceeded
9 Runtime error 1332 ms 1048576 KB Execution killed with signal 9
10 Execution timed out 2086 ms 1026444 KB Time limit exceeded
11 Execution timed out 2138 ms 687456 KB Time limit exceeded
12 Execution timed out 2123 ms 638848 KB Time limit exceeded
13 Execution timed out 2101 ms 641132 KB Time limit exceeded
14 Execution timed out 2058 ms 627904 KB Time limit exceeded
15 Execution timed out 2040 ms 71780 KB Time limit exceeded
16 Execution timed out 2073 ms 628756 KB Time limit exceeded
17 Execution timed out 2087 ms 636768 KB Time limit exceeded
18 Runtime error 1898 ms 1048576 KB Execution killed with signal 9

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2033 ms 124920 KB Time limit exceeded
2 Execution timed out 2068 ms 1048576 KB Time limit exceeded
3 Execution timed out 2021 ms 183544 KB Time limit exceeded
4 Execution timed out 2054 ms 98388 KB Time limit exceeded
5 Incorrect 384 ms 174868 KB Output isn't correct
6 Execution timed out 2128 ms 706352 KB Time limit exceeded
7 Runtime error 1755 ms 1048576 KB Execution killed with signal 9
8 Execution timed out 2053 ms 124756 KB Time limit exceeded
9 Execution timed out 2063 ms 65620 KB Time limit exceeded
10 Runtime error 1817 ms 1048576 KB Execution killed with signal 9
11 Execution timed out 2083 ms 752776 KB Time limit exceeded
12 Incorrect 34 ms 67420 KB Output isn't correct
13 Execution timed out 2066 ms 1041220 KB Time limit exceeded
14 Execution timed out 2103 ms 705972 KB Time limit exceeded
15 Execution timed out 2090 ms 712608 KB Time limit exceeded
16 Runtime error 1958 ms 1048576 KB Execution killed with signal 9
17 Runtime error 1872 ms 1048576 KB Execution killed with signal 9
18 Execution timed out 2052 ms 700724 KB Time limit exceeded
19 Execution timed out 2032 ms 98232 KB Time limit exceeded
20 Runtime error 1812 ms 1048576 KB Execution killed with signal 9
21 Execution timed out 2095 ms 709520 KB Time limit exceeded
22 Incorrect 372 ms 175860 KB Output isn't correct
23 Execution timed out 2080 ms 696816 KB Time limit exceeded
24 Runtime error 1866 ms 1048576 KB Execution killed with signal 9
25 Execution timed out 2104 ms 180740 KB Time limit exceeded
26 Runtime error 1426 ms 1048576 KB Execution killed with signal 9
27 Runtime error 1833 ms 1048576 KB Execution killed with signal 9
28 Execution timed out 2061 ms 688884 KB Time limit exceeded
29 Execution timed out 2086 ms 711928 KB Time limit exceeded
30 Runtime error 1744 ms 1048576 KB Execution killed with signal 9
31 Execution timed out 2015 ms 1048576 KB Time limit exceeded
32 Runtime error 1642 ms 1048576 KB Execution killed with signal 9