oj.uz

Submission #1110105

# Submission time Handle Problem Language Result Execution time Memory
1110105 2024-11-08T17:41:56 Z HossamHero7 Jakarta Skyscrapers (APIO15_skyscraper) C++14
57 / 100
 367 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 = 50;
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];
ll dis[3][N][SQ];
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;
    for(int i=0;i<N;i++) for(int j=0;j<SQ;j++) dis[0][i][j] = dis[1][i][j] = dis[2][i][j] = 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:18:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   18 |     for(auto &[i,p] : d) cin>>i>>p;
      |               ^
skyscraper.cpp:36:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   36 |         auto [i,p] = d[j];
      |              ^
skyscraper.cpp:46:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   46 |         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 19 ms 108112 KB Output is correct
2 Correct 19 ms 108112 KB Output is correct
3 Correct 19 ms 108188 KB Output is correct
4 Correct 20 ms 108224 KB Output is correct
5 Correct 19 ms 108112 KB Output is correct
6 Correct 18 ms 108112 KB Output is correct
7 Correct 19 ms 108112 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 108112 KB Output is correct
2 Correct 19 ms 108028 KB Output is correct
3 Correct 19 ms 108112 KB Output is correct
4 Correct 20 ms 108112 KB Output is correct
5 Correct 20 ms 108112 KB Output is correct
6 Correct 21 ms 108244 KB Output is correct
7 Correct 19 ms 108240 KB Output is correct
8 Correct 20 ms 108112 KB Output is correct
9 Correct 20 ms 108368 KB Output is correct
10 Correct 22 ms 108368 KB Output is correct
11 Correct 20 ms 108624 KB Output is correct
12 Correct 22 ms 108624 KB Output is correct
13 Correct 20 ms 108636 KB Output is correct
14 Correct 24 ms 108624 KB Output is correct
15 Correct 27 ms 108616 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 108244 KB Output is correct
2 Correct 25 ms 108112 KB Output is correct
3 Correct 26 ms 108088 KB Output is correct
4 Correct 30 ms 108184 KB Output is correct
5 Correct 26 ms 108112 KB Output is correct
6 Correct 21 ms 108112 KB Output is correct
7 Correct 19 ms 108112 KB Output is correct
8 Correct 19 ms 108124 KB Output is correct
9 Correct 23 ms 108368 KB Output is correct
10 Correct 21 ms 108536 KB Output is correct
11 Correct 29 ms 108624 KB Output is correct
12 Correct 27 ms 108616 KB Output is correct
13 Correct 25 ms 108624 KB Output is correct
14 Correct 29 ms 108624 KB Output is correct
15 Correct 30 ms 108600 KB Output is correct
16 Correct 24 ms 108880 KB Output is correct
17 Correct 33 ms 110800 KB Output is correct
18 Correct 31 ms 113744 KB Output is correct
19 Correct 34 ms 114308 KB Output is correct
20 Correct 29 ms 114504 KB Output is correct
21 Correct 28 ms 109396 KB Output is correct
22 Correct 34 ms 113736 KB Output is correct
23 Correct 32 ms 113232 KB Output is correct
24 Correct 35 ms 114256 KB Output is correct
25 Correct 35 ms 114380 KB Output is correct
26 Correct 33 ms 114512 KB Output is correct
27 Correct 33 ms 114512 KB Output is correct
28 Correct 36 ms 114448 KB Output is correct
29 Correct 53 ms 114504 KB Output is correct
30 Correct 39 ms 114300 KB Output is correct
31 Correct 45 ms 114612 KB Output is correct
32 Correct 37 ms 114504 KB Output is correct
33 Correct 47 ms 115148 KB Output is correct
34 Correct 45 ms 115036 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 108112 KB Output is correct
2 Correct 19 ms 108112 KB Output is correct
3 Correct 20 ms 108112 KB Output is correct
4 Correct 19 ms 108268 KB Output is correct
5 Correct 27 ms 108260 KB Output is correct
6 Correct 29 ms 108180 KB Output is correct
7 Correct 27 ms 108124 KB Output is correct
8 Correct 25 ms 108112 KB Output is correct
9 Correct 22 ms 108368 KB Output is correct
10 Correct 33 ms 108360 KB Output is correct
11 Correct 27 ms 108624 KB Output is correct
12 Correct 24 ms 108624 KB Output is correct
13 Correct 26 ms 108636 KB Output is correct
14 Correct 27 ms 108624 KB Output is correct
15 Correct 29 ms 108616 KB Output is correct
16 Correct 28 ms 108892 KB Output is correct
17 Correct 29 ms 110576 KB Output is correct
18 Correct 35 ms 113736 KB Output is correct
19 Correct 30 ms 114524 KB Output is correct
20 Correct 30 ms 114504 KB Output is correct
21 Correct 30 ms 109488 KB Output is correct
22 Correct 35 ms 113732 KB Output is correct
23 Correct 37 ms 113232 KB Output is correct
24 Correct 41 ms 114268 KB Output is correct
25 Correct 32 ms 114504 KB Output is correct
26 Correct 33 ms 114512 KB Output is correct
27 Correct 31 ms 114504 KB Output is correct
28 Correct 34 ms 114504 KB Output is correct
29 Correct 41 ms 114504 KB Output is correct
30 Correct 35 ms 114256 KB Output is correct
31 Correct 44 ms 114512 KB Output is correct
32 Correct 39 ms 114504 KB Output is correct
33 Correct 55 ms 115156 KB Output is correct
34 Correct 46 ms 115016 KB Output is correct
35 Correct 59 ms 114880 KB Output is correct
36 Correct 35 ms 111952 KB Output is correct
37 Correct 59 ms 117216 KB Output is correct
38 Correct 63 ms 117448 KB Output is correct
39 Correct 77 ms 117440 KB Output is correct
40 Correct 62 ms 117448 KB Output is correct
41 Correct 62 ms 117444 KB Output is correct
42 Correct 34 ms 115148 KB Output is correct
43 Correct 38 ms 115156 KB Output is correct
44 Correct 33 ms 115156 KB Output is correct
45 Correct 63 ms 120512 KB Output is correct
46 Correct 70 ms 120472 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 108112 KB Output is correct
2 Correct 27 ms 108092 KB Output is correct
3 Correct 26 ms 108112 KB Output is correct
4 Correct 24 ms 108052 KB Output is correct
5 Correct 27 ms 108284 KB Output is correct
6 Correct 24 ms 108112 KB Output is correct
7 Correct 25 ms 108104 KB Output is correct
8 Correct 25 ms 108112 KB Output is correct
9 Correct 22 ms 108368 KB Output is correct
10 Correct 23 ms 108476 KB Output is correct
11 Correct 20 ms 108624 KB Output is correct
12 Correct 19 ms 108516 KB Output is correct
13 Correct 18 ms 108640 KB Output is correct
14 Correct 20 ms 108640 KB Output is correct
15 Correct 19 ms 108624 KB Output is correct
16 Correct 20 ms 108892 KB Output is correct
17 Correct 27 ms 110672 KB Output is correct
18 Correct 27 ms 113744 KB Output is correct
19 Correct 29 ms 114256 KB Output is correct
20 Correct 36 ms 114512 KB Output is correct
21 Correct 20 ms 109444 KB Output is correct
22 Correct 28 ms 113744 KB Output is correct
23 Correct 28 ms 113224 KB Output is correct
24 Correct 32 ms 114256 KB Output is correct
25 Correct 30 ms 114512 KB Output is correct
26 Correct 30 ms 114508 KB Output is correct
27 Correct 33 ms 114512 KB Output is correct
28 Correct 36 ms 114504 KB Output is correct
29 Correct 48 ms 114512 KB Output is correct
30 Correct 32 ms 114256 KB Output is correct
31 Correct 38 ms 114264 KB Output is correct
32 Correct 34 ms 114512 KB Output is correct
33 Correct 47 ms 115148 KB Output is correct
34 Correct 49 ms 115016 KB Output is correct
35 Correct 49 ms 114880 KB Output is correct
36 Correct 33 ms 112004 KB Output is correct
37 Correct 67 ms 117200 KB Output is correct
38 Correct 65 ms 117456 KB Output is correct
39 Correct 67 ms 117440 KB Output is correct
40 Correct 64 ms 117448 KB Output is correct
41 Correct 63 ms 117524 KB Output is correct
42 Correct 38 ms 115148 KB Output is correct
43 Correct 39 ms 115148 KB Output is correct
44 Correct 37 ms 115032 KB Output is correct
45 Correct 64 ms 120512 KB Output is correct
46 Correct 69 ms 120396 KB Output is correct
47 Correct 215 ms 153804 KB Output is correct
48 Correct 153 ms 182572 KB Output is correct
49 Correct 159 ms 189060 KB Output is correct
50 Correct 169 ms 196480 KB Output is correct
51 Correct 268 ms 205512 KB Output is correct
52 Correct 272 ms 206016 KB Output is correct
53 Correct 217 ms 202480 KB Output is correct
54 Correct 204 ms 200776 KB Output is correct
55 Correct 212 ms 200776 KB Output is correct
56 Correct 192 ms 203336 KB Output is correct
57 Correct 367 ms 202952 KB Output is correct
58 Correct 198 ms 201704 KB Output is correct
59 Correct 196 ms 201932 KB Output is correct
60 Correct 213 ms 202444 KB Output is correct
61 Correct 199 ms 202192 KB Output is correct
62 Correct 220 ms 206492 KB Output is correct
63 Correct 252 ms 232688 KB Output is correct
64 Correct 266 ms 241156 KB Output is correct
65 Correct 288 ms 252856 KB Output is correct
66 Runtime error 255 ms 262144 KB Execution killed with signal 9
67 Halted 0 ms 0 KB -