oj.uz

Submission #1110049

# Submission time Handle Problem Language Result Execution time Memory
1110049 2024-11-08T14:41:21 Z HossamHero7 Jakarta Skyscrapers (APIO15_skyscraper) C++14
22 / 100
 130 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>>(max(n,m),vector<ll>(SQ,1e18)));
    dis[0][d[0].first][0] = 0;
    q.push({0,0,d[0].first,0});
    while(q.size()){
        auto [c,t,i,p] = q.top();     q.pop();
        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:48:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   48 |             for(auto [ii,pp] : r_adj1[i]){
      |                      ^
skyscraper.cpp:84:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   84 |             for(auto [j,cost] : adj2[i]){
      |                      ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 249160 KB Output is correct
2 Correct 89 ms 249160 KB Output is correct
3 Correct 93 ms 249168 KB Output is correct
4 Correct 97 ms 249160 KB Output is correct
5 Correct 92 ms 249160 KB Output is correct
6 Correct 105 ms 249224 KB Output is correct
7 Correct 102 ms 249136 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 249132 KB Output is correct
2 Correct 97 ms 248940 KB Output is correct
3 Correct 109 ms 249108 KB Output is correct
4 Correct 103 ms 249112 KB Output is correct
5 Correct 99 ms 249092 KB Output is correct
6 Correct 114 ms 249140 KB Output is correct
7 Correct 114 ms 249128 KB Output is correct
8 Correct 103 ms 249416 KB Output is correct
9 Correct 106 ms 249672 KB Output is correct
10 Correct 115 ms 252208 KB Output is correct
11 Correct 112 ms 260992 KB Output is correct
12 Correct 130 ms 261196 KB Output is correct
13 Correct 106 ms 261060 KB Output is correct
14 Correct 117 ms 261016 KB Output is correct
15 Correct 107 ms 261192 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 249160 KB Output is correct
2 Correct 98 ms 249160 KB Output is correct
3 Correct 96 ms 249168 KB Output is correct
4 Correct 100 ms 249196 KB Output is correct
5 Correct 114 ms 249240 KB Output is correct
6 Correct 107 ms 249080 KB Output is correct
7 Correct 108 ms 249172 KB Output is correct
8 Correct 105 ms 249436 KB Output is correct
9 Correct 105 ms 249668 KB Output is correct
10 Correct 106 ms 252232 KB Output is correct
11 Correct 106 ms 261104 KB Output is correct
12 Correct 106 ms 261192 KB Output is correct
13 Correct 111 ms 261184 KB Output is correct
14 Correct 118 ms 261192 KB Output is correct
15 Correct 116 ms 261204 KB Output is correct
16 Correct 108 ms 255816 KB Output is correct
17 Runtime error 117 ms 262144 KB Execution killed with signal 9
18 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 249012 KB Output is correct
2 Correct 111 ms 249160 KB Output is correct
3 Correct 107 ms 249196 KB Output is correct
4 Correct 107 ms 249160 KB Output is correct
5 Correct 105 ms 249300 KB Output is correct
6 Correct 99 ms 249256 KB Output is correct
7 Correct 97 ms 249164 KB Output is correct
8 Correct 96 ms 249416 KB Output is correct
9 Correct 104 ms 249728 KB Output is correct
10 Correct 101 ms 251976 KB Output is correct
11 Correct 113 ms 261204 KB Output is correct
12 Correct 114 ms 261192 KB Output is correct
13 Correct 117 ms 261064 KB Output is correct
14 Correct 109 ms 261012 KB Output is correct
15 Correct 119 ms 261116 KB Output is correct
16 Correct 103 ms 255816 KB Output is correct
17 Runtime error 112 ms 262144 KB Execution killed with signal 9
18 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 249160 KB Output is correct
2 Correct 95 ms 249156 KB Output is correct
3 Correct 93 ms 249208 KB Output is correct
4 Correct 93 ms 249156 KB Output is correct
5 Correct 106 ms 249088 KB Output is correct
6 Correct 114 ms 249108 KB Output is correct
7 Correct 101 ms 249160 KB Output is correct
8 Correct 97 ms 249416 KB Output is correct
9 Correct 104 ms 249680 KB Output is correct
10 Correct 100 ms 252072 KB Output is correct
11 Correct 120 ms 261192 KB Output is correct
12 Correct 117 ms 261192 KB Output is correct
13 Correct 107 ms 261192 KB Output is correct
14 Correct 111 ms 261192 KB Output is correct
15 Correct 107 ms 261192 KB Output is correct
16 Correct 107 ms 255816 KB Output is correct
17 Runtime error 104 ms 262144 KB Execution killed with signal 9
18 Halted 0 ms 0 KB -