Submission #1118430

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118430		I_FloPPed21	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	205 ms	49684 KiB

skyscraper

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int radical=401,N=3e4+1;
vector<int>adj[N];
int dp[N][radical+1],n,m,best[N];
struct merg
{
    int nod,val,cost;
};
void asoc(int &a,int &b,int &c,merg &x)
{
    a=x.nod;
    b=x.val;
    c=x.cost;
}
void init(int n)
{
    for(int i=1; i<=n; i++)
        best[i]=1e9;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=radical; j++)
            dp[i][j]=1e9;
}
struct doge
{
    int poz,val;
} dog[N];

void citeste()
{
    cin>>n>>m;
    init(n);
    for(int i=1; i<=m; i++)
    {
        int a,b;
        cin>>dog[i].poz>>dog[i].val;
        dog[i].poz++;
        adj[dog[i].poz].push_back(dog[i].val);
    }

}
void rezolva()
{
    queue<merg>q;
    long long vals=-1;

     if(dog[1].val<=radical)
         vals=dog[1].val;
     else
     {
         int ctc=1;
         int nod=dog[1].poz;
         int u=dog[1].val;
         for(int j=nod+u; j<=n; j+=u)
         {
             if(best[j]>ctc)
             {
                 best[j]=ctc;
                 q.push({j,-1,ctc});
             }
             ctc++;
         }
         ctc=1;
         for(int j=nod-u; j>=1; j-=u)
         {
             if(best[j]>ctc)
             {
                 best[j]=ctc;
                 q.push({j,-1,ctc});
             }
             ctc++;
         }
     }
    q.push({dog[1].poz,vals,0});
    while(!q.empty())
    {
        int nod,valoare,cost;
        asoc(nod,valoare,cost,q.front());
        best[nod]=min(best[nod],cost);
        if(valoare!=-1)
        {
            if(nod+valoare<=n && dp[nod+valoare][valoare]>cost+1)
            {
                dp[nod+valoare][valoare]=cost+1;
                best[nod+valoare]=min(best[nod+valoare],cost+1);
                q.push({nod+valoare,valoare,cost+1});
            }
            if(nod-valoare>=1 && dp[nod-valoare][valoare]>cost+1)
            {
                dp[nod-valoare][valoare]=cost+1;
                best[nod-valoare]=min(best[nod-valoare],cost+1);
                q.push({nod-valoare,valoare,cost+1});
            }
        }
        for(auto u:adj[nod])
        {
            if(u<=radical)
                dp[nod][u]=min(dp[nod][u],cost);
            if(u>radical)
            {
                int ctc=1;
                for(int j=nod+u; j<=n; j+=u)
                {
                    if(best[j]>cost+ctc)
                    {
                        best[j]=cost+ctc;
                        q.push({j,-1,cost+ctc});
                    }
                    ctc++;
                }
                ctc=1;
                for(int j=nod-u; j>=1; j-=u)
                {
                    if(best[j]>cost+ctc)
                    {
                        best[j]=cost+ctc;
                        q.push({j,-1,cost+ctc});
                    }
                    ctc++;
                }
            }
            else
            {
                if(nod+u<=n &&dp[nod+u][u]>cost+1)
                {
                    dp[nod+u][u]=cost+1;
                    q.push({nod+u,u,cost+1});
                }
                if(nod-u>=1&&dp[nod-u][u]>cost+1)
                {
                    dp[nod-u][u]=cost+1;
                    q.push({nod-u,u,cost+1});
                }
            }
        }
        q.pop();
    }
    if(best[dog[2].poz]==1e9)
        cout<<-1<<'\n';
    else
        cout<<best[dog[2].poz]<<'\n';
}
int main()
{
    citeste();
    rezolva();

    return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'void citeste()':
skyscraper.cpp:37:13: warning: unused variable 'a' [-Wunused-variable]
   37 |         int a,b;
      |             ^
skyscraper.cpp:37:15: warning: unused variable 'b' [-Wunused-variable]
   37 |         int a,b;
      |               ^
skyscraper.cpp: In function 'void rezolva()':
skyscraper.cpp:76:24: warning: narrowing conversion of 'vals' from 'long long int' to 'int' [-Wnarrowing]
   76 |     q.push({dog[1].poz,vals,0});
      |                        ^~~~

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