Submission #487246

#	Time	Username	Problem	Language	Result	Execution time	Memory
487246		ala2	Rainforest Jumps (APIO21_jumps)	C++14	21 / 100	276 ms	39552 KiB

jumps

        #include "jumps.h"
         
        #include <vector>

        #include <queue>
        using namespace std;
         int n; vector<int>h;  vector<int>v[10100];  int vi[2100][2100];  int d[2010][2010]; int g[1000100];
         
         queue<int>q;  int mn=1000000023;
         void bfs(int node)
         {
             vi[node][node]=1;
            q.push(node);
             while(!q.empty()){
                    int u=q.front();
             q.pop();//  cout<<"       "<<u<<endl;
             d[node][node]=0;
             for(int i=0;i<v[u].size();i++)
             {
                 if(!vi[node][v[u][i]]){
                 q.push(v[u][i]);
                 d[node][v[u][i]]=d[node][u]+1;
                 vi[node][v[u][i]]=1;
                                      }
             }
         
             }
         
         }
         
        void init(int N, vector<int> H) {
            n=N;
            for(int i=0;i<n;i++)
            {
                h.push_back(H[i]);
            }
            for(int i=0;i<n;i++)
            {
                 for(int j=i-1;j>=0;j--)
                 {
                     if(h[j]>h[i])
                     {
                         v[i].push_back(j);  d[i][j]=1;
                         break;
                     }
                 }
                 for(int j=i+1;j<n;j++)
                 {
                     if(h[j]>h[i])
                     {
                         v[i].push_back(j);  d[i][j]=1;
                         break;
                     }
                 }
            }
           for(int i=0;i<n;i++) bfs(i);
         
         
        }
         
        int minimum_jumps(int A, int B, int C, int D) {
        mn=1000000003;  //cout<<"            "<<d[3][6]<<endl;
           for(int i=A;i<=B;i++)
           {
               for(int j=C;j<=D;j++)
               {   if(d[i][j])
                   mn=min(mn,d[i][j]);
               }
           }
           if(mn==1000000003) return -1;
        return mn;
        //  return 0;
        }

Compilation message (stderr)

jumps.cpp: In function 'void bfs(int)':
jumps.cpp:18:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |              for(int i=0;i<v[u].size();i++)
      |                          ~^~~~~~~~~~~~

• Subtask 1: 0 / 4
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 0 / 12
• Subtask 5: 0 / 23
• Subtask 6: 0 / 21
• Subtask 7: 0 / 19