제출 #823470

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
823470		lprochniak	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	0 / 100	66 ms	122932 KiB

skyscraper

//https://oj.uz/problem/view/APIO15_skyscraper
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define st first
#define nd second
#define pii pair<int,int>
int n,m;
int root;
//position / power
struct E{
    int pos;
    int pow;
    int waga;
};
struct Node{
    int d;
    int pos;
    int pow;
};
class comp{
    public:
        bool operator()(Node A,Node B){
            return A.d<B.d;
        }
};
vector<E> edges[30009][174];
int dis[30009][174];
void build(){
    for(int i=0;i<n;i++){
        for(int j=1;j<=root;j++){
            edges[i][j].pb({i,0,0});
        }
    }
}
void addsmaller(int pos,int pow){
    int pos2 = pos;
    while(pos2+pow<n){
        edges[pos2][pow].pb({pos2+pow,pow,1});
        pos2 += pow;
    }
    pos2 = pos;
    while(pos2-pow>=0){
        edges[pos2][pow].pb({pos2-pow,pow,1});
        pos2 -= pow;
    }
}
void addbigger(int pos,int pow){
    int pos2 = pos;
    int dl = 1;
    while(pos2+pow<n){
        edges[pos][pow].pb({pos2+pow,0,dl});
        pos2 += pow;
        dl++;
    }
    pos2 = pos;
    dl = 1;
    while(pos2-pow>=0){
        edges[pos][pow].pb({pos2-pow,0,dl});
        pos2 -= pow;
        dl++;
    }
}
void dijkstra(pii pocz){
    priority_queue<Node,vector<Node>,comp> q;
    q.push({0,pocz.st,pocz.nd});
    while(!q.empty()){
        auto t = q.top();
        q.pop();
        t.d = -t.d;
        if(dis[t.pos][t.pow] != t.d)
            continue;
        for(auto x:edges[t.pos][t.pow]){
            if(t.d + x.waga < dis[x.pos][x.pow]){
                dis[x.pos][x.pow] = t.d + x.waga;
                q.push({-dis[x.pos][x.pow],x.pos,x.pow});
            }
        }
    }
}
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m;
    root = (int)sqrt(n);
    build();
    pii zero,one;
    for(int i=0;i<m;i++){
        int pos,pow;
        cin>>pos>>pow;
        edges[pos][0].pb({pos,pow,0});
        if(pow <= root){
            addsmaller(pos,pow);
        } else{
            addbigger(pos,pow);
        }
        if(i>1) continue;

        if(i == 0){
            zero = {pos,pow};
        } else if(i == 1){
            one = {pos,pow};
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<=root;j++){
            dis[i][j] = 1000000000;
        }
    }
    dis[zero.st][zero.nd] = 0;
    dijkstra(zero);
    
    /*for(int i=0;i<n;i++){
        for(int j=0;j<=n;j++){
            cout<<"pos: "<<i<<" pow: "<<j<<endl;
            for(auto x:edges[i][j]){
                cout<<"pos: "<<x.pos<<" pow: "<<x.pow<<" waga: "<<x.waga<<endl;
            }
        }
    }*/
    if(dis[one.st][one.nd] == 1000000000){
        cout<<"-1\n";
    } else cout<<dis[one.st][one.nd]<<endl;
    return 0;
}

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