제출 #1019157

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1019157		amine_aroua	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	1004 ms	29124 KiB

skyscraper

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
using namespace std;
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n , m;
    cin>>n>>m;
    int sz = (int)sqrt(n);
    vector<vector<int>> p(n);
    vector<vector<int>> dist(n , vector<int>(sz +1 , INT32_MAX));
    vector<vector<bool>> vis(n , vector<bool>(sz + 1 , 0));
    priority_queue<tuple<int ,int , int>, vector<tuple<int ,int , int>> , greater<tuple<int,int ,int>>> q;
    int trg = 0;
    for(int i = 0 ; i < m; i++)
    {
        int a , b;
        cin>>a>>b;
        if(i == 0)
        {
            dist[a][0] = 0;
            q.push({0 , a , 0});
        }
        if(i == 1)
        {
            trg = a;
        }
        p[a].push_back(b);
    }
    while(!q.empty())
    {
        auto [d , tp , last] = q.top();
        q.pop();
        if(vis[tp][last])
            continue;
        vis[tp][last] = 1;
        vector<int> all = p[tp];
        all.push_back(last);
        for(auto P : all)
        {
            if(P == 0)
                continue;
            if(P > sz)
            {
                for(int k = 1 ; tp + k * P < n ; k++)
                {
                    if(dist[k * P + tp][0] > dist[tp][last] + k)
                    {
                        dist[k * P + tp][0] = dist[tp][last] + k;
                        q.push({dist[k * P + tp][0] , k * P + tp , 0});
                    }
                }
                for(int k = 1 ; tp - k * P >= 0 ; k++)
                {
                    if(dist[tp - k * P][0] > dist[tp][last] + k)
                    {
                        dist[tp - k * P][0] = dist[tp][last] + k;
                        q.push({dist[tp - k * P][0] , tp - k * P , 0});
                    }
                }
            }
            else
            {
                if(P + tp < n)
                {
                    if(dist[P + tp][P] > dist[tp][last] + 1)
                    {
                        dist[P + tp][P] = dist[tp][last] + 1;
                        q.push({dist[P + tp][P] , P + tp , P});
                    }
                }
                if(tp - P >= 0)
                {
                    if(dist[tp - P][P] > dist[tp][last] + 1)
                    {
                        dist[tp - P][P] = dist[tp][last] + 1;
                        q.push({dist[tp - P][P] , tp - P , P});
                    }
                }
            }
        }
    }
    int mn = INT32_MAX;
    for(int i = 0 ; i <= sz ; i++)
    {
        mn = min(mn , dist[trg][i]);
    }
    cout<<(mn == INT32_MAX ? -1 : mn);
}

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