oj.uz

Submission #1110092

# Submission time Handle Problem Language Result Execution time Memory
1110092 2024-11-08T17:29:25 Z HossamHero7 Jakarta Skyscrapers (APIO15_skyscraper) C++14
0 / 100
 62 ms 167200 KB 
#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;
    memset(dis,'?',sizeof(dis));
    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

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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 166992 KB Output is correct
2 Correct 57 ms 167176 KB Output is correct
3 Correct 52 ms 166984 KB Output is correct
4 Incorrect 50 ms 167200 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 167136 KB Output is correct
2 Correct 57 ms 166984 KB Output is correct
3 Correct 59 ms 167072 KB Output is correct
4 Incorrect 56 ms 167104 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 166984 KB Output is correct
2 Correct 52 ms 167108 KB Output is correct
3 Correct 56 ms 166980 KB Output is correct
4 Incorrect 60 ms 166984 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 167048 KB Output is correct
2 Correct 57 ms 166984 KB Output is correct
3 Correct 59 ms 166984 KB Output is correct
4 Incorrect 59 ms 166984 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 166984 KB Output is correct
2 Correct 58 ms 166984 KB Output is correct
3 Correct 57 ms 166984 KB Output is correct
4 Incorrect 55 ms 166984 KB Output isn't correct
5 Halted 0 ms 0 KB -