Submission #1278210

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278210		hoangtien69	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	100 / 100	125 ms	10224 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 3e4 + 5;
const int block = 170;
#define pii pair<int,int>

int n, m;
vector<int> adj[MAXN];
int b[MAXN];
int p[MAXN];
int start = 0;
int endd = 0;
int d[MAXN];
bool ck[MAXN][block];

void dijskstra()
{
    for (int i = 0; i < n; i++)
    {
        d[i] = INT_MAX;
    }
    d[start] = 0;
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({d[start], start});
    while(!pq.empty())
    {
        auto[dist, u] = pq.top();
        pq.pop();
        if (dist > d[u])
        {
            continue;
        }
        if (u == endd)
        {
            break;
        }
        for (int v : adj[u])
        {
            if (v >= block || (v < block and ck[u][v] == false))
            {
                for (int i = u + v; i < n; i += v)
                {
                    if (d[i] > d[u] + (i - u) / v)
                    {
                        d[i] = d[u] + (i - u) / v;
                        pq.push({d[i], i});
                    }
                    if (v < block)
                    {
                        if (ck[i][v] == true)
                        {
                            break;
                        }
                        ck[i][v] = true;
                    }
                }
                for (int i = u - v; i >= 0; i -= v)
                {
                    if (d[i] > d[u] + (u - i) / v)
                    {
                        d[i] = d[u] + (u - i) / v;
                        pq.push({d[i], i});
                    }
                    if (v < block)
                    {
                        if (ck[i][v] == true)
                        {
                            break;
                        }
                        ck[i][v] = true;
                    }
                }
            }
        }
    }
    if (d[endd] == INT_MAX)
    {
        cout << -1;
        return;
    }
    else
    {
        cout << d[endd];
    }
}

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

    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        cin >> b[i] >> p[i];
        adj[b[i]].push_back(p[i]);
    }
    start = b[0];
    endd = b[1];
    for (int i = 0; i < n; i++)
    {
        sort(adj[i].begin(), adj[i].end());
        adj[i].erase(unique(adj[i].begin(), adj[i].end()), adj[i].end());
    }
    dijskstra();
}

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