oj.uz

Submission #977080

# Submission time Handle Problem Language Result Execution time Memory
977080 2024-05-07T11:14:38 Z nnin Jakarta Skyscrapers (APIO15_skyscraper) C++14
0 / 100
 1 ms 1176 KB 
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>

int N, M, B[30005], P[30005];
vector<pii> adj[30005];
int mindis[30005];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin>>N>>M;
    for(int i=0;i<M;i++) {
        cin>>B[i]>>P[i];
        for(int j=1;B[i]-(j*P[i])>=0;j++) {
            adj[B[i]].push_back({B[i]-(j*P[i]), j});
        }
        for(int j=1;B[i]+(j*P[i])<N;j++) {
            adj[B[i]].push_back({B[i]+(j*P[i]), j});
        }
    }
    for(int i=0;i<N;i++) mindis[i] = 2e9;
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({0, 0});
    mindis[0] = 0;
    while(!pq.empty()) {
        auto [dis, u] = pq.top();
        pq.pop();
        if(mindis[u]!=dis) continue;
        for(auto [v, w]:adj[u]) {
            if(mindis[v]>dis+w) {
                mindis[v] = dis+w;
                pq.push({mindis[v], v});
            }
        }
    }
    cout<<mindis[1];
}

/*
5 3
0 2
1 1
4 1
*/

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:26:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   26 |         auto [dis, u] = pq.top();
      |              ^
skyscraper.cpp:29:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   29 |         for(auto [v, w]:adj[u]) {
      |                  ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1112 KB Output is correct
2 Correct 1 ms 1112 KB Output is correct
3 Incorrect 1 ms 1116 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Incorrect 1 ms 1176 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 1 ms 1172 KB Output is correct
3 Incorrect 1 ms 1116 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1112 KB Output is correct
2 Correct 1 ms 1112 KB Output is correct
3 Incorrect 1 ms 1116 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1112 KB Output is correct
2 Correct 1 ms 1172 KB Output is correct
3 Incorrect 1 ms 1116 KB Output isn't correct
4 Halted 0 ms 0 KB -