oj.uz

Submission #877581

# Submission time Handle Problem Language Result Execution time Memory
877581 2023-11-23T10:45:12 Z asli_bg Tracks in the Snow (BOI13_tracks) C++11
0 / 100
 806 ms 153776 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;
    return true;
}

int d[MAXN][MAXN];

void bfs(int x,int y){
    queue<pii> q;
    q.push({x,y});
    vis[x][y]=true;
    d[x][y]=0;

    while(!q.empty()){
        auto el=q.front();
        q.pop();

        for(int i=0;i<4;i++){
            int newx=el.fi+xyon[i];
            int newy=el.se+yyon[i];

            if(isvalid(newx,newy) and !vis[newx][newy]){
                vis[newx][newy]=true;
                q.push({newx,newy});
                d[newx][newy]+=d[el.fi][el.se]+(grid[newx][newy]==grid[el.fi][el.se]?0:1);
                //cout<<"distance of "<<grid[newx][newy]<<" is: "<<d[newx][newy]<<endl;
            }

        }
    }
}
 
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;

    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<<d[h-1][w-1]<<endl;

}

Compilation message

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

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 23132 KB Output isn't correct
2 Incorrect 1 ms 6492 KB Output isn't correct
3 Incorrect 1 ms 6748 KB Output isn't correct
4 Incorrect 9 ms 22876 KB Output isn't correct
5 Incorrect 5 ms 15920 KB Output isn't correct
6 Incorrect 1 ms 6492 KB Output isn't correct
7 Incorrect 1 ms 6748 KB Output isn't correct
8 Incorrect 1 ms 6748 KB Output isn't correct
9 Incorrect 2 ms 9052 KB Output isn't correct
10 Incorrect 4 ms 13660 KB Output isn't correct
11 Incorrect 3 ms 11356 KB Output isn't correct
12 Incorrect 8 ms 15848 KB Output isn't correct
13 Incorrect 6 ms 15916 KB Output isn't correct
14 Incorrect 7 ms 15840 KB Output isn't correct
15 Incorrect 14 ms 23004 KB Output isn't correct
16 Incorrect 12 ms 22876 KB Output isn't correct
17 Incorrect 14 ms 22872 KB Output isn't correct
18 Incorrect 8 ms 22876 KB Output isn't correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 140372 KB Output isn't correct
2 Incorrect 78 ms 50004 KB Output isn't correct
3 Incorrect 794 ms 153484 KB Output isn't correct
4 Incorrect 147 ms 74576 KB Output isn't correct
5 Incorrect 396 ms 117748 KB Output isn't correct
6 Incorrect 711 ms 153720 KB Output isn't correct
7 Incorrect 20 ms 141100 KB Output isn't correct
8 Incorrect 20 ms 140368 KB Output isn't correct
9 Incorrect 3 ms 6748 KB Output isn't correct
10 Incorrect 2 ms 4700 KB Output isn't correct
11 Incorrect 20 ms 140816 KB Output isn't correct
12 Incorrect 2 ms 11100 KB Output isn't correct
13 Incorrect 73 ms 50000 KB Output isn't correct
14 Incorrect 45 ms 37968 KB Output isn't correct
15 Incorrect 41 ms 42068 KB Output isn't correct
16 Incorrect 26 ms 19036 KB Output isn't correct
17 Incorrect 171 ms 79364 KB Output isn't correct
18 Incorrect 162 ms 79612 KB Output isn't correct
19 Incorrect 180 ms 74412 KB Output isn't correct
20 Incorrect 145 ms 69968 KB Output isn't correct
21 Incorrect 438 ms 122508 KB Output isn't correct
22 Incorrect 356 ms 117840 KB Output isn't correct
23 Incorrect 336 ms 98632 KB Output isn't correct
24 Incorrect 446 ms 122108 KB Output isn't correct
25 Incorrect 806 ms 153724 KB Output isn't correct
26 Incorrect 535 ms 138688 KB Output isn't correct
27 Incorrect 685 ms 153724 KB Output isn't correct
28 Incorrect 679 ms 153776 KB Output isn't correct
29 Incorrect 704 ms 153680 KB Output isn't correct
30 Incorrect 656 ms 153148 KB Output isn't correct
31 Incorrect 511 ms 125716 KB Output isn't correct
32 Incorrect 707 ms 153720 KB Output isn't correct