Submission #151860

#	Time	Username	Problem	Language	Result	Execution time	Memory
151860		Ruxandra985	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	10 / 100	19 ms	17016 KiB

skyscraper

/// verific niste observatii
#include <cstdio>
#include <deque>
#include <vector>
#include <algorithm>
#define DIM 2010
#define DIMN 30010

using namespace std;
int f[DIM][DIM],dp[DIM][DIM],ch[DIMN];
pair <int,int> v[DIMN];
deque <pair <int,int> > dq;
vector <int> poz[DIMN];
int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int n,m,i,curr,jump,idx,j;
    fscanf (fin,"%d%d",&n,&m);
    for (i=1;i<=m;i++){
        fscanf (fin,"%d%d",&v[i].first,&v[i].second);
        v[i].first++;
        poz[v[i].first].push_back(i);
    }
    for (i=1;i<DIM;i++)
        for (j=1;j<DIM;j++)
            dp[i][j] = 2000000000;
    dp[1][v[1].second] = 0;
    dq.push_back(make_pair(1,v[1].second));
    while (!dq.empty()){
        curr = dq.front().first;
        jump = dq.front().second;
        //if (curr == 3 && jump == 2)
          //  printf ("a");
        if (curr == v[2].first)
            break;
        dq.pop_front();
        /// distanta minima ca sa ajungi in skyscrape ul curr cu jump

        if (curr + jump <= n){ /// faci o saritura
            /// nu schimbi
            if (!f[curr + jump][jump]){
                f[curr+jump][jump] = 1;
                dp[curr + jump][jump] = 1 + dp[curr][jump];
                dq.push_back(make_pair(curr+jump,jump));
            }
            if (!ch[curr + jump]){ /// schimbi
                ch[curr + jump] = 1;
                for (i=0;i<poz[curr+jump].size();i++){
                    idx = poz[curr + jump][i];
                    if (!f[curr + jump][v[idx].second]){
                        f[curr + jump][v[idx].second] = 1;
                        dp[curr + jump][v[idx].second] = 1 + dp[curr][jump];
                        dq.push_back(make_pair(curr+jump , v[idx].second));
                    }
                }
            }
        }


         if (curr - jump > 0){ /// faci o saritura
            /// nu schimbi
            if (!f[curr - jump][jump]){
                f[curr - jump][jump] = 1;
                dp[curr - jump][jump] = 1 + dp[curr][jump];
                dq.push_back(make_pair(curr-jump,jump));
            }
            if (!ch[curr - jump]){ /// schimbi
                ch[curr - jump] = 1;
                for (i=0;i<poz[curr-jump].size();i++){
                    idx = poz[curr - jump][i];
                    if (!f[curr - jump][v[idx].second]){
                        f[curr - jump][v[idx].second] = 1;
                        dp[curr - jump][v[idx].second] = 1 + dp[curr][jump];
                        dq.push_back(make_pair(curr-jump , v[idx].second));
                    }
                }
            }
        }
    }
    if (dq.empty())
        fprintf (fout,"-1");
    else fprintf (fout,"%d",dp[curr][jump]);
    return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:49:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for (i=0;i<poz[curr+jump].size();i++){
                          ~^~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:70:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for (i=0;i<poz[curr-jump].size();i++){
                          ~^~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:19:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%d%d",&n,&m);
     ~~~~~~~^~~~~~~~~~~~~~~~~~
skyscraper.cpp:21:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%d%d",&v[i].first,&v[i].second);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 0 / 12
• Subtask 3: 0 / 14
• Subtask 4: 0 / 21
• Subtask 5: 0 / 43