제출 #124143

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
124143		youssefbou62	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	36 / 100	1076 ms	3432 KiB

skyscraper

#include  <bits/stdc++.h>

using namespace std;

#define mp make_pair
#define fi first
#define se second
#define all(v) v.begin(),v.end()
#define allarr(a) a , a + n
#define ll long long
#define ull unsigned long long 
#define pb push_back
#define fastio ios_base::sync_with_stdio(false) ; cin.tie(NULL); cout.tie(NULL)
typedef pair<int, int> pi;
typedef pair<ll,ll> pll; 
typedef pair<int,pi> trp ;
typedef vector<pi> vpi;
typedef vector<pll> vpll ;
ll ab (ll x ) { return (x>0?x:-x); }
const int N = 300005 ; 
const ll oo = 1e18 ;  
ll dist [N] ; 
set<int>  dogs;
// int par[N];
ll n , m ;
ll B[N] , P[N] ;  

ll dijkstra(){

priority_queue< pll, vector <pll> , greater<pll> > pq;
pq.push( mp(0,0) ) ;

    for(int i = 1 ; i <= m ; i++ )dist[i] = oo ;

    dist[0] = 0LL ; 
  //  vector<int> choosen ; 
    while ( !pq.empty() ){
        int u = pq.top().se ; 
        ll d = pq.top().fi ;
        pq.pop() ; 
        if(  dogs.find ( u  ) != dogs.end() ) 
        dogs.erase( dogs.find (u) ) ; 
        if( u == 1 )return dist[1] ; 
        if( dist[u] < d )continue ;
        for(int v : dogs ){
            d = dist[u] + ab(B[u]-B[v]) / P[u] ; 
            if(ab(B[u]-B[v])%P[u] == 0LL && dist[v] > d ){
                // cout << u << " " << v << endl;
                dist[v] = d;  
                pq.push( {d ,v} ); 
            }
        }
        
    } return -1 ; 
}

void input(){
    // fastio ; 
    // ifstream cin("in.in") ; 
    cin >> n >> m ; 
    for(int i = 0 ; i < m  ; i++ ){
        cin >> B[i] >> P[i] ; 
        if(i)dogs.insert(i) ;
    }
}

int main(){
    input() ; 
    cout << dijkstra( ) << endl; 
}

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