oj.uz

Submission #1109992

# Submission time Handle Problem Language Result Execution time Memory
1109992 2024-11-08T11:32:19 Z HossamHero7 Jakarta Skyscrapers (APIO15_skyscraper) C++14
0 / 100
 271 ms 262144 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define endl '\n'
const int N = 3e4 + 5;
const int SQ = 175;
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];
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,4>,vector<array<ll,4>>,greater<>> q;
    vector<vector<vector<ll>>> dis(3,vector<vector<ll>>(n,vector<ll>(SQ,1e18)));
    dis[0][d[0].first][0] = 0;
    q.push({0,d[0].first,0});
    while(q.size()){
        auto [c,t,i,p] = q.top();     q.pop();
        assert(i < n);
        if(c > dis[t][i][p]) continue;
        if(t == 0){
            for(auto [ii,pp] : r_adj1[i]){
                if(c < dis[1][ii][pp]) {
                    //cout<<"HI"<<endl;
                    q.push({c,1,ii,pp});
                    dis[1][ii][pp] = c;
                }
            }/*
            for(auto j : r_adj2[i]){
                if(c < dis[2][j][0]){
                    q.push({c,2,j,0});
                    dis[2][j][0] = c;
                }
            }*/
        }
        else if(t == 1){

                    //if(t == 1 && i == 4 && p == 1) cout<<"WOW"<<endl;
            for(auto j : adj1[i][p]){
                if(c < dis[0][j][0]){
                    //if(i == 0 && p == 2) cout<<j<<endl;
                    q.push({c,0,j,0});
                    dis[0][j][0] = c;
                }
            }
            for(auto j : adj11[i][p]){

                    //if(t == 1 && i == 4 && p == 1) cout<<"mm"<<endl;
                if(c+1 < dis[1][j][p]){

                    //if(t == 1 && i == 4 && p == 1) cout<<j<<' '<<p<<endl;
                    q.push({c+1,1,j,p});
                    dis[1][j][p] = c+1;
                }
            }
        }
        else {
            for(auto [j,cost] : adj2[i]){
                if(c + cost < dis[0][j][0]){
                    q.push({c+cost,0,j,0});
                    dis[0][j][0] = c + cost;
                }
            }
        }
    }
    cout<<(dis[0][d[1].first][0] == 1e18 ? -1 : dis[0][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:17:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   17 |     for(auto &[i,p] : d) cin>>i>>p;
      |               ^
skyscraper.cpp:35:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   35 |         auto [i,p] = d[j];
      |              ^
skyscraper.cpp:45:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   45 |         auto [c,t,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:85:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   85 |             for(auto [j,cost] : adj2[i]){
      |                      ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 249160 KB Output is correct
2 Correct 114 ms 249032 KB Output is correct
3 Correct 119 ms 249124 KB Output is correct
4 Runtime error 244 ms 262144 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 249160 KB Output is correct
2 Correct 121 ms 249172 KB Output is correct
3 Correct 118 ms 249064 KB Output is correct
4 Runtime error 248 ms 262144 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 249160 KB Output is correct
2 Correct 118 ms 249124 KB Output is correct
3 Correct 123 ms 249160 KB Output is correct
4 Runtime error 197 ms 262144 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 249172 KB Output is correct
2 Correct 141 ms 248968 KB Output is correct
3 Correct 125 ms 249160 KB Output is correct
4 Runtime error 271 ms 262144 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 249316 KB Output is correct
2 Correct 133 ms 249124 KB Output is correct
3 Correct 132 ms 249160 KB Output is correct
4 Runtime error 248 ms 262144 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -