Submission #1257769

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257769		erfankaviani	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	0 / 100	135 ms	247104 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define X       first
#define Y       second
#define endl    '\n'

const int MAXN = 3e4 + 10;
const int MOD = 1e9 + 7;
const ll INF = 2e18;
const int LOG = 22;
const int SQ = 300;

int n , m , B[MAXN] , P[MAXN] , dist[MAXN * SQ];
vector<pii> adj[MAXN * SQ];
map<pii , int> mark , ind;
deque<int> q;

void BFS(int v){
    for(int i = 0; i < MAXN * SQ; i++){
        dist[i] = MOD;
    }
    dist[v] = 0;
    q.push_back(v);
    while(q.size() > 0){
        int v = q.front();
        q.pop_front();
        for(auto i : adj[v]){
            int u = i.X , w = i.Y;
            if(dist[v] + w >= dist[u]){
                continue;
            }
            dist[u] = dist[v] + w;
            if(w == 0){
                q.push_front(u);
            }
            else{
                q.push_back(u);
            }
        }
    }
}

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

    cin >> n >> m;
    vector<pii> vec;
    for(int i = 0; i < m; i++){
        cin >> B[i] >> P[i];
        if(mark[pii(P[i] , B[i])] == 0){
            for(int j = B[i]; j < n; j += P[i]){
                vec.push_back({P[i] , j});
                mark[pii(P[i] , j)] = 1;
            }
            for(int j = B[i] - P[i]; j >= 0; j -= P[i]){
                vec.push_back({P[i] , j});
                mark[pii(P[i] , j)] = 1;
            }
        }
    }
    sort(vec.begin() , vec.end());
    for(int i = 0; i < vec.size(); i++){
        ind[pii(vec[i].X , vec[i].Y)] = i + n;
    }
    for(int i = 0; i < m; i++){
        adj[B[i]].push_back({ind[pii(P[i] , B[i])] , 0});
    }
    for(int i = 0; i < vec.size(); i++){
        int x = vec[i].X , y = vec[i].Y;
        if(y + x < n){
            adj[i + n].push_back({ind[pii(x , y + x)] , 1});
        }
        if(y - x >= 0){
            adj[i + n].push_back({ind[pii(x , y - x)] , 1});
        }
        adj[i + n].push_back({y , 0});
    }
    BFS(ind[pii(P[0] , B[0])]);
    cout << dist[B[1]] << endl;

    return 0;
}

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