Submission #420094

#	Time	Username	Problem	Language	Result	Execution time	Memory
420094		Dymo	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	1002 ms	62088 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;


#define ll  int
#define pll pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
#define endl "\n"
const ll maxn=3e4+10;
const ll mod =1e9+7 ;
const ll base=500;

ll b[maxn];
ll p[maxn];
ll dp[maxn][base+3];
bool dd[maxn];
vector<ll> adj[maxn];
vector<ll> adj1[maxn];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    if (fopen("t.inp", "r"))
    {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
   ll n, m  ;
    cin>> n>> m;
    ll st;
    ll ed;
    for (int i=1;i<=m;i++)
    {
        cin>>b[i]>>p[i];
        b[i]++;
        if (i==1) st=b[i];
        if (i==2) ed=b[i];
        if (p[i]<=base)
        {
           adj[b[i]].pb(p[i]);
        }
        else
        {
            adj1[b[i]].pb(p[i]);
        }
    }
    priority_queue<pair<ll,pll>,vector<pair<ll,pll>>, greater<pair<ll,pll>>> q;
    for (int i=1;i<=n;i++) for (int j=0;j<=base;j++) dp[i][j]=1e9;
    dp[st][0]=0;
    q.push(make_pair(dp[st][0],make_pair(st,0)));
    while (!q.empty())
    {
        auto p=q.top();
        q.pop();

        if (p.ff!=dp[p.ss.ff][p.ss.ss]) continue;
        ll t=p.ss.ss;
        ll u=p.ss.ff;
        if (!dd[u])
        {
            dd[u]=1;
            for (auto to:adj[u])
            {
                if (dp[u][to]>dp[u][t])
                {
                    dp[u][to]=dp[u][t];
                    q.push(make_pair(dp[u][to],make_pair(u,to)));
                }
            }
            for (auto to:adj1[u])
            {
                for (int j=(u%to ? u%to : to);j<=n;j+=to)
                {
                    if (dp[j][0]>dp[u][t]+abs(u-j)/to)
                    {
                       dp[j][0]=dp[u][t]+abs(u-j)/to;
                       q.push(make_pair(dp[j][0],make_pair(j,0)));
                    }
                }
            }
        }
        for (int j=-1;j<=1;j+=2)
        {
            ll nxt=u+j*t;
            if (nxt>=1&&nxt<=n&&dp[nxt][t]>dp[u][t]+1)
            {
                dp[nxt][t]=dp[u][t]+1;
                q.push(make_pair(dp[nxt][t],make_pair(nxt,t)));
            }
        }
    }
    ll h=1e9;
    for (int j=0;j<=base;j++) h=min(h,dp[ed][j]);
    if (h==1e9) h=-1;
    cout <<h<<endl;




}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:29:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:30:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:54:47: warning: 'st' may be used uninitialized in this function [-Wmaybe-uninitialized]
   54 |     q.push(make_pair(dp[st][0],make_pair(st,0)));
      |                                               ^
skyscraper.cpp:35:8: warning: 'ed' may be used uninitialized in this function [-Wmaybe-uninitialized]
   35 |     ll ed;
      |        ^~

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