oj.uz

Submission #1061986

# Submission time Handle Problem Language Result Execution time Memory
1061986 2024-08-16T16:20:13 Z sikai004 Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 572 ms 134408 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;
    int maxweight=-1;
    //priority_queue<tuple<int, int, int>, vector<tuple<int, int, int> >, greater<tuple<int, int, int> > > q; 
    deque<tuple<int,int,int> > q;
                     //pair contains <y_coord, x_coord>
    q.push_front(make_tuple(1,0, 0));    //push the starting node
    while (!q.empty()) {
        int weight=get<0>(q.front());
        maxweight=max(maxweight,weight);
        int y = get<1>(q.front());
        int x = get<2>(q.front());

        q.pop_front();
        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];
                    q.push_front(make_tuple(vis[new_y][new_x],new_y,new_x));

                }
                else{
                    vis[new_y][new_x]=vis[y][x]+1;
                    q.push_back(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";
    }
    */

    cout<<maxweight;
    
}        
        
    

    /*
    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 13 ms 1628 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 6 ms 1476 KB Output is correct
5 Correct 2 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 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 4 ms 860 KB Output is correct
13 Correct 2 ms 860 KB Output is correct
14 Correct 2 ms 860 KB Output is correct
15 Correct 10 ms 1680 KB Output is correct
16 Correct 12 ms 1628 KB Output is correct
17 Correct 7 ms 1416 KB Output is correct
18 Correct 5 ms 1372 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 39 ms 8104 KB Output is correct
3 Correct 263 ms 78704 KB Output is correct
4 Correct 61 ms 18780 KB Output is correct
5 Correct 132 ms 44376 KB Output is correct
6 Correct 569 ms 98772 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 2 ms 604 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 560 KB Output is correct
13 Correct 37 ms 8124 KB Output is correct
14 Correct 21 ms 4880 KB Output is correct
15 Correct 16 ms 5332 KB Output is correct
16 Correct 21 ms 3420 KB Output is correct
17 Correct 104 ms 20272 KB Output is correct
18 Correct 60 ms 20000 KB Output is correct
19 Correct 59 ms 18776 KB Output is correct
20 Correct 57 ms 17240 KB Output is correct
21 Correct 155 ms 45848 KB Output is correct
22 Correct 131 ms 44460 KB Output is correct
23 Correct 195 ms 38236 KB Output is correct
24 Correct 135 ms 44916 KB Output is correct
25 Correct 247 ms 78704 KB Output is correct
26 Correct 322 ms 134408 KB Output is correct
27 Correct 421 ms 110568 KB Output is correct
28 Correct 564 ms 98772 KB Output is correct
29 Correct 572 ms 95812 KB Output is correct
30 Correct 507 ms 101312 KB Output is correct
31 Correct 520 ms 51080 KB Output is correct
32 Correct 375 ms 97728 KB Output is correct