Submission #164912

#	Time	Username	Problem	Language	Result	Execution time	Memory
164912		combi1k1	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	497 ms	121000 KiB

skyscraper

#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native"

#include<bits/stdc++.h>

using namespace std;

#define X   first
#define Y   second

#define pb  push_back

const int   N   = 1e6 + 1;

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;

    vector<ii>  doge;

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

        assert(p > 0);

        if (p < 30) {
            g[b].pb(ii(p * n + b,0));
            doge.pb(ii(p,b % p));
        }
        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;
    }
    sort(doge.begin(),doge.end());
    doge.erase(unique(doge.begin(),doge.end()),doge.end());

    for(ii  a : doge)   {
        int b = a.Y;
        int p = a.X;
        for(int i = b ; i < n ; i += p) {
            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 < 30 ; ++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));
            }
        }
    }

    cout << (d[t] < 1e9 + 7 ? d[t] : -1) << endl;
}

Compilation message (stderr)

skyscraper.cpp:1:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/stack:200000000")
 
skyscraper.cpp:3:20: warning: '#pragma GCC target (string [,string]...)' does not have a final ')' [-Wpragmas]
 #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native"
                    ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:96:17: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
     cout << (d[t] < 1e9 + 7 ? d[t] : -1) << endl;
              ~~~^

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