oj.uz

Submission #1110093

# Submission time Handle Problem Language Result Execution time Memory
1110093 2024-11-08T17:30:15 Z HossamHero7 Jakarta Skyscrapers (APIO15_skyscraper) C++14
10 / 100
 63 ms 145352 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];
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 44 ms 143372 KB Output is correct
2 Correct 41 ms 143368 KB Output is correct
3 Correct 42 ms 143436 KB Output is correct
4 Correct 43 ms 143432 KB Output is correct
5 Correct 43 ms 143412 KB Output is correct
6 Correct 44 ms 143432 KB Output is correct
7 Correct 51 ms 143436 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 143432 KB Output is correct
2 Correct 54 ms 143432 KB Output is correct
3 Correct 63 ms 143432 KB Output is correct
4 Correct 60 ms 143408 KB Output is correct
5 Correct 62 ms 143364 KB Output is correct
6 Correct 60 ms 143440 KB Output is correct
7 Correct 61 ms 143432 KB Output is correct
8 Correct 52 ms 143696 KB Output is correct
9 Correct 54 ms 143696 KB Output is correct
10 Incorrect 58 ms 145236 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 143436 KB Output is correct
2 Correct 53 ms 143432 KB Output is correct
3 Correct 55 ms 143400 KB Output is correct
4 Correct 57 ms 143432 KB Output is correct
5 Correct 53 ms 143432 KB Output is correct
6 Correct 53 ms 143436 KB Output is correct
7 Correct 55 ms 143432 KB Output is correct
8 Correct 54 ms 143684 KB Output is correct
9 Correct 57 ms 143952 KB Output is correct
10 Incorrect 58 ms 145232 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 143432 KB Output is correct
2 Correct 40 ms 143436 KB Output is correct
3 Correct 44 ms 143340 KB Output is correct
4 Correct 49 ms 143432 KB Output is correct
5 Correct 51 ms 143364 KB Output is correct
6 Correct 52 ms 143432 KB Output is correct
7 Correct 54 ms 143524 KB Output is correct
8 Correct 60 ms 143516 KB Output is correct
9 Correct 63 ms 143944 KB Output is correct
10 Incorrect 59 ms 145224 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 143432 KB Output is correct
2 Correct 56 ms 143436 KB Output is correct
3 Correct 54 ms 143436 KB Output is correct
4 Correct 54 ms 143436 KB Output is correct
5 Correct 56 ms 143368 KB Output is correct
6 Correct 58 ms 143432 KB Output is correct
7 Correct 51 ms 143520 KB Output is correct
8 Correct 59 ms 143724 KB Output is correct
9 Correct 58 ms 143928 KB Output is correct
10 Incorrect 53 ms 145352 KB Output isn't correct
11 Halted 0 ms 0 KB -