oj.uz

Submission #1061936

# Submission time Handle Problem Language Result Execution time Memory
1061936 2024-08-16T15:37:13 Z sikai004 Tracks in the Snow (BOI13_tracks) C++14
65 / 100
 2000 ms 97876 KB 
#include <bits/stdc++.h>
using namespace std;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int row, col;
    cin>>row>>col;
    char meadow[row][col];
    int vis[row][col];
    for(int i=0;i<row;i++){
        fill(vis[i],vis[i]+col,0);
    }
    for(int i=0;i<row;i++){
        for(int j=0;j<col;j++){
            cin>>meadow[i][j];
        }
    }
    int numberoftimes=0;
    if(meadow[0][0]=='.')return 0;
    int dx[4] = {0, 0, -1, 1},dy[4] = {1, -1, 0, 0};          //dx and dy stores the way to get to the adjacent nodes

    vis[0][0]=1;

    queue<tuple<int, int,int,char> > q;                       //pair contains <y_coord, x_coord>
    q.push(make_tuple(0, 0,1,meadow[0][0]));    //push the starting node
    while (!q.empty()) {
        int y = get<0>(q.front());
        int x = get<1>(q.front());

        int number = get<2>(q.front());
        char currchar = get<3>(q.front());
        q.pop();
        for (int i = 0; i < 4; i++) {
            int new_y = y + dy[i], new_x = x + dx[i];              //adjacent nodes
            if(new_y>=0 and new_y<row and new_x>=0 and new_x<col and (meadow[new_y][new_x]=='F' or meadow[new_y][new_x]=='R')){
                if(vis[new_y][new_x]==0){
                    if(meadow[new_y][new_x]!=currchar){
                        vis[new_y][new_x]=number+1;
                        q.push(make_tuple(new_y,new_x,number+1,meadow[new_y][new_x]));
                        //if(new_y==2 and new_x==1)cout<<"FUCK OFF";

                        //if(new_y==3 and new_x==7)cout<<"HI"<<number;
                    }
                    else{
                        vis[new_y][new_x]=number;
                        q.push(make_tuple(new_y,new_x,number,meadow[new_y][new_x]));
                    }
                }
                else if(meadow[new_y][new_x]==currchar and vis[new_y][new_x]>number){
                    vis[new_y][new_x]=number;
                    q.push(make_tuple(new_y,new_x,number,meadow[new_y][new_x]));
                }
                else if(meadow[new_y][new_x]!=currchar and vis[new_y][new_x]>number+1){
                    vis[new_y][new_x]=number+1;
                    q.push(make_tuple(new_y,new_x,number+1,meadow[new_y][new_x]));
                }
            }
            //check if new node is within bounds, not visited and reachable (code for if it is not)
        }

        //cout<<"y: "<<y<<" x: "<<x<<" vis: "<<vis[y][x]<<" currchar: "<<currchar<<" number: "<<number<<"\n";
        
    }
    /*
    for(int i=0;i<row;i++){
        for(int j=0;j<col;j++){
            cout<<vis[i][j]<<" ";
        }
        cout<<"\n";
    }
    */
    int maxx=-1;
    for(int i=0;i<row;i++){
        for(int j=0;j<col;j++){
            maxx=max(maxx,vis[i][j]);
        }
        //cout<<"\n";
    }
    cout<<maxx;
}        
        
    

    /*
    for(int i=0;i<row;i++){
        for(int j=0;j<col;j++){
            cout<<vis[i][j]<<" ";
        }
        cout<<"\n";
    }
    */
    //cout<<numberoftimes;

Compilation message

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

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 647 ms 2748 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 135 ms 1488 KB Output is correct
5 Correct 35 ms 856 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 3 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 18 ms 852 KB Output is correct
11 Correct 11 ms 604 KB Output is correct
12 Correct 147 ms 1380 KB Output is correct
13 Correct 32 ms 856 KB Output is correct
14 Correct 32 ms 856 KB Output is correct
15 Correct 456 ms 2648 KB Output is correct
16 Correct 642 ms 2704 KB Output is correct
17 Correct 295 ms 2388 KB Output is correct
18 Correct 135 ms 1488 KB Output is correct

Subtask #2
35.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Execution timed out 2078 ms 10376 KB Time limit exceeded
3 Execution timed out 2045 ms 94432 KB Time limit exceeded
4 Execution timed out 2016 ms 24656 KB Time limit exceeded
5 Correct 155 ms 53148 KB Output is correct
6 Execution timed out 2073 ms 97876 KB Time limit exceeded
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 159 ms 848 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Execution timed out 2096 ms 10252 KB Time limit exceeded
14 Correct 905 ms 5972 KB Output is correct
15 Correct 16 ms 6232 KB Output is correct
16 Correct 1635 ms 5028 KB Output is correct
17 Execution timed out 2082 ms 25620 KB Time limit exceeded
18 Correct 71 ms 23908 KB Output is correct
19 Execution timed out 2068 ms 24660 KB Time limit exceeded
20 Execution timed out 2040 ms 20708 KB Time limit exceeded
21 Execution timed out 2013 ms 55184 KB Time limit exceeded
22 Correct 149 ms 53076 KB Output is correct
23 Execution timed out 2059 ms 47648 KB Time limit exceeded
24 Correct 158 ms 53840 KB Output is correct
25 Correct 354 ms 94288 KB Output is correct
26 Correct 466 ms 72276 KB Output is correct
27 Execution timed out 2068 ms 95060 KB Time limit exceeded
28 Execution timed out 2012 ms 97872 KB Time limit exceeded
29 Execution timed out 2044 ms 97360 KB Time limit exceeded
30 Execution timed out 2045 ms 95312 KB Time limit exceeded
31 Execution timed out 2035 ms 63824 KB Time limit exceeded
32 Execution timed out 2069 ms 96756 KB Time limit exceeded