oj.uz

답안 #820174

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
820174 2023-08-10T22:50:25 Z lprochniak Jakarta Skyscrapers (APIO15_skyscraper) C++17
22 / 100
 55 ms 34776 KB 
#include<bits/stdc++.h>
using namespace std;
#define MAX 30009
#define pb push_back
#define st first
#define nd second
int n,m;
vector<int> p[MAX];
struct Node{
    int v;
    int waga;
};
vector<Node> edges[MAX];
int wyn[MAX];
void dijkstra(int s){
    priority_queue<pair<int,int>> q;
    q.push({0,s});

    while(!q.empty()){
        pair<int,int> t = q.top();
        q.pop();
        t.st = -t.st;

        for(auto x:edges[t.nd]){
            if(t.st+x.waga<wyn[x.v]){
                wyn[x.v] = t.st + x.waga;
                q.push({-wyn[x.v],x.v});
            }
        }
    }
}
int main(){
    cin>>n>>m;
    memset(p,0,sizeof p);
    int whereZero,whereOne;
    for(int i=0;i<m;i++){
        int b,pwr;
        cin>>b>>pwr;
        p[b].pb(pwr);
        if(i == 0)
            whereZero = b;
        else if(i == 1)
            whereOne = b;
    }
    for(int i=0;i<n;i++){
        if(p[i].empty()) continue;
        for(auto pwr:p[i]){
            int idx = i-pwr;
            int ile = 1;
            while(idx>=0){
                edges[i].pb({idx,ile});
                idx-=pwr,ile++;
            }
            idx = i+pwr;
            ile = 1;
            while(idx<n){
                edges[i].pb({idx,ile});
                idx+=pwr,ile++;
            }
        }
    }
    for(int i=1;i<n;i++){
        wyn[i] = 1000000000;
    }
    dijkstra(whereZero);
    
    if(wyn[whereOne] == 1000000000){
        cout<<"-1\n";
    } else
        cout<<wyn[whereOne]<<"\n";
    return 0;
}

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:34:24: warning: 'void* memset(void*, int, size_t)' clearing an object of type 'class std::vector<int>' with no trivial copy-assignment; use assignment or value-initialization instead [-Wclass-memaccess]
   34 |     memset(p,0,sizeof p);
      |                        ^
In file included from /usr/include/c++/10/vector:67,
                 from /usr/include/c++/10/functional:62,
                 from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/10/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from skyscraper.cpp:1:
/usr/include/c++/10/bits/stl_vector.h:389:11: note: 'class std::vector<int>' declared here
  389 |     class vector : protected _Vector_base<_Tp, _Alloc>
      |           ^~~~~~
skyscraper.cpp:67:20: warning: 'whereOne' may be used uninitialized in this function [-Wmaybe-uninitialized]
   67 |     if(wyn[whereOne] == 1000000000){
      |        ~~~~~~~~~~~~^
skyscraper.cpp:65:13: warning: 'whereZero' may be used uninitialized in this function [-Wmaybe-uninitialized]
   65 |     dijkstra(whereZero);
      |     ~~~~~~~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1716 KB Output is correct
2 Correct 1 ms 1620 KB Output is correct
3 Correct 1 ms 1620 KB Output is correct
4 Correct 1 ms 1620 KB Output is correct
5 Correct 2 ms 1620 KB Output is correct
6 Correct 1 ms 1620 KB Output is correct
7 Correct 1 ms 1620 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1620 KB Output is correct
2 Correct 1 ms 1620 KB Output is correct
3 Correct 1 ms 1716 KB Output is correct
4 Correct 1 ms 1716 KB Output is correct
5 Correct 1 ms 1620 KB Output is correct
6 Correct 1 ms 1620 KB Output is correct
7 Correct 1 ms 1620 KB Output is correct
8 Correct 1 ms 1620 KB Output is correct
9 Correct 1 ms 1720 KB Output is correct
10 Correct 2 ms 1748 KB Output is correct
11 Correct 2 ms 1748 KB Output is correct
12 Correct 5 ms 3912 KB Output is correct
13 Correct 4 ms 3916 KB Output is correct
14 Correct 2 ms 1708 KB Output is correct
15 Correct 2 ms 1748 KB Output is correct

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1648 KB Output is correct
2 Correct 1 ms 1620 KB Output is correct
3 Correct 1 ms 1716 KB Output is correct
4 Correct 1 ms 1692 KB Output is correct
5 Correct 1 ms 1620 KB Output is correct
6 Correct 1 ms 1616 KB Output is correct
7 Correct 1 ms 1712 KB Output is correct
8 Correct 1 ms 1620 KB Output is correct
9 Correct 1 ms 1620 KB Output is correct
10 Correct 1 ms 1620 KB Output is correct
11 Correct 2 ms 1748 KB Output is correct
12 Correct 4 ms 3912 KB Output is correct
13 Correct 4 ms 4008 KB Output is correct
14 Correct 2 ms 1748 KB Output is correct
15 Correct 2 ms 1748 KB Output is correct
16 Correct 2 ms 1748 KB Output is correct
17 Correct 2 ms 2004 KB Output is correct
18 Correct 2 ms 1728 KB Output is correct
19 Correct 2 ms 1736 KB Output is correct
20 Correct 51 ms 33868 KB Output is correct
21 Correct 2 ms 1756 KB Output is correct
22 Correct 2 ms 1720 KB Output is correct
23 Correct 2 ms 1748 KB Output is correct
24 Correct 3 ms 1876 KB Output is correct
25 Correct 4 ms 1884 KB Output is correct
26 Correct 55 ms 34736 KB Output is correct
27 Correct 52 ms 34680 KB Output is correct
28 Incorrect 2 ms 2004 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1620 KB Output is correct
2 Correct 2 ms 1620 KB Output is correct
3 Correct 1 ms 1620 KB Output is correct
4 Correct 1 ms 1620 KB Output is correct
5 Correct 1 ms 1712 KB Output is correct
6 Correct 1 ms 1620 KB Output is correct
7 Correct 1 ms 1724 KB Output is correct
8 Correct 2 ms 1720 KB Output is correct
9 Correct 1 ms 1620 KB Output is correct
10 Correct 1 ms 1716 KB Output is correct
11 Correct 2 ms 1748 KB Output is correct
12 Correct 4 ms 3912 KB Output is correct
13 Correct 5 ms 4044 KB Output is correct
14 Correct 2 ms 1748 KB Output is correct
15 Correct 2 ms 1748 KB Output is correct
16 Correct 1 ms 1748 KB Output is correct
17 Correct 2 ms 2004 KB Output is correct
18 Correct 2 ms 1748 KB Output is correct
19 Correct 1 ms 1724 KB Output is correct
20 Correct 52 ms 33852 KB Output is correct
21 Correct 1 ms 1748 KB Output is correct
22 Correct 1 ms 1748 KB Output is correct
23 Correct 2 ms 1748 KB Output is correct
24 Correct 3 ms 1856 KB Output is correct
25 Correct 2 ms 1856 KB Output is correct
26 Correct 54 ms 34776 KB Output is correct
27 Correct 51 ms 34676 KB Output is correct
28 Incorrect 3 ms 2004 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1620 KB Output is correct
2 Correct 1 ms 1712 KB Output is correct
3 Correct 1 ms 1620 KB Output is correct
4 Correct 1 ms 1620 KB Output is correct
5 Correct 1 ms 1620 KB Output is correct
6 Correct 1 ms 1620 KB Output is correct
7 Correct 1 ms 1620 KB Output is correct
8 Correct 1 ms 1620 KB Output is correct
9 Correct 1 ms 1620 KB Output is correct
10 Correct 1 ms 1620 KB Output is correct
11 Correct 2 ms 1748 KB Output is correct
12 Correct 4 ms 3912 KB Output is correct
13 Correct 4 ms 4028 KB Output is correct
14 Correct 2 ms 1728 KB Output is correct
15 Correct 2 ms 1748 KB Output is correct
16 Correct 1 ms 1748 KB Output is correct
17 Correct 2 ms 2004 KB Output is correct
18 Correct 1 ms 1748 KB Output is correct
19 Correct 1 ms 1748 KB Output is correct
20 Correct 51 ms 34020 KB Output is correct
21 Correct 1 ms 1748 KB Output is correct
22 Correct 1 ms 1748 KB Output is correct
23 Correct 2 ms 1728 KB Output is correct
24 Correct 3 ms 1876 KB Output is correct
25 Correct 2 ms 1860 KB Output is correct
26 Correct 54 ms 34752 KB Output is correct
27 Correct 50 ms 34744 KB Output is correct
28 Incorrect 2 ms 2004 KB Output isn't correct
29 Halted 0 ms 0 KB -