Submission #695272

#	Time	Username	Problem	Language	Result	Execution time	Memory
695272		3omar_ahmed	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	36 / 100	1085 ms	1876 KiB

skyscraper

/**
 * author: 3omar_ahmed
 * date: 04-02-2023
 * Expert When :)
 */
#include <ext/rope>
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std ;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
template<class x> using ordered_set = tree<x, null_type,less<x>, rb_tree_tag,tree_order_statistics_node_update>;
#define int long long
#define endl '\n'
#define all(a) a.begin() , a.end()
#define alr(a) a.rbegin() , a.rend()
const int N = 2e3 + 5;
int n, m;
vector < int > dis(N, INT_MAX);
vector < set < int > > possible(N);
int aa, bb;
int dij(int from, int to){
    priority_queue<pair < int ,int >> p;
    p.push({0 , from});
    dis[from] = 0;
    while(p.size()){
        auto node = p.top();
        p.pop();
        for(auto child : possible[node.second]){
            bool f1 = 0, f2 = 0;
            for(int i = 1, nod1 = i * child + node.second; ; i++, 
                                    nod1 = i * child + node.second){
                if(nod1 < n && dis[nod1] > node.first + i){
                    dis[nod1] = node.first + i ;
                    p.push({node.first + i, nod1});
                    if(possible[nod1].find(child) != 
                       possible[nod1].end())
                        break;
                } else if(nod1 >= n) break;
            }
            for(int i = 1, nod2 = -i * child + node.second; ; i++, 
                                    nod2 = -i * child + node.second){
                if(!f2 && nod2 >= 0 && dis[nod2] > node.first + i){
                    dis[nod2] = node.first + i ;
                    p.push({node.first + i, nod2});
                    if(possible[nod2].find(child) != 
                       possible[nod2].end())
                        break;
                } else if(nod2 < 0) break;
            }
        }
    }
    return dis[to];
}
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

    cin >> n >> m;
    int from = 0 , to = 1;
    for(int i = 0; i < m; i++){
        int b , p; cin >> b >> p;
        (i == 0? aa = b : (i == 1? bb = b : bb = bb));
        possible[b].insert(p);
    }
    int dist = dij(aa, bb);
    cout << (dist == INT_MAX? -1 : dist);
    return 0 ;
}

Compilation message (stderr)

skyscraper.cpp: In function 'long long int dij(long long int, long long int)':
skyscraper.cpp:31:18: warning: unused variable 'f1' [-Wunused-variable]
   31 |             bool f1 = 0, f2 = 0;
      |                  ^~
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:60:9: warning: unused variable 'from' [-Wunused-variable]
   60 |     int from = 0 , to = 1;
      |         ^~~~
skyscraper.cpp:60:20: warning: unused variable 'to' [-Wunused-variable]
   60 |     int from = 0 , to = 1;
      |                    ^~

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