Submission #847185

#	Time	Username	Problem	Language	Result	Execution time	Memory
847185		vjudge1	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	0 / 100	1 ms	2652 KiB

skyscraper

#include <bits/stdc++.h>
#define quan160607 "BoundSeq"
#define fi first
#define se second
#define pii pair<int, int>
#define piii pair<int, pii>
#define pb push_back
using namespace std;
typedef long long ll;
const ll oo = 1e18;
const int inf = 2e9;
const int nmax = 3e4 + 5;
void start()
{
//    freopen(quan160607".inp","r",stdin);
//    freopen(quan160607".out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int n, m;
int b[nmax], a[nmax], p[nmax], pp[nmax];
bool ck[nmax];
vector<int> bp[nmax];
const int block = 150;
int dp[nmax][block + 5];
priority_queue<piii, vector<piii>, greater<piii>> q;

bool minimize(int &a, int b)
{
    if(a > b)
    {
        a = b;
        return true;
    } else return false;
}
void solve_dij()
{
    for(int i = 0; i <= n; i++)
    {
        for(int j = 0; j <= block; j++)
            dp[i][j] = inf;
    }
    dp[0][0] = 0;
    q.push({dp[0][0], {0, 0}}); // dp[u][x], u, x
    // dp[i][0] : đến đỉnh i từ 1 đỉnh khác bằng năng lượng > block
    // dp[i][x] : đến đỉnh i từ 1 đỉnh khác bằng năng lượng x <= block
//    cout << dp[1][0] << "\n";
    piii temp;
    while(!q.empty())
    {
        temp = q.top();
        q.pop();
        int u = temp.se.fi;
        if(temp.fi != dp[u][temp.se.se])
            continue;
        if(ck[u] == false)
        {
            for(auto x : bp[u])
            {
                if(x <= block)
                {
                    if(minimize(dp[u][x], dp[u][temp.se.se]))
                        q.push({dp[u][x], {u, x}});
                }
                else
                {
                    if(minimize(dp[u][0], dp[u][temp.se.se]))
                        q.push({dp[u][0], {u, 0}});
                }
            }
            ck[u] = true;
        }
        if(temp.se.se > 0)
        {
            int x = temp.se.se;
            if(u - x >= 1){
                if(minimize(dp[u - x][x], dp[u][x] + 1))
                    q.push({dp[u - x][x], {u - x, x}});
            }
            if(u + x <= n){
                if(minimize(dp[u + x][x], dp[u][x] + 1))
                    q.push({dp[u + x][x], {u + x, x}});
            }
        }
        else
        {
//            cout << "kaka " << u << "\n";
            for(int x : bp[u])
            {
                if(x > block)
                {
                    for(int i = u + x; i <= n; i += x)
                    {
                        if(minimize(dp[i][0], dp[u][0] + (i - u) / x))
                            q.push({dp[i][0], {i, 0}});
                    }
                    for(int i = u - x; i >= 1; i -= x)
                    {
                        if(minimize(dp[i][0], dp[u][0] + (u - i) / x))
                            q.push({dp[i][0], {i, 0}});
                    }
                }
            }
        }
    }
}
int main()
{
    start();
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        cin >> b[i] >> p[i];
        bp[b[i]].push_back(p[i]);
    }
    solve_dij();
    int ans = inf;
    ans = min(ans, dp[1][0]);
//    for(int j = 0; j <= block; j++)
//    {
//        if(dp[1][j] != inf)
//            cout << j << " " << dp[1][j] << "\n";
//    }
    for(int j = 1; j <= block; j++)
        ans = min(ans, dp[1][j]);
    cout << (ans == inf ? -1 : ans);
//    cout << dp[1][1];
}

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