Submission #516192

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
516192	2022-01-20T15:10:10 Z	CaoHuuKhuongDuy	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	Compilation error	0 ms	0 KB

skyscraper

// #pragma GCC target("avx2")
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define ll int
#define cll const ll
#define lp(a, b, c) for(ll a = b; a <= c; ++a)
#define lpd(a, b, c) for(ll a = b; a >= c; --a)
#define vec(a) vector<a>
#define pp(a, b) pair<a, b>
#define EACHCASE lpd(cs, read(), 1)
#define Fname "f"
using namespace std;
 
template <typename T> inline void Read(T &x){
    x = 0; char c;
    ll dau = 1;
    while(!isdigit(c = getchar())) if(c == '-') dau = -1;
    do{
        x = x * 10 + c - '0';
    } while (isdigit(c = getchar()));
    x *= dau;
}
 
ll read(){
    ll tmp;
    cin >> tmp;
    return tmp;
}
 
void giuncute(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
}
 
// void OF(){
//     if(fopen(Fname".inp", "r")){
//         freopen(Fname".inp", "r", stdin);
//         freopen(Fname".out", "w", stdout);
//     } else if(fopen(Fname".in", "r")){
//         freopen(Fname".in", "r", stdin);
//         freopen(Fname".out", "w", stdout);
//     }
// }
 
cll mxn = 3e4 + 5, _sqrt = 173;
ll n, m, dp[mxn][_sqrt + 4];
vec(ll) jump[mxn];
priority_queue<pp(ll, pp(ll, ll))> q;
 
void prc(ll u, ll cu, ll step){
    if(u + step < n && dp[u + step][step] > cu + 1){
        dp[u + step][step] = cu + 1;
        q.push({-dp[u + step][step], {u + step, step}});
    } 
    if(u - step >= 0 && dp[u - step][step] > cu + 1){
        dp[u - step][step] = cu + 1;
        q.push({-dp[u - step][step], {u - step, step}});
    } 
 
    // if(u + step < n && dp[u + step][0] > cu + 1){
    //     dp[u + step][0] = cu + 1;
    //     q.push({-dp[u + step][0], {u + step, 0}});
    // } 
    // if(u - step >= 0 && dp[u - step][0] > cu + 1){
    //     dp[u - step][0] = cu + 1;
    //     q.push({-dp[u - step][0], {u - step, 0}});
    // } 
}
bool First[mxn];
int main(){
    giuncute();
    #ifndef ONLINE_JUDGE
  //  OF();
  //freopen("test.inp","r",stdin);
    #endif
    cin >> n >> m;
    lp(i, 1, m){
        static ll u, p;
        cin >> u >> p;
        jump[u].push_back(p);
    }
    if (n==1)
      {
      cout<<-1;
      return 0;
      }
    lp(i, 0, n-1) lp(j, 0, _sqrt) dp[i][j] = 1e9;
    lp(i, 0, _sqrt) dp[a[0]][i] = 0;
    q.push({a[0], {0, 0}});
    while(q.size()){
        ll cu = -q.top().first, u = q.top().second.first, step = q.top().second.second;
        q.pop();
        if(cu != dp[u][step]) continue;
 
        // maintain last step
        prc(u, cu, step);
        // change step
        if (First[u]) continue;
        First[u]=true;
        for(ll i : jump[u]){
            //prc(u,cu-1,i);
            if (dp[u][0]>cu)
                {
                  dp[u][0]=cu;
                  q.push({-dp[u][0],{u,0}});
                }            
            if(i <= _sqrt)
            {
              if (dp[u][i]>cu)
                {
                  dp[u][i]=cu;
                  q.push({-dp[u][i],{u,i}});
                }
              prc(u, cu, i);
            }
            else{
                for(ll v = u + i, cnt = 1; v < n; v += i, ++cnt)
                    if(dp[v][0] > cu + cnt){
                        dp[v][0] = cu + cnt;
                        q.push({-dp[v][0], {v, 0}});
                    }
                for(ll v = u - i, cnt = 1; v >= 0; v -= i, ++cnt)
                    if(dp[v][0] > cu + cnt){
                        dp[v][0] = cu + cnt;
                        q.push({-dp[v][0], {v, 0}});
                    }
            }
        }
    }
    ll ans = 1e9;
    lp(i, 0, _sqrt) ans = min(ans, dp[a[1]][i]);
    if(ans ==1e9) ans = -1;
    cout << ans;
}

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:89:24: error: 'a' was not declared in this scope
   89 |     lp(i, 0, _sqrt) dp[a[0]][i] = 0;
      |                        ^
skyscraper.cpp:90:13: error: 'a' was not declared in this scope
   90 |     q.push({a[0], {0, 0}});
      |             ^
skyscraper.cpp:90:26: error: no matching function for call to 'std::priority_queue<std::pair<int, std::pair<int, int> > >::push(<brace-enclosed initializer list>)'
   90 |     q.push({a[0], {0, 0}});
      |                          ^
In file included from /usr/include/c++/10/queue:64,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:86,
                 from skyscraper.cpp:4:
/usr/include/c++/10/bits/stl_queue.h:640:7: note: candidate: 'void std::priority_queue<_Tp, _Sequence, _Compare>::push(const value_type&) [with _Tp = std::pair<int, std::pair<int, int> >; _Sequence = std::vector<std::pair<int, std::pair<int, int> >, std::allocator<std::pair<int, std::pair<int, int> > > >; _Compare = std::less<std::pair<int, std::pair<int, int> > >; std::priority_queue<_Tp, _Sequence, _Compare>::value_type = std::pair<int, std::pair<int, int> >]'
  640 |       push(const value_type& __x)
      |       ^~~~
/usr/include/c++/10/bits/stl_queue.h:640:30: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const value_type&' {aka 'const std::pair<int, std::pair<int, int> >&'}
  640 |       push(const value_type& __x)
      |            ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_queue.h:648:7: note: candidate: 'void std::priority_queue<_Tp, _Sequence, _Compare>::push(std::priority_queue<_Tp, _Sequence, _Compare>::value_type&&) [with _Tp = std::pair<int, std::pair<int, int> >; _Sequence = std::vector<std::pair<int, std::pair<int, int> >, std::allocator<std::pair<int, std::pair<int, int> > > >; _Compare = std::less<std::pair<int, std::pair<int, int> > >; std::priority_queue<_Tp, _Sequence, _Compare>::value_type = std::pair<int, std::pair<int, int> >]'
  648 |       push(value_type&& __x)
      |       ^~~~
/usr/include/c++/10/bits/stl_queue.h:648:25: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::priority_queue<std::pair<int, std::pair<int, int> > >::value_type&&' {aka 'std::pair<int, std::pair<int, int> >&&'}
  648 |       push(value_type&& __x)
      |            ~~~~~~~~~~~~~^~~