oj.uz

Submission #1110062

# Submission time Handle Problem Language Result Execution time Memory
1110062 2024-11-08T15:35:22 Z HossamHero7 Jakarta Skyscrapers (APIO15_skyscraper) C++14
22 / 100
 146 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 < 3 && i < n && p < SQ)){
            cout<<"WA"<<endl;
            exit(0);
        }
        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:52:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   52 |             for(auto [ii,pp] : r_adj1[i]){
      |                      ^
skyscraper.cpp:88:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   88 |             for(auto [j,cost] : adj2[i]){
      |                      ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 249160 KB Output is correct
2 Correct 99 ms 249160 KB Output is correct
3 Correct 100 ms 249160 KB Output is correct
4 Correct 99 ms 249416 KB Output is correct
5 Correct 99 ms 249160 KB Output is correct
6 Correct 101 ms 249160 KB Output is correct
7 Correct 101 ms 249128 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 249048 KB Output is correct
2 Correct 107 ms 249396 KB Output is correct
3 Correct 113 ms 249160 KB Output is correct
4 Correct 112 ms 249192 KB Output is correct
5 Correct 102 ms 249232 KB Output is correct
6 Correct 100 ms 249160 KB Output is correct
7 Correct 103 ms 249160 KB Output is correct
8 Correct 96 ms 249416 KB Output is correct
9 Correct 103 ms 249812 KB Output is correct
10 Correct 106 ms 252236 KB Output is correct
11 Correct 104 ms 261192 KB Output is correct
12 Correct 119 ms 261192 KB Output is correct
13 Correct 116 ms 261016 KB Output is correct
14 Correct 118 ms 261192 KB Output is correct
15 Correct 119 ms 261192 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 249160 KB Output is correct
2 Correct 116 ms 249160 KB Output is correct
3 Correct 108 ms 249160 KB Output is correct
4 Correct 114 ms 249160 KB Output is correct
5 Correct 113 ms 249268 KB Output is correct
6 Correct 109 ms 249140 KB Output is correct
7 Correct 117 ms 249160 KB Output is correct
8 Correct 111 ms 249528 KB Output is correct
9 Correct 118 ms 249672 KB Output is correct
10 Correct 112 ms 252232 KB Output is correct
11 Correct 119 ms 261172 KB Output is correct
12 Correct 120 ms 261060 KB Output is correct
13 Correct 120 ms 261124 KB Output is correct
14 Correct 146 ms 261056 KB Output is correct
15 Correct 117 ms 261192 KB Output is correct
16 Correct 114 ms 255832 KB Output is correct
17 Runtime error 123 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 106 ms 249076 KB Output is correct
2 Correct 112 ms 249104 KB Output is correct
3 Correct 108 ms 249104 KB Output is correct
4 Correct 108 ms 249056 KB Output is correct
5 Correct 115 ms 249212 KB Output is correct
6 Correct 100 ms 249084 KB Output is correct
7 Correct 115 ms 249160 KB Output is correct
8 Correct 113 ms 249416 KB Output is correct
9 Correct 115 ms 249672 KB Output is correct
10 Correct 114 ms 252236 KB Output is correct
11 Correct 120 ms 261192 KB Output is correct
12 Correct 109 ms 261192 KB Output is correct
13 Correct 114 ms 261192 KB Output is correct
14 Correct 136 ms 261196 KB Output is correct
15 Correct 132 ms 261192 KB Output is correct
16 Correct 121 ms 255816 KB Output is correct
17 Runtime error 114 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 104 ms 249212 KB Output is correct
2 Correct 111 ms 249160 KB Output is correct
3 Correct 115 ms 249164 KB Output is correct
4 Correct 105 ms 249160 KB Output is correct
5 Correct 107 ms 249160 KB Output is correct
6 Correct 98 ms 249160 KB Output is correct
7 Correct 100 ms 249036 KB Output is correct
8 Correct 112 ms 249592 KB Output is correct
9 Correct 104 ms 249672 KB Output is correct
10 Correct 108 ms 252240 KB Output is correct
11 Correct 109 ms 261112 KB Output is correct
12 Correct 114 ms 261204 KB Output is correct
13 Correct 114 ms 261192 KB Output is correct
14 Correct 116 ms 261132 KB Output is correct
15 Correct 110 ms 261192 KB Output is correct
16 Correct 116 ms 255816 KB Output is correct
17 Runtime error 117 ms 262144 KB Execution killed with signal 9
18 Halted 0 ms 0 KB -