Submission #1016401

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016401		Icelast	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	0 / 100	1 ms	604 KiB

skyscraper

#include <iostream>
#include <bits/stdc++.h>
#define ll int
using namespace std;
const ll maxn = 2*1e5+5, INF = 1e9+9;
const int B = 200;
vector<ll> dijkstra(int n, int s, vector<vector<pair<int, short>>> &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;
    auto cv = [&](int i, int j) -> int{
        return i*(B+1) + j;
    };
    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;
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= B; j++){
            c++;
        }
    }
    int nb = c;
    auto valid = [&](int x) -> bool{
        return (x >= 1 && x <= n);
    };
    vector<vector<pair<int, short>>> 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();
}

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