oj.uz

Submission #1110094

# Submission time Handle Problem Language Result Execution time Memory
1110094 2024-11-08T17:31:21 Z HossamHero7 Jakarta Skyscrapers (APIO15_skyscraper) C++14
57 / 100
 218 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 = 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 == 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 45 ms 143432 KB Output is correct
2 Correct 46 ms 143356 KB Output is correct
3 Correct 60 ms 143432 KB Output is correct
4 Correct 52 ms 143444 KB Output is correct
5 Correct 53 ms 143360 KB Output is correct
6 Correct 58 ms 143540 KB Output is correct
7 Correct 56 ms 143428 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 143432 KB Output is correct
2 Correct 61 ms 143404 KB Output is correct
3 Correct 60 ms 143432 KB Output is correct
4 Correct 52 ms 143316 KB Output is correct
5 Correct 59 ms 143340 KB Output is correct
6 Correct 57 ms 143452 KB Output is correct
7 Correct 61 ms 143328 KB Output is correct
8 Correct 55 ms 143688 KB Output is correct
9 Correct 52 ms 143952 KB Output is correct
10 Correct 56 ms 145224 KB Output is correct
11 Correct 61 ms 150600 KB Output is correct
12 Correct 62 ms 150556 KB Output is correct
13 Correct 61 ms 150516 KB Output is correct
14 Correct 67 ms 150600 KB Output is correct
15 Correct 66 ms 150516 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 143432 KB Output is correct
2 Correct 56 ms 143432 KB Output is correct
3 Correct 60 ms 143432 KB Output is correct
4 Correct 55 ms 143436 KB Output is correct
5 Correct 56 ms 143440 KB Output is correct
6 Correct 57 ms 143432 KB Output is correct
7 Correct 58 ms 143432 KB Output is correct
8 Correct 55 ms 143688 KB Output is correct
9 Correct 55 ms 143824 KB Output is correct
10 Correct 62 ms 145212 KB Output is correct
11 Correct 69 ms 150600 KB Output is correct
12 Correct 65 ms 150540 KB Output is correct
13 Correct 59 ms 150612 KB Output is correct
14 Correct 66 ms 150600 KB Output is correct
15 Correct 65 ms 150600 KB Output is correct
16 Correct 60 ms 147528 KB Output is correct
17 Correct 76 ms 153980 KB Output is correct
18 Correct 81 ms 160020 KB Output is correct
19 Correct 89 ms 162340 KB Output is correct
20 Correct 89 ms 162632 KB Output is correct
21 Correct 62 ms 149832 KB Output is correct
22 Correct 87 ms 160332 KB Output is correct
23 Correct 85 ms 158664 KB Output is correct
24 Correct 86 ms 161668 KB Output is correct
25 Correct 88 ms 162604 KB Output is correct
26 Correct 88 ms 162432 KB Output is correct
27 Correct 81 ms 162572 KB Output is correct
28 Correct 94 ms 162588 KB Output is correct
29 Correct 109 ms 162632 KB Output is correct
30 Correct 88 ms 162384 KB Output is correct
31 Correct 90 ms 162516 KB Output is correct
32 Correct 94 ms 162376 KB Output is correct
33 Correct 102 ms 162376 KB Output is correct
34 Correct 100 ms 162448 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 143304 KB Output is correct
2 Correct 59 ms 143316 KB Output is correct
3 Correct 61 ms 143376 KB Output is correct
4 Correct 59 ms 143436 KB Output is correct
5 Correct 62 ms 143432 KB Output is correct
6 Correct 63 ms 143432 KB Output is correct
7 Correct 69 ms 143432 KB Output is correct
8 Correct 66 ms 143688 KB Output is correct
9 Correct 63 ms 143824 KB Output is correct
10 Correct 61 ms 145200 KB Output is correct
11 Correct 67 ms 150600 KB Output is correct
12 Correct 63 ms 150604 KB Output is correct
13 Correct 65 ms 150600 KB Output is correct
14 Correct 73 ms 150600 KB Output is correct
15 Correct 67 ms 150600 KB Output is correct
16 Correct 64 ms 147488 KB Output is correct
17 Correct 84 ms 153992 KB Output is correct
18 Correct 86 ms 160040 KB Output is correct
19 Correct 91 ms 162384 KB Output is correct
20 Correct 97 ms 162632 KB Output is correct
21 Correct 66 ms 149576 KB Output is correct
22 Correct 79 ms 160328 KB Output is correct
23 Correct 83 ms 158536 KB Output is correct
24 Correct 86 ms 161608 KB Output is correct
25 Correct 89 ms 162888 KB Output is correct
26 Correct 99 ms 162376 KB Output is correct
27 Correct 87 ms 162376 KB Output is correct
28 Correct 87 ms 162632 KB Output is correct
29 Correct 93 ms 162364 KB Output is correct
30 Correct 78 ms 162376 KB Output is correct
31 Correct 90 ms 162376 KB Output is correct
32 Correct 99 ms 162444 KB Output is correct
33 Correct 106 ms 162376 KB Output is correct
34 Correct 112 ms 162416 KB Output is correct
35 Correct 182 ms 238272 KB Output is correct
36 Correct 84 ms 165904 KB Output is correct
37 Correct 171 ms 220968 KB Output is correct
38 Correct 197 ms 256328 KB Output is correct
39 Correct 201 ms 256328 KB Output is correct
40 Correct 201 ms 256332 KB Output is correct
41 Correct 194 ms 256420 KB Output is correct
42 Correct 157 ms 255172 KB Output is correct
43 Correct 163 ms 255380 KB Output is correct
44 Correct 158 ms 255432 KB Output is correct
45 Correct 218 ms 258632 KB Output is correct
46 Correct 200 ms 258632 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 143432 KB Output is correct
2 Correct 52 ms 143436 KB Output is correct
3 Correct 56 ms 143480 KB Output is correct
4 Correct 57 ms 143432 KB Output is correct
5 Correct 52 ms 143312 KB Output is correct
6 Correct 52 ms 143432 KB Output is correct
7 Correct 61 ms 143432 KB Output is correct
8 Correct 61 ms 143672 KB Output is correct
9 Correct 66 ms 143824 KB Output is correct
10 Correct 64 ms 145224 KB Output is correct
11 Correct 69 ms 150480 KB Output is correct
12 Correct 68 ms 150520 KB Output is correct
13 Correct 70 ms 150600 KB Output is correct
14 Correct 70 ms 150608 KB Output is correct
15 Correct 73 ms 150628 KB Output is correct
16 Correct 76 ms 147404 KB Output is correct
17 Correct 83 ms 153932 KB Output is correct
18 Correct 90 ms 160144 KB Output is correct
19 Correct 97 ms 162492 KB Output is correct
20 Correct 95 ms 162656 KB Output is correct
21 Correct 77 ms 149628 KB Output is correct
22 Correct 89 ms 160328 KB Output is correct
23 Correct 88 ms 158536 KB Output is correct
24 Correct 93 ms 161608 KB Output is correct
25 Correct 97 ms 162632 KB Output is correct
26 Correct 94 ms 162376 KB Output is correct
27 Correct 102 ms 162648 KB Output is correct
28 Correct 93 ms 162640 KB Output is correct
29 Correct 97 ms 162344 KB Output is correct
30 Correct 92 ms 162496 KB Output is correct
31 Correct 91 ms 162376 KB Output is correct
32 Correct 99 ms 162376 KB Output is correct
33 Correct 111 ms 162376 KB Output is correct
34 Correct 105 ms 162376 KB Output is correct
35 Correct 169 ms 237896 KB Output is correct
36 Correct 91 ms 165960 KB Output is correct
37 Correct 172 ms 220748 KB Output is correct
38 Correct 204 ms 256252 KB Output is correct
39 Correct 206 ms 256324 KB Output is correct
40 Correct 203 ms 256412 KB Output is correct
41 Correct 198 ms 256328 KB Output is correct
42 Correct 167 ms 255172 KB Output is correct
43 Correct 186 ms 255172 KB Output is correct
44 Correct 173 ms 255432 KB Output is correct
45 Correct 207 ms 258636 KB Output is correct
46 Correct 202 ms 258620 KB Output is correct
47 Runtime error 215 ms 262144 KB Execution killed with signal 9
48 Halted 0 ms 0 KB -