oj.uz

Submission #250404

# Submission time Handle Problem Language Result Execution time Memory
250404 2020-07-17T17:43:45 Z aloo123 Jakarta Skyscrapers (APIO15_skyscraper) C++14
0 / 100
 4 ms 5120 KB 
        #include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <ratio>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <climits>
#define ll long long
#define ld long double
#define mp make_pair
#define pb push_back
#define in insert
#define vll vector<ll>
#define endl "\n"
#define pll pair<ll,ll>
#define f first
#define s second
#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
#define int ll
#define sz(x) (ll)x.size()
#define all(x) (x.begin(),x.end())
using namespace std;

 
const ll INF = 1e12;
const ll N =(2e5+5); // TODO : change value as per problem
const ll MOD = 1e9+7;
ll b[N];
ll p[N];
vector<pair<int,int>> adj[N];
map<pll,bool> done;
map<pll,bool> there;
ll dis[N];
void solve(){
    ll n,m;
    cin >> n >> m;
    for(int i =1;i<=m;i++){
        cin >> b[i] >> p[i];
        b[i]++;
        there[{b[i],p[i]}] = true;
    }
    // path b/w 1 and 2
    for(int i =1;i<=m;i++){
        if(done[mp(b[i],p[i])]){
            continue;
         }
        for(int j = 1;(b[i] + p[i]*j) <= n;j++){
            adj[b[i]].pb({b[i]+p[i]*j,j});
            if(there[mp(b[i]+p[i]*j,p[i])]) break;
        }
        for(int j = 1;(b[i] - p[i]*j) >= 1;j++){
            adj[b[i]].pb({b[i]-p[i]*j,j});
            if(there[mp(b[i]-p[i]*j,p[i])]) break;
        }
        done[mp(b[i],p[i])] = true;
    }
    for(int i =1;i<=n;i++) dis[i] = INF;
    dis[1] = 0;
    priority_queue<pll,vector<pll>,greater<pll>> pq;
    pq.push({0,1});
    while(!pq.empty()){
        pll P = pq.top();
        pq.pop();
        for(auto v:adj[P.s]){
            if(dis[v.f] > dis[P.s] + v.s){
                dis[v.f] = dis[P.s] + v.s;
                pq.push({dis[v.f],v.f});
            }
        }
    }
    if(dis[2] == INF) dis[2] = -1;
    cout << dis[2] << endl;

}   
signed main(){
 
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
     // freopen(".in","r",stdin);freopen(".out","w",stdout);
    
     ll tt=1;   
     // cin >> tt;
    while(tt--){    
        solve();
    }    
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4992 KB Output is correct
2 Correct 3 ms 4992 KB Output is correct
3 Incorrect 3 ms 4992 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4992 KB Output is correct
2 Correct 3 ms 4992 KB Output is correct
3 Incorrect 3 ms 4992 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5120 KB Output is correct
2 Correct 3 ms 4992 KB Output is correct
3 Incorrect 4 ms 4992 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4992 KB Output is correct
2 Correct 4 ms 4992 KB Output is correct
3 Incorrect 3 ms 4992 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4992 KB Output is correct
2 Correct 4 ms 4992 KB Output is correct
3 Incorrect 4 ms 4992 KB Output isn't correct
4 Halted 0 ms 0 KB -