Submission #1348655

#	Time	Username	Problem	Language	Result	Execution time	Memory
1348655		truongthaiduonglaptrinh	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	100 / 100	604 ms	25956 KiB

skyscraper

// duonglaptrinh

# include <bits/stdc++.h>

# define paa pair<pair<int, int>, int>
# define fi first
# define se second

using namespace std;

const int N = 3e4+4;

int n, m;
int s, t;
vector<int> way[N];

int dp[N][201];
priority_queue<paa, vector<paa>, greater<>> q;

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

    if(fopen("nhap.inp", "r")) {
        freopen("nhap.inp", "r", stdin);
        freopen("nhap.out", "w", stdout);
    }

    memset(dp, -1, sizeof(dp));

    cin>>n>>m;
    for(int i = 0; i < m; i++) {
        int u, p;
        cin>>u>>p;
        way[u].push_back(p);
        if(i == 0) {
            s = u;
        }
        else if(i == 1) {
            t = u;
        }
    }

    dp[s][0] = 0;

    q.push({{0, 0}, s});

    while(!q.empty()) {
        paa x = q.top();
        q.pop();
        int w = x.fi.fi, d = x.fi.se, u = x.se;
        if(d == 0) {
            for(int x : way[u]) {
                if(x > 200) {
                    for(int i = 1; u + i * x < n; i++) {
                        int v = u + i * x;
                        if(dp[v][0] == -1 || dp[v][0] > dp[u][0] + i) {
                            dp[v][0] = dp[u][0] + i;
                            q.push({{dp[v][0], 0}, v});
                        }
                    }
                    for(int i = 1; u - i * x >= 0; i++) {
                        int v = u - i * x;
                        if(dp[v][0] == -1 || dp[v][0] > dp[u][0] + i) {
                            dp[v][0] = dp[u][0] + i;
                            q.push({{dp[v][0], 0}, v});
                        }
                    }
                }
                else {
                    if(u + x < n && (dp[u + x][x] == -1 || dp[u + x][x] > dp[u][0] + 1)) {
                        dp[u + x][x] = dp[u][0] + 1;
                        q.push({{dp[u + x][x], x}, u + x});
                    }
                    if(u - x >= 0 && (dp[u - x][x] == -1 || dp[u - x][x] > dp[u][0] + 1)) {
                        dp[u - x][x] = dp[u][0] + 1;
                        q.push({{dp[u - x][x], x}, u - x});
                    }
                }
            }
        }
        else {
            if(u + d < n && (dp[u + d][d] == -1 || dp[u + d][d] > dp[u][d] + 1)) {
                dp[u + d][d] = dp[u][d] + 1;
                q.push({{dp[u + d][d], d}, u + d});
            }
            if(u - d >= 0 && (dp[u - d][d] == -1 || dp[u - d][d] > dp[u][d] + 1)) {
                dp[u - d][d] = dp[u][d] + 1;
                q.push({{dp[u - d][d], d}, u - d});
            }
            if(dp[u][0] == -1 || dp[u][0] > dp[u][d]) {
                dp[u][0] = dp[u][d];
                q.push({{dp[u][0], 0}, u});
            }
        }
    }

    cout<<dp[t][0];

    return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:26:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |         freopen("nhap.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:27:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |         freopen("nhap.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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