Submission #164900

#	Time	Username	Problem	Language	Result	Execution time	Memory
164900		combi1k1	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	10 / 100	155 ms	148660 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[j + p].pb(ii(j,1));
            for(int j = b + p ; j <  n ; j += p)    g[j - p].pb(ii(j,1));
        }

        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));
    }
    memset(d,-1,sizeof d);  d[s] = 0;

    queue<int>  q;  q.push(s);

    while (q.size())    {
        int u = q.front();  q.pop();
        for(ii  e : g[u])   {
            int v = e.X;
            int w = e.Y;
            if (d[v] < 0)   {
                d[v] = d[u] + w;
                q.push(v);
            }
        }
    }

    cout << d[t] << endl;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:66:16: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
     cout << d[t] << endl;
                ^

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