oj.uz

Submission #1110076

# Submission time Handle Problem Language Result Execution time Memory
1110076 2024-11-08T16:21:16 Z HossamHero7 Jakarta Skyscrapers (APIO15_skyscraper) C++14
22 / 100
 164 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});
                    if(pp >= SQ){
                        cout<<"WA"<<endl;
                        exit(0);
                    }
                    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:92:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   92 |             for(auto [j,cost] : adj2[i]){
      |                      ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 249212 KB Output is correct
2 Correct 127 ms 249152 KB Output is correct
3 Correct 128 ms 249164 KB Output is correct
4 Correct 131 ms 249160 KB Output is correct
5 Correct 146 ms 249160 KB Output is correct
6 Correct 127 ms 249160 KB Output is correct
7 Correct 136 ms 249292 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 249224 KB Output is correct
2 Correct 134 ms 249048 KB Output is correct
3 Correct 129 ms 249160 KB Output is correct
4 Correct 123 ms 249120 KB Output is correct
5 Correct 124 ms 249152 KB Output is correct
6 Correct 138 ms 249156 KB Output is correct
7 Correct 136 ms 249160 KB Output is correct
8 Correct 141 ms 249592 KB Output is correct
9 Correct 141 ms 249676 KB Output is correct
10 Correct 164 ms 252124 KB Output is correct
11 Correct 151 ms 261196 KB Output is correct
12 Correct 145 ms 261192 KB Output is correct
13 Correct 141 ms 261056 KB Output is correct
14 Correct 143 ms 261192 KB Output is correct
15 Correct 152 ms 261192 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 249152 KB Output is correct
2 Correct 141 ms 249168 KB Output is correct
3 Correct 132 ms 249160 KB Output is correct
4 Correct 139 ms 249160 KB Output is correct
5 Correct 136 ms 249160 KB Output is correct
6 Correct 138 ms 249160 KB Output is correct
7 Correct 139 ms 249176 KB Output is correct
8 Correct 135 ms 249420 KB Output is correct
9 Correct 132 ms 249812 KB Output is correct
10 Correct 145 ms 251976 KB Output is correct
11 Correct 149 ms 261192 KB Output is correct
12 Correct 157 ms 261192 KB Output is correct
13 Correct 150 ms 261200 KB Output is correct
14 Correct 151 ms 261108 KB Output is correct
15 Correct 150 ms 261000 KB Output is correct
16 Correct 142 ms 255816 KB Output is correct
17 Runtime error 146 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 144 ms 249160 KB Output is correct
2 Correct 133 ms 248944 KB Output is correct
3 Correct 140 ms 249160 KB Output is correct
4 Correct 148 ms 249160 KB Output is correct
5 Correct 135 ms 249160 KB Output is correct
6 Correct 153 ms 249172 KB Output is correct
7 Correct 138 ms 249172 KB Output is correct
8 Correct 134 ms 249416 KB Output is correct
9 Correct 148 ms 249868 KB Output is correct
10 Correct 135 ms 252232 KB Output is correct
11 Correct 155 ms 261192 KB Output is correct
12 Correct 147 ms 261192 KB Output is correct
13 Correct 144 ms 261192 KB Output is correct
14 Correct 135 ms 261220 KB Output is correct
15 Correct 143 ms 261016 KB Output is correct
16 Correct 148 ms 255816 KB Output is correct
17 Runtime error 134 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 124 ms 249160 KB Output is correct
2 Correct 126 ms 249100 KB Output is correct
3 Correct 134 ms 249160 KB Output is correct
4 Correct 127 ms 249160 KB Output is correct
5 Correct 141 ms 249104 KB Output is correct
6 Correct 142 ms 249204 KB Output is correct
7 Correct 137 ms 249280 KB Output is correct
8 Correct 140 ms 249564 KB Output is correct
9 Correct 140 ms 249932 KB Output is correct
10 Correct 147 ms 252116 KB Output is correct
11 Correct 158 ms 261192 KB Output is correct
12 Correct 149 ms 261192 KB Output is correct
13 Correct 151 ms 261192 KB Output is correct
14 Correct 150 ms 261192 KB Output is correct
15 Correct 148 ms 261200 KB Output is correct
16 Correct 151 ms 255820 KB Output is correct
17 Runtime error 149 ms 262144 KB Execution killed with signal 9
18 Halted 0 ms 0 KB -