Submission #1110103

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110103		HossamHero7	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	355 ms	262144 KiB

skyscraper

#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
#define endl '\n'
const int N = 3e4 + 5;
const int SQ = 100;
vector<int> adj1[N][SQ];
vector<int> adj11[N][SQ];
vector<pair<int,int>> r_adj1[N];
vector<pair<int,int>> adj2[N];
vector<int> r_adj2[N];
ll dis[N][SQ+1];
void solve(){
    int n,m;
    cin>>n>>m;
    vector<pair<int,int>> d(m);
    for(auto &[i,p] : d) cin>>i>>p;
    vector<vector<int>> dogs(n+1);
    for(int i=0;i<m;i++) dogs[d[i].first].push_back(i);
    for(int i=0;i<n;i++){
        for(int j=1;j<SQ;j++){
            adj1[i][j].push_back(i);
 
            if(i+j<n) adj11[i][j].push_back(i+j) ;
            if(i-j>=0) adj11[i][j].push_back(i-j);
        }
    }
    for(int i=0;i<n;i++){
        for(auto j : dogs[i]){
            if(d[j].second < SQ) r_adj1[i].push_back({d[j].first,d[j].second});
            else r_adj2[i].push_back(j);
        }
    }
    for(int j=0;j<m;j++){
        auto [i,p] = d[j];
        if(p < SQ) continue;
        for(int k=i+p;k<n;k+=p) adj2[j].push_back({k,(k-i)/p});
        for(int k=i-p;k>=0;k-=p) adj2[j].push_back({k,(i-k)/p});
    }
    priority_queue<array<ll,3>,vector<array<ll,3>>,greater<>> q;
    for(int i=0;i<N;i++) for(int j=0;j<=SQ;j++) dis[i][j] = 1e18;
    dis[d[0].first][0] = 0;
    q.push({0,d[0].first,0});
    while(q.size()){
        auto [c,i,p] = q.top();     q.pop();
        if(c > dis[i][p]) continue;
        if(p == 0){
            for(auto [ii,pp] : r_adj1[i]){
                if(c < dis[ii][pp]) {
                    //cout<<"HI"<<endl;
                    q.push({c,ii,pp});
                    dis[ii][pp] = c;
                }
            }
            for(auto j : r_adj2[i]){
                if(c < dis[j][SQ]){
                    q.push({c,j,SQ});
                    dis[j][SQ] = c;
                }
            }
        }
        else if(p < SQ){
            for(auto j : adj1[i][p]){
                if(c < dis[j][0]){
                    //if(i == 0 && p == 2) cout<<j<<endl;
                    q.push({c,j,0});
                    dis[j][0] = c;
                }
            }
            for(auto j : adj11[i][p]){
 
                    //if(t == 1 && i == 4 && p == 1) cout<<"mm"<<endl;
                if(c+1 < dis[j][p]){
 
                    //if(t == 1 && i == 4 && p == 1) cout<<j<<' '<<p<<endl;
                    q.push({c+1,j,p});
                    dis[j][p] = c+1;
                }
            }
        }
        else {
            for(auto [j,cost] : adj2[i]){
                if(c + cost < dis[j][0]){
                    q.push({c+cost,j,0});
                    dis[j][0] = c + cost;
                }
            }
        }
    }
    cout<<(dis[d[1].first][0] == 1e18 ? -1 : dis[d[1].first][0])<<endl;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);      cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'void solve()':
skyscraper.cpp:18:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   18 |     for(auto &[i,p] : d) cin>>i>>p;
      |               ^
skyscraper.cpp:36:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   36 |         auto [i,p] = d[j];
      |              ^
skyscraper.cpp:46:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   46 |         auto [c,i,p] = q.top();     q.pop();
      |              ^
skyscraper.cpp:49:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   49 |             for(auto [ii,pp] : r_adj1[i]){
      |                      ^
skyscraper.cpp:83:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   83 |             for(auto [j,cost] : adj2[i]){
      |                      ^

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