# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
735927 | 2023-05-05T03:45:27 Z | Cutebol | Jakarta Skyscrapers (APIO15_skyscraper) | C++17 | 1 ms | 1024 KB |
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; using namespace std; void fopn(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);} #define ordered_set tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> #define Ganyu ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0); #define int long long #define endl "\n" #define ff first #define ss second const int N = 3e4 + 5 ; const int inf = 1e9 ; const int mod = 1e9 + 7 ; int n , m , ans = inf ; int p[N] , d[N] ; vector <pair <int , int> > g[N] ; void djikstra( int s ){ set <pair <int , int> > q ; q.insert({0,s}) ; d[s] = 0 ; while ( !q.empty() ){ int v = q.begin()->ss ; // cout << v << endl ; q.erase(q.begin()) ; for ( auto to : g[v] ){ if ( d[to.ff] > d[v]+to.ss ){ q.erase({d[to.ff],to.ff}) ; d[to.ff] = d[v]+to.ss ; q.insert({d[to.ff],to.ff}) ; } } } } void solve(){ cin >> n >> m ; for ( int i = 0 ; i < n ; i ++ ) d[i] = inf ; for ( int i = 0 ; i < m ; i ++ ){ int x , y ; cin >> x >> p[x] ; for ( int j = x+p[x] ; j < n ; j += p[x] ) g[x].push_back({j,(j-x)/p[x]}) ; for ( int j = x-p[x] ; j >= 0 ; j -= p[x] ) g[x].push_back({j,(x-j)/p[x]}) ; } djikstra(0) ; if ( d[1] == inf ) cout << -1 ; else cout << d[1] ; } signed main(){ // fopn("") ; // Ganyu ; int t = 1 ; // cin >> t ; while ( t -- ) solve() ; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 980 KB | Output is correct |
2 | Correct | 1 ms | 1004 KB | Output is correct |
3 | Incorrect | 1 ms | 980 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 980 KB | Output is correct |
2 | Correct | 1 ms | 1024 KB | Output is correct |
3 | Incorrect | 1 ms | 1012 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 1012 KB | Output is correct |
2 | Correct | 1 ms | 1012 KB | Output is correct |
3 | Incorrect | 1 ms | 980 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 1008 KB | Output is correct |
2 | Correct | 1 ms | 1008 KB | Output is correct |
3 | Incorrect | 1 ms | 980 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 980 KB | Output is correct |
2 | Correct | 1 ms | 1012 KB | Output is correct |
3 | Incorrect | 1 ms | 980 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |