Submission #91570

#	Time	Username	Problem	Language	Result	Execution time	Memory
91570		Bodo171	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	683 ms	36440 KiB

skyscraper

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
const int nmax=30005;
const int buck=200;
vector<int> v[nmax],mare[nmax];
bool E[nmax];
int d[nmax][buck+5];
int n,m,i,j,wh,x,cost,use,fin,k,val,md;
struct node
{
    int fi,se,cat;
};
struct cmp
{
    bool operator() (node unu,node doi)
    {
        return unu.cat>doi.cat;
    }
};
priority_queue< node,vector<node>, cmp > pq;
void prp(int a,int b,int dist)
{
    if(dist<d[a][b])
    {
        d[a][b]=dist;
        pq.push({a,b,d[a][b]});
    }
}
int abss(int x)
{
    if(x<0) return -x;
    return x;
}
int dij()
{
    while(!pq.empty())
    {
        i=pq.top().fi;
        j=pq.top().se;
        cost=pq.top().cat;
        pq.pop();
        if(cost==d[i][j])
        {
            if(i==fin)
                return cost;
            if(i-j>=0) prp(i-j,j,cost+1);
            if(i+j<n)  prp(i+j,j,cost+1);
            for(k=0; k<v[i].size(); k++)
                prp(i,v[i][k],cost);
            if(!E[i])
            {
                E[i]=1;
                for(k=0; k<mare[i].size(); k++)
                {
                    val=mare[i][k];
                    md=i%val;
                    for(j=md; j<n; j+=val)
                        prp(j,0,cost+abss(j-i)/val);
                }
            }
        }
    }
    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=0;j<=buck;j++)
          d[i][j]=INT_MAX;
    for(i=0;i<m;i++)
    {
        cin>>wh>>x;
        if(x<=buck) v[wh].push_back(x);
        else mare[wh].push_back(x);
        if(i==0)
           pq.push({wh,0,0}),d[wh][0]=0;
        if(i==1)
            fin=wh;
    }
    cout<<dij();
    return 0;
}

Compilation message (stderr)

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

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