Submission #164899

#	Time	Username	Problem	Language	Result	Execution time	Memory
164899		combi1k1	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	753 ms	262148 KiB

skyscraper

#include<bits/stdc++.h>

using namespace std;

#define X   first
#define Y   second

#define pb  push_back

const int   N   = 5400000;

typedef pair<int,int>   ii;

vector<ii>  g[N];

int d[N];

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;  cin >> n;
    int m;  cin >> m;

    int s, t;

    for(int i = 0 ; i < m ; ++i)    {
        int b;  cin >> b;
        int p;  cin >> p;

        if (p < 175)    g[b].pb(ii(p * n + b,0));
        else    {
            for(int j = b - p ; j >= 0 ; j -= p)    g[b].pb(ii(j,(b - j) / p));
            for(int j = b + p ; j <  n ; j += p)    g[b].pb(ii(j,(j - b) / p));
        }

        if (i == 0) s = b;
        if (i == 1) t = b;
    }
    for(int p = 1 ; p < 175 ; ++p)
    for(int i = 0 ; i < n ; ++i)    {
        int u = p * n + i;
        int v = p * n + i + p;
        if (v < p * n + n)
            g[u].pb(ii(v,1)),
            g[v].pb(ii(u,1));

        g[u].pb(ii(i,0));
    }
    for(int i = 0 ; i < 175 ; ++i)
    for(int j = 0 ; j < n ; ++j)
        d[i * n + j] = 1e9 + 7;

    d[s] = 0;

    priority_queue<ii,vector<ii>,greater<ii> >  pq;

    pq.push(ii(0,s));

    while (pq.size())   {
        int du = pq.top().X;
        int  u = pq.top().Y;

        pq.pop();

        if (du != d[u])
            continue;

        for(ii  e : g[u])   {
            int v = e.X;
            int w = e.Y;
            if (d[v] > du + w)    {
                d[v] = du + w;
                pq.push(ii(d[v],v));
            }
        }
    }

    int ans = d[t];

    if (ans == 1e9 + 7)
        ans = -1;

    cout << ans << endl;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:79:9: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int ans = d[t];
         ^~~

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