oj.uz

Submission #1110103

# Submission time Handle Problem Language Result Execution time Memory
1110103 2024-11-08T17:40:27 Z HossamHero7 Jakarta Skyscrapers (APIO15_skyscraper) C++14
57 / 100
 355 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[N][SQ+1];
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,3>,vector<array<ll,3>>,greater<>> q;
    for(int i=0;i<N;i++) for(int j=0;j<=SQ;j++) dis[i][j] = 1e18;
    dis[d[0].first][0] = 0;
    q.push({0,d[0].first,0});
    while(q.size()){
        auto [c,i,p] = q.top();     q.pop();
        if(c > dis[i][p]) continue;
        if(p == 0){
            for(auto [ii,pp] : r_adj1[i]){
                if(c < dis[ii][pp]) {
                    //cout<<"HI"<<endl;
                    q.push({c,ii,pp});
                    dis[ii][pp] = c;
                }
            }
            for(auto j : r_adj2[i]){
                if(c < dis[j][SQ]){
                    q.push({c,j,SQ});
                    dis[j][SQ] = c;
                }
            }
        }
        else if(p < SQ){
            for(auto j : adj1[i][p]){
                if(c < dis[j][0]){
                    //if(i == 0 && p == 2) cout<<j<<endl;
                    q.push({c,j,0});
                    dis[j][0] = c;
                }
            }
            for(auto j : adj11[i][p]){
 
                    //if(t == 1 && i == 4 && p == 1) cout<<"mm"<<endl;
                if(c+1 < dis[j][p]){
 
                    //if(t == 1 && i == 4 && p == 1) cout<<j<<' '<<p<<endl;
                    q.push({c+1,j,p});
                    dis[j][p] = c+1;
                }
            }
        }
        else {
            for(auto [j,cost] : adj2[i]){
                if(c + cost < dis[j][0]){
                    q.push({c+cost,j,0});
                    dis[j][0] = c + cost;
                }
            }
        }
    }
    cout<<(dis[d[1].first][0] == 1e18 ? -1 : dis[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,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:83:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   83 |             for(auto [j,cost] : adj2[i]){
      |                      ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 166984 KB Output is correct
2 Correct 28 ms 166984 KB Output is correct
3 Correct 28 ms 166984 KB Output is correct
4 Correct 34 ms 167248 KB Output is correct
5 Correct 37 ms 167240 KB Output is correct
6 Correct 34 ms 167248 KB Output is correct
7 Correct 32 ms 167104 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 166992 KB Output is correct
2 Correct 40 ms 166984 KB Output is correct
3 Correct 47 ms 167108 KB Output is correct
4 Correct 46 ms 166988 KB Output is correct
5 Correct 42 ms 166984 KB Output is correct
6 Correct 42 ms 167160 KB Output is correct
7 Correct 41 ms 167248 KB Output is correct
8 Correct 39 ms 167248 KB Output is correct
9 Correct 48 ms 167252 KB Output is correct
10 Correct 43 ms 167704 KB Output is correct
11 Correct 53 ms 167860 KB Output is correct
12 Correct 54 ms 167752 KB Output is correct
13 Correct 59 ms 167752 KB Output is correct
14 Correct 67 ms 167680 KB Output is correct
15 Correct 64 ms 167752 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 167092 KB Output is correct
2 Correct 60 ms 166984 KB Output is correct
3 Correct 51 ms 167124 KB Output is correct
4 Correct 50 ms 167008 KB Output is correct
5 Correct 59 ms 167092 KB Output is correct
6 Correct 60 ms 167120 KB Output is correct
7 Correct 48 ms 167240 KB Output is correct
8 Correct 45 ms 167248 KB Output is correct
9 Correct 49 ms 167240 KB Output is correct
10 Correct 49 ms 167752 KB Output is correct
11 Correct 58 ms 167764 KB Output is correct
12 Correct 49 ms 167752 KB Output is correct
13 Correct 55 ms 167752 KB Output is correct
14 Correct 50 ms 167752 KB Output is correct
15 Correct 57 ms 167752 KB Output is correct
16 Correct 57 ms 168448 KB Output is correct
17 Correct 77 ms 171852 KB Output is correct
18 Correct 73 ms 177936 KB Output is correct
19 Correct 79 ms 179544 KB Output is correct
20 Correct 86 ms 179784 KB Output is correct
21 Correct 60 ms 169544 KB Output is correct
22 Correct 72 ms 178248 KB Output is correct
23 Correct 70 ms 177224 KB Output is correct
24 Correct 91 ms 179160 KB Output is correct
25 Correct 72 ms 179784 KB Output is correct
26 Correct 81 ms 179716 KB Output is correct
27 Correct 76 ms 179644 KB Output is correct
28 Correct 77 ms 179788 KB Output is correct
29 Correct 92 ms 179528 KB Output is correct
30 Correct 106 ms 179652 KB Output is correct
31 Correct 87 ms 179528 KB Output is correct
32 Correct 96 ms 179528 KB Output is correct
33 Correct 104 ms 179720 KB Output is correct
34 Correct 126 ms 179784 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 166984 KB Output is correct
2 Correct 73 ms 166984 KB Output is correct
3 Correct 35 ms 166984 KB Output is correct
4 Correct 35 ms 167000 KB Output is correct
5 Correct 37 ms 167220 KB Output is correct
6 Correct 43 ms 167248 KB Output is correct
7 Correct 45 ms 166980 KB Output is correct
8 Correct 57 ms 167240 KB Output is correct
9 Correct 53 ms 167356 KB Output is correct
10 Correct 51 ms 167720 KB Output is correct
11 Correct 57 ms 167660 KB Output is correct
12 Correct 51 ms 167724 KB Output is correct
13 Correct 54 ms 167760 KB Output is correct
14 Correct 51 ms 167732 KB Output is correct
15 Correct 57 ms 167680 KB Output is correct
16 Correct 56 ms 168264 KB Output is correct
17 Correct 61 ms 171792 KB Output is correct
18 Correct 68 ms 177952 KB Output is correct
19 Correct 68 ms 179528 KB Output is correct
20 Correct 68 ms 179560 KB Output is correct
21 Correct 51 ms 169692 KB Output is correct
22 Correct 83 ms 178136 KB Output is correct
23 Correct 85 ms 177248 KB Output is correct
24 Correct 83 ms 179132 KB Output is correct
25 Correct 86 ms 179784 KB Output is correct
26 Correct 76 ms 179684 KB Output is correct
27 Correct 79 ms 179644 KB Output is correct
28 Correct 80 ms 179660 KB Output is correct
29 Correct 81 ms 179552 KB Output is correct
30 Correct 82 ms 179608 KB Output is correct
31 Correct 79 ms 179528 KB Output is correct
32 Correct 73 ms 179700 KB Output is correct
33 Correct 114 ms 179684 KB Output is correct
34 Correct 90 ms 179688 KB Output is correct
35 Correct 101 ms 177972 KB Output is correct
36 Correct 54 ms 174160 KB Output is correct
37 Correct 104 ms 181256 KB Output is correct
38 Correct 96 ms 182096 KB Output is correct
39 Correct 98 ms 182044 KB Output is correct
40 Correct 100 ms 182084 KB Output is correct
41 Correct 129 ms 182032 KB Output is correct
42 Correct 73 ms 180164 KB Output is correct
43 Correct 83 ms 180268 KB Output is correct
44 Correct 70 ms 180424 KB Output is correct
45 Correct 107 ms 184320 KB Output is correct
46 Correct 138 ms 184300 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 166992 KB Output is correct
2 Correct 48 ms 167024 KB Output is correct
3 Correct 49 ms 166984 KB Output is correct
4 Correct 69 ms 166988 KB Output is correct
5 Correct 47 ms 167056 KB Output is correct
6 Correct 63 ms 166984 KB Output is correct
7 Correct 53 ms 167124 KB Output is correct
8 Correct 43 ms 167228 KB Output is correct
9 Correct 46 ms 167240 KB Output is correct
10 Correct 48 ms 167524 KB Output is correct
11 Correct 48 ms 167752 KB Output is correct
12 Correct 48 ms 167780 KB Output is correct
13 Correct 48 ms 167680 KB Output is correct
14 Correct 68 ms 167752 KB Output is correct
15 Correct 80 ms 167752 KB Output is correct
16 Correct 57 ms 168264 KB Output is correct
17 Correct 98 ms 172008 KB Output is correct
18 Correct 84 ms 178136 KB Output is correct
19 Correct 80 ms 179476 KB Output is correct
20 Correct 83 ms 179724 KB Output is correct
21 Correct 56 ms 169524 KB Output is correct
22 Correct 68 ms 178248 KB Output is correct
23 Correct 79 ms 177224 KB Output is correct
24 Correct 69 ms 179216 KB Output is correct
25 Correct 78 ms 179784 KB Output is correct
26 Correct 72 ms 179528 KB Output is correct
27 Correct 64 ms 179528 KB Output is correct
28 Correct 61 ms 179792 KB Output is correct
29 Correct 71 ms 179472 KB Output is correct
30 Correct 70 ms 179492 KB Output is correct
31 Correct 74 ms 179460 KB Output is correct
32 Correct 69 ms 179528 KB Output is correct
33 Correct 88 ms 179784 KB Output is correct
34 Correct 81 ms 179784 KB Output is correct
35 Correct 84 ms 177984 KB Output is correct
36 Correct 59 ms 174152 KB Output is correct
37 Correct 111 ms 181224 KB Output is correct
38 Correct 103 ms 182128 KB Output is correct
39 Correct 107 ms 182084 KB Output is correct
40 Correct 95 ms 182088 KB Output is correct
41 Correct 102 ms 182084 KB Output is correct
42 Correct 63 ms 180180 KB Output is correct
43 Correct 72 ms 180164 KB Output is correct
44 Correct 71 ms 180412 KB Output is correct
45 Correct 135 ms 184304 KB Output is correct
46 Correct 126 ms 184400 KB Output is correct
47 Correct 355 ms 250440 KB Output is correct
48 Runtime error 229 ms 262144 KB Execution killed with signal 9
49 Halted 0 ms 0 KB -