제출 #1016391

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

skyscraper

#include <iostream>
#include <bits/stdc++.h>
#define ll int
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;
const int B = 200;
vector<ll> dijkstra(int n, int s, vector<vector<pair<int, int>>> &adj){
    vector<ll> dist(n+1, INF);
    dist[s] = 0;
    vector<bool> vis(n+1, false);
    priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
    pq.push({0, s});
    while(!pq.empty()){
        ll d_u = pq.top().first;
        int u = pq.top().second;
        pq.pop();
        if(vis[u]){
            continue;
        }
        vis[u] = true;
        for(auto it : adj[u]){
            int v = it.first;
            ll w = it.second;
            if(vis[v]) continue;
            dist[v] = min(dist[v], d_u+w);
            pq.push({dist[v], v});
        }
    }
    return dist;
}
void solve(){
    int n, m;
    cin >> n >> m;
    vector<ll> b(m+1), p(m+1);
    for(int i = 1; i <= m; i++){
        cin >> b[i] >> p[i];
        b[i]++;
    }
    int c = 0;
    vector<vector<int>> cv(n+1, vector<int>(B+1));
    vector<vector<bool>> have_doge(n+1, vector<bool>(B+1, false));
    for(int i = 1; i <= m; i++){
        if(p[i] <= B){
            have_doge[b[i]][p[i]] = true;
        }
    }
    vector<pair<int, int>> dc;
    dc.push_back({-1, -1});
    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= B; j++){
            c++;
            cv[i][j] = c;
            dc.push_back({i, j});
        }
    }
    int nb = c;
    auto valid = [&](int x) -> bool{
        return (x >= 1 && x <= n);
    };
    vector<vector<pair<ll, ll>>> adj(nb+1);
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= B; j++){
            int u, v;
            u = cv[i][0];
            v = cv[i][j];
            if(have_doge[i][j]){
                adj[u].push_back({v, 0});
            }
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= B; j++){
            int u, v;
            if(valid(i+j)){
                u = cv[i][j];
                v = cv[i+j][0];
                adj[u].push_back({v, 1});
                v = cv[i+j][j];
                adj[u].push_back({v, 1});
            }
            if(valid(i-j)){
                u = cv[i][j];
                v = cv[i-j][0];
                adj[u].push_back({v, 1});
                v = cv[i-j][j];
                adj[u].push_back({v, 1});
            }
        }
    }
    for(int i = 1; i <= m; i++){
        int pos, u, v;
        pos = b[i];
        if(p[i] <= B) continue;
        for(int j = -B; j <= B; j++){
            if(valid(pos+j*p[i]) && j != 0){
                u = cv[pos][0];
                v = cv[pos+j*p[i]][0];
                adj[u].push_back({v, abs(j)});
            }
        }
    }
    for(int j = 1; j <= n; j++){
        if(abs(b[1]-j)%p[1] == 0){
            ll w = abs(b[1]-j)/p[1];
            adj[0].push_back({cv[j][0], w});
        }
    }
    int S = 0, T = cv[b[2]][0];
    vector<ll> dist = dijkstra(nb, S, adj);
    ll ans = dist[T];
    if(ans == INF){
        ans = -1;
    }
    cout << ans;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}

컴파일 시 표준 에러 (stderr) 메시지

skyscraper.cpp:5:36: warning: overflow in conversion from 'double' to 'int' changes value from '4.0e+18' to '2147483647' [-Woverflow]
    5 | const ll maxn = 2*1e5+5, INF = 4e18+9;
      |                                ~~~~^~

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