Submission #91552

#	Time	Username	Problem	Language	Result	Execution time	Memory
91552		Bodo171	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	193 ms	163944 KiB

skyscraper

#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
const int nmax=2005;
vector<int> v[nmax];
pair<int,int> q[2][nmax*nmax];
int d[nmax][nmax];
int p[2],u[2];
int n,m,i,j,wh,x,cost,use,fin,k;
void prp(int a,int b,int dist,int wh)
{
    if(dist<d[a][b])
    {
        d[a][b]=dist;
        q[wh][++u[wh]]={a,b};
    }
}
int dij()
{
    p[0]=u[0]=1;
    for(cost=0;cost<=n*n;cost++)
    {
        p[1-use]=1;u[1-use]=0;
        while(p[use]<=u[use])
        {
            i=q[use][p[use]].first;j=q[use][p[use]].second;
            ++p[use];
            if(i==fin)
                return cost;
            if(i-j>=0) prp(i-j,j,cost+1,1-use);
            if(i+j<n)  prp(i+j,j,cost+1,1-use);
            for(k=0;k<v[i].size();k++)
                prp(i,v[i][k],cost,use);
        }
        use=1-use;
    }
    return -1;
}
int main()
{
    //freopen("data.in","r",stdin);
    ios_base::sync_with_stdio(false);
    cin>>n>>m;
    for(i=0;i<n;i++)
        for(j=1;j<=n;j++)
          d[i][j]=2*n*n;
    for(i=0;i<m;i++)
    {
        cin>>wh>>x;
        v[wh].push_back(x);
        if(i==0)
           q[0][1]={wh,x},d[wh][x]=0;
        if(i==1)
            fin=wh;
    }
    cout<<dij();
    return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int dij()':
skyscraper.cpp:33:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(k=0;k<v[i].size();k++)
                     ~^~~~~~~~~~~~

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