oj.uz

Submission #1110002

# Submission time Handle Problem Language Result Execution time Memory
1110002 2024-11-08T12:15:19 Z HossamHero7 Jakarta Skyscrapers (APIO15_skyscraper) C++14
22 / 100
 102 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,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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 249168 KB Output is correct
2 Correct 43 ms 249160 KB Output is correct
3 Correct 47 ms 249168 KB Output is correct
4 Correct 48 ms 249156 KB Output is correct
5 Correct 55 ms 249160 KB Output is correct
6 Correct 62 ms 249144 KB Output is correct
7 Correct 69 ms 249172 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 249160 KB Output is correct
2 Correct 67 ms 249160 KB Output is correct
3 Correct 66 ms 249060 KB Output is correct
4 Correct 71 ms 249224 KB Output is correct
5 Correct 67 ms 249240 KB Output is correct
6 Correct 77 ms 249272 KB Output is correct
7 Correct 72 ms 249128 KB Output is correct
8 Correct 74 ms 249612 KB Output is correct
9 Correct 74 ms 249784 KB Output is correct
10 Correct 78 ms 250440 KB Output is correct
11 Correct 84 ms 250396 KB Output is correct
12 Correct 79 ms 250360 KB Output is correct
13 Correct 83 ms 250336 KB Output is correct
14 Correct 78 ms 250440 KB Output is correct
15 Correct 79 ms 250336 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 249160 KB Output is correct
2 Correct 80 ms 249168 KB Output is correct
3 Correct 78 ms 249160 KB Output is correct
4 Correct 73 ms 249160 KB Output is correct
5 Correct 72 ms 249160 KB Output is correct
6 Correct 75 ms 249160 KB Output is correct
7 Correct 81 ms 249160 KB Output is correct
8 Correct 79 ms 249404 KB Output is correct
9 Correct 83 ms 249672 KB Output is correct
10 Correct 92 ms 250440 KB Output is correct
11 Correct 90 ms 250440 KB Output is correct
12 Correct 84 ms 250440 KB Output is correct
13 Correct 95 ms 250440 KB Output is correct
14 Correct 79 ms 250564 KB Output is correct
15 Correct 86 ms 250580 KB Output is correct
16 Correct 75 ms 252156 KB Output is correct
17 Runtime error 88 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 68 ms 249160 KB Output is correct
2 Correct 65 ms 249160 KB Output is correct
3 Correct 71 ms 249168 KB Output is correct
4 Correct 92 ms 249172 KB Output is correct
5 Correct 80 ms 249160 KB Output is correct
6 Correct 84 ms 249172 KB Output is correct
7 Correct 91 ms 249236 KB Output is correct
8 Correct 91 ms 249416 KB Output is correct
9 Correct 95 ms 249672 KB Output is correct
10 Correct 91 ms 250452 KB Output is correct
11 Correct 86 ms 250440 KB Output is correct
12 Correct 93 ms 250440 KB Output is correct
13 Correct 83 ms 250440 KB Output is correct
14 Correct 90 ms 250448 KB Output is correct
15 Correct 86 ms 250580 KB Output is correct
16 Correct 92 ms 252280 KB Output is correct
17 Runtime error 97 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 76 ms 249180 KB Output is correct
2 Correct 65 ms 249160 KB Output is correct
3 Correct 65 ms 249160 KB Output is correct
4 Correct 75 ms 249176 KB Output is correct
5 Correct 78 ms 249160 KB Output is correct
6 Correct 76 ms 249276 KB Output is correct
7 Correct 69 ms 249416 KB Output is correct
8 Correct 65 ms 249416 KB Output is correct
9 Correct 56 ms 249672 KB Output is correct
10 Correct 69 ms 250440 KB Output is correct
11 Correct 75 ms 250396 KB Output is correct
12 Correct 82 ms 250464 KB Output is correct
13 Correct 80 ms 250444 KB Output is correct
14 Correct 88 ms 250368 KB Output is correct
15 Correct 84 ms 250432 KB Output is correct
16 Correct 91 ms 252112 KB Output is correct
17 Runtime error 102 ms 262144 KB Execution killed with signal 9
18 Halted 0 ms 0 KB -