oj.uz

Submission #1061959

# Submission time Handle Problem Language Result Execution time Memory
1061959 2024-08-16T16:01:14 Z sikai004 Tracks in the Snow (BOI13_tracks) C++14
89.0625 / 100
 2000 ms 104792 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;

    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int> >, greater<tuple<int, int, int> > > q; 
                     //pair contains <y_coord, x_coord>
    q.push(make_tuple(1,0, 0));    //push the starting node
    while (!q.empty()) {
        int weight=get<0>(q.top());
        int y = get<1>(q.top());
        int x = get<2>(q.top());

        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') and vis[new_y][new_x]==0){
                if(meadow[new_y][new_x]==meadow[y][x]){
                    vis[new_y][new_x]=vis[y][x];
                }
                else{
                    vis[new_y][new_x]=vis[y][x]+1;
                }
                q.push(make_tuple(vis[new_y][new_x],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:28:13: warning: unused variable 'weight' [-Wunused-variable]
   28 |         int weight=get<0>(q.top());
      |             ^~~~~~
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 37 ms 1880 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 21 ms 1640 KB Output is correct
5 Correct 4 ms 860 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 4 ms 604 KB Output is correct
11 Correct 5 ms 848 KB Output is correct
12 Correct 14 ms 856 KB Output is correct
13 Correct 4 ms 856 KB Output is correct
14 Correct 4 ms 856 KB Output is correct
15 Correct 28 ms 1884 KB Output is correct
16 Correct 40 ms 2048 KB Output is correct
17 Correct 20 ms 1884 KB Output is correct
18 Correct 21 ms 1572 KB Output is correct

Subtask #2
59.0625 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 98 ms 8344 KB Output is correct
3 Correct 417 ms 78928 KB Output is correct
4 Correct 117 ms 18844 KB Output is correct
5 Correct 179 ms 44608 KB Output is correct
6 Execution timed out 2016 ms 103780 KB Time limit exceeded
7 Correct 2 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 4 ms 860 KB Output is correct
10 Correct 1 ms 640 KB Output is correct
11 Correct 1 ms 612 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 110 ms 8404 KB Output is correct
14 Correct 62 ms 4952 KB Output is correct
15 Correct 19 ms 5468 KB Output is correct
16 Correct 51 ms 3676 KB Output is correct
17 Correct 255 ms 20564 KB Output is correct
18 Correct 73 ms 20140 KB Output is correct
19 Correct 115 ms 18936 KB Output is correct
20 Correct 103 ms 17852 KB Output is correct
21 Correct 258 ms 46164 KB Output is correct
22 Correct 182 ms 44636 KB Output is correct
23 Correct 539 ms 38932 KB Output is correct
24 Correct 169 ms 44932 KB Output is correct
25 Correct 338 ms 78960 KB Output is correct
26 Correct 968 ms 60496 KB Output is correct
27 Execution timed out 2075 ms 82068 KB Time limit exceeded
28 Execution timed out 2067 ms 104792 KB Time limit exceeded
29 Execution timed out 2047 ms 91832 KB Time limit exceeded
30 Execution timed out 2029 ms 91316 KB Time limit exceeded
31 Correct 1808 ms 51536 KB Output is correct
32 Correct 1744 ms 80528 KB Output is correct