oj.uz

Submission #1110101

# Submission time Handle Problem Language Result Execution time Memory
1110101 2024-11-08T17:38:27 Z HossamHero7 Jakarta Skyscrapers (APIO15_skyscraper) C++14
57 / 100
 161 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];
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 41 ms 213836 KB Output is correct
2 Correct 38 ms 213840 KB Output is correct
3 Correct 35 ms 213840 KB Output is correct
4 Correct 36 ms 213832 KB Output is correct
5 Correct 37 ms 213840 KB Output is correct
6 Correct 43 ms 213840 KB Output is correct
7 Correct 44 ms 213844 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 213960 KB Output is correct
2 Correct 53 ms 213832 KB Output is correct
3 Correct 51 ms 213832 KB Output is correct
4 Correct 57 ms 213832 KB Output is correct
5 Correct 56 ms 213868 KB Output is correct
6 Correct 58 ms 213840 KB Output is correct
7 Correct 58 ms 213832 KB Output is correct
8 Correct 56 ms 214088 KB Output is correct
9 Correct 62 ms 214088 KB Output is correct
10 Correct 54 ms 214344 KB Output is correct
11 Correct 66 ms 214600 KB Output is correct
12 Correct 63 ms 214344 KB Output is correct
13 Correct 63 ms 214532 KB Output is correct
14 Correct 62 ms 214528 KB Output is correct
15 Correct 59 ms 214600 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 213968 KB Output is correct
2 Correct 57 ms 213828 KB Output is correct
3 Correct 52 ms 213832 KB Output is correct
4 Correct 62 ms 213832 KB Output is correct
5 Correct 63 ms 213832 KB Output is correct
6 Correct 61 ms 213872 KB Output is correct
7 Correct 63 ms 213820 KB Output is correct
8 Correct 67 ms 214088 KB Output is correct
9 Correct 63 ms 214088 KB Output is correct
10 Correct 62 ms 214344 KB Output is correct
11 Correct 59 ms 214612 KB Output is correct
12 Correct 58 ms 214476 KB Output is correct
13 Correct 59 ms 214344 KB Output is correct
14 Correct 65 ms 214600 KB Output is correct
15 Correct 59 ms 214600 KB Output is correct
16 Correct 60 ms 215112 KB Output is correct
17 Correct 73 ms 218712 KB Output is correct
18 Correct 86 ms 224764 KB Output is correct
19 Correct 82 ms 226244 KB Output is correct
20 Correct 85 ms 226376 KB Output is correct
21 Correct 65 ms 216392 KB Output is correct
22 Correct 85 ms 224840 KB Output is correct
23 Correct 84 ms 223816 KB Output is correct
24 Correct 88 ms 225864 KB Output is correct
25 Correct 82 ms 226380 KB Output is correct
26 Correct 77 ms 226252 KB Output is correct
27 Correct 78 ms 226376 KB Output is correct
28 Correct 83 ms 226376 KB Output is correct
29 Correct 87 ms 226376 KB Output is correct
30 Correct 83 ms 226376 KB Output is correct
31 Correct 89 ms 226376 KB Output is correct
32 Correct 89 ms 226328 KB Output is correct
33 Correct 99 ms 226376 KB Output is correct
34 Correct 96 ms 226376 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 213836 KB Output is correct
2 Correct 59 ms 213812 KB Output is correct
3 Correct 54 ms 213948 KB Output is correct
4 Correct 61 ms 213832 KB Output is correct
5 Correct 62 ms 213832 KB Output is correct
6 Correct 57 ms 214000 KB Output is correct
7 Correct 62 ms 213832 KB Output is correct
8 Correct 68 ms 213836 KB Output is correct
9 Correct 67 ms 214012 KB Output is correct
10 Correct 70 ms 214268 KB Output is correct
11 Correct 67 ms 214600 KB Output is correct
12 Correct 64 ms 214396 KB Output is correct
13 Correct 62 ms 214344 KB Output is correct
14 Correct 62 ms 214600 KB Output is correct
15 Correct 80 ms 214544 KB Output is correct
16 Correct 61 ms 215160 KB Output is correct
17 Correct 68 ms 218696 KB Output is correct
18 Correct 76 ms 224840 KB Output is correct
19 Correct 80 ms 226376 KB Output is correct
20 Correct 85 ms 226388 KB Output is correct
21 Correct 74 ms 216400 KB Output is correct
22 Correct 73 ms 225096 KB Output is correct
23 Correct 81 ms 223820 KB Output is correct
24 Correct 79 ms 225800 KB Output is correct
25 Correct 83 ms 226376 KB Output is correct
26 Correct 80 ms 226356 KB Output is correct
27 Correct 90 ms 226396 KB Output is correct
28 Correct 87 ms 226376 KB Output is correct
29 Correct 98 ms 226376 KB Output is correct
30 Correct 92 ms 226384 KB Output is correct
31 Correct 98 ms 226376 KB Output is correct
32 Correct 90 ms 226376 KB Output is correct
33 Correct 103 ms 226484 KB Output is correct
34 Correct 111 ms 226576 KB Output is correct
35 Correct 109 ms 225024 KB Output is correct
36 Correct 81 ms 221008 KB Output is correct
37 Correct 122 ms 228544 KB Output is correct
38 Correct 127 ms 229104 KB Output is correct
39 Correct 128 ms 229232 KB Output is correct
40 Correct 125 ms 229064 KB Output is correct
41 Correct 115 ms 229060 KB Output is correct
42 Correct 94 ms 227012 KB Output is correct
43 Correct 88 ms 227012 KB Output is correct
44 Correct 84 ms 227016 KB Output is correct
45 Correct 129 ms 231184 KB Output is correct
46 Correct 132 ms 231268 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 213832 KB Output is correct
2 Correct 61 ms 213832 KB Output is correct
3 Correct 58 ms 213832 KB Output is correct
4 Correct 62 ms 213832 KB Output is correct
5 Correct 59 ms 213832 KB Output is correct
6 Correct 55 ms 213832 KB Output is correct
7 Correct 60 ms 213892 KB Output is correct
8 Correct 64 ms 214080 KB Output is correct
9 Correct 63 ms 214148 KB Output is correct
10 Correct 66 ms 214344 KB Output is correct
11 Correct 68 ms 214408 KB Output is correct
12 Correct 69 ms 214428 KB Output is correct
13 Correct 65 ms 214348 KB Output is correct
14 Correct 64 ms 214600 KB Output is correct
15 Correct 63 ms 214496 KB Output is correct
16 Correct 61 ms 215116 KB Output is correct
17 Correct 72 ms 218696 KB Output is correct
18 Correct 80 ms 224796 KB Output is correct
19 Correct 81 ms 226380 KB Output is correct
20 Correct 93 ms 226416 KB Output is correct
21 Correct 61 ms 216264 KB Output is correct
22 Correct 83 ms 225016 KB Output is correct
23 Correct 76 ms 223816 KB Output is correct
24 Correct 85 ms 225872 KB Output is correct
25 Correct 86 ms 226376 KB Output is correct
26 Correct 86 ms 226376 KB Output is correct
27 Correct 82 ms 226368 KB Output is correct
28 Correct 83 ms 226556 KB Output is correct
29 Correct 93 ms 226376 KB Output is correct
30 Correct 90 ms 226376 KB Output is correct
31 Correct 85 ms 226376 KB Output is correct
32 Correct 84 ms 226376 KB Output is correct
33 Correct 99 ms 226376 KB Output is correct
34 Correct 95 ms 226488 KB Output is correct
35 Correct 99 ms 224960 KB Output is correct
36 Correct 73 ms 221000 KB Output is correct
37 Correct 121 ms 228544 KB Output is correct
38 Correct 136 ms 229064 KB Output is correct
39 Correct 125 ms 229060 KB Output is correct
40 Correct 131 ms 229064 KB Output is correct
41 Correct 121 ms 229104 KB Output is correct
42 Correct 82 ms 226960 KB Output is correct
43 Correct 83 ms 227012 KB Output is correct
44 Correct 94 ms 227176 KB Output is correct
45 Correct 125 ms 231368 KB Output is correct
46 Correct 133 ms 231364 KB Output is correct
47 Runtime error 161 ms 262144 KB Execution killed with signal 9
48 Halted 0 ms 0 KB -