oj.uz

Submission #823604

# Submission time Handle Problem Language Result Execution time Memory
823604 2023-08-12T20:41:33 Z lprochniak Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 356 ms 262144 KB 
//https://oj.uz/problem/view/APIO15_skyscraper
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define st first
#define nd second
#define pii pair<int,int>
int n,m;
int root;
//position / power
struct E{
    int pos;
    int pow;
    int waga;
};
struct Node{
    int d;
    int pos;
    int pow;
};
class comp{
    public:
        bool operator()(Node A,Node B){
            return A.d<B.d;
        }
};
vector<pair<int,int>> kand,doges;
unordered_map<int,bool> odw[30009];
vector<E> edges[30001][174];
int dis[30001][174];
void build(){
    for(int i=0;i<n;i++){
        for(int j=1;j<=root;j++){
            edges[i][j].pb({i,0,0});
        }
    }
}
void addsmaller(int pos,int pow){
    if(odw[pow][pos%pow]) return;
        else odw[pow][pos%pow] = 1;
    int pos2 = pos;
    while(pos2+pow<n){
        edges[pos2][pow].pb({pos2+pow,pow,1});
        edges[pos2+pow][pow].pb({pos2,pow,1});
        pos2 += pow;
    }
    pos2 = pos;
    while(pos2-pow>=0){
        edges[pos2][pow].pb({pos2-pow,pow,1});
        edges[pos2-pow][pow].pb({pos2,pow,1});
        pos2 -= pow;
    }
}
void addbigger(int pos,int pow){
    int pos2 = pos;
    int dl = 1;
    while(pos2+pow<n){
        edges[pos][0].pb({pos2+pow,0,dl});
        pos2 += pow;
        dl++;
    }
    pos2 = pos;
    dl = 1;
    while(pos2-pow>=0){
        edges[pos][0].pb({pos2-pow,0,dl});
        pos2 -= pow;
        dl++;
    }
}
priority_queue<Node,vector<Node>,comp> q;
void dijkstra(int pocz){
    q.push({0,pocz,0});
    while(!q.empty()){
        auto t = q.top();
        q.pop();
        t.d = -t.d;
        if(dis[t.pos][t.pow] != t.d)
            continue;
        for(auto x:edges[t.pos][t.pow]){
            if(t.d + x.waga < dis[x.pos][x.pow]){
                dis[x.pos][x.pow] = t.d + x.waga;
                q.push({-dis[x.pos][x.pow],x.pos,x.pow});
            }
        }
    }
}
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m;
    root = (int)sqrt(n);
    build();
    int zero,one;
    for(int i=0;i<m;i++){
        int pos,pow;
        cin>>pos>>pow;
        kand.pb({pos,pow});
        if(i>1) continue;
        if(i == 0){
            zero = pos;
        } else if(i == 1){
            one = pos;
        }
    }
    sort(kand.begin(),kand.end());
    doges.pb(kand[0]);
    for(int i=1;i<m;i++){
        if(kand[i-1] != kand[i])
            doges.pb(kand[i]);
    }

    for(int i=0;i<doges.size();i++){
        int pos = doges[i].st;
        int pow = doges[i].nd;
        if(pow <= root){
            edges[pos][0].pb({pos,pow,0});
            addsmaller(pos,pow);
        } else if(pow<=n){
            addbigger(pos,pow);
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<=root;j++){
            dis[i][j] = 1000000000;
        }
    }
    dis[zero][0] = 0;
    dijkstra(zero);
    /*
    pair<long long,pii> maxi = {0,{0,0}};
    int s = 0;
    for(int i=0;i<n;i++){
        for(int j=0;j<=root;j++){
            s += edges[i][j].size();
            if(edges[i][j].size()>maxi.st)
                maxi = {(long long)edges[i][j].size(),{i,j}};
            //cout<<"pos: "<<i<<" pow: "<<j<<endl;
            //for(auto x:edges[i][j]){
                //cout<<"pos: "<<x.pos<<" pow: "<<x.pow<<" waga: "<<x.waga<<endl;
            //}
        }
    }
    cout<<s<<" "<<maxi.st<<" "<<maxi.nd.st<<" "<<maxi.nd.nd<<endl;
    */
    if(dis[one][0] == 1000000000){
        cout<<"-1\n";
    } else cout<<dis[one][0]<<endl;
    return 0;
}

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:111:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |     for(int i=0;i<doges.size();i++){
      |                 ~^~~~~~~~~~~~~
skyscraper.cpp:144:18: warning: 'one' may be used uninitialized in this function [-Wmaybe-uninitialized]
  144 |     if(dis[one][0] == 1000000000){
      |        ~~~~~~~~~~^
skyscraper.cpp:127:13: warning: 'zero' may be used uninitialized in this function [-Wmaybe-uninitialized]
  127 |     dijkstra(zero);
      |     ~~~~~~~~^~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 124492 KB Output is correct
2 Correct 50 ms 124468 KB Output is correct
3 Correct 50 ms 124544 KB Output is correct
4 Correct 50 ms 124488 KB Output is correct
5 Correct 50 ms 124492 KB Output is correct
6 Correct 51 ms 124544 KB Output is correct
7 Correct 51 ms 124496 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 124524 KB Output is correct
2 Correct 50 ms 124448 KB Output is correct
3 Correct 53 ms 124556 KB Output is correct
4 Correct 50 ms 124500 KB Output is correct
5 Correct 56 ms 124472 KB Output is correct
6 Correct 51 ms 124464 KB Output is correct
7 Correct 50 ms 124492 KB Output is correct
8 Correct 51 ms 124528 KB Output is correct
9 Correct 51 ms 124596 KB Output is correct
10 Correct 51 ms 124620 KB Output is correct
11 Correct 51 ms 124788 KB Output is correct
12 Correct 51 ms 124620 KB Output is correct
13 Correct 51 ms 124612 KB Output is correct
14 Correct 50 ms 124748 KB Output is correct
15 Correct 51 ms 124740 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 124480 KB Output is correct
2 Correct 50 ms 124500 KB Output is correct
3 Correct 50 ms 124468 KB Output is correct
4 Correct 51 ms 124496 KB Output is correct
5 Correct 52 ms 124444 KB Output is correct
6 Correct 50 ms 124464 KB Output is correct
7 Correct 50 ms 124500 KB Output is correct
8 Correct 50 ms 124492 KB Output is correct
9 Correct 50 ms 124548 KB Output is correct
10 Correct 52 ms 124580 KB Output is correct
11 Correct 51 ms 124748 KB Output is correct
12 Correct 50 ms 124616 KB Output is correct
13 Correct 50 ms 124620 KB Output is correct
14 Correct 51 ms 124684 KB Output is correct
15 Correct 51 ms 124660 KB Output is correct
16 Correct 52 ms 124808 KB Output is correct
17 Correct 55 ms 126040 KB Output is correct
18 Correct 55 ms 128136 KB Output is correct
19 Correct 55 ms 128768 KB Output is correct
20 Correct 56 ms 128716 KB Output is correct
21 Correct 56 ms 125128 KB Output is correct
22 Correct 56 ms 128208 KB Output is correct
23 Correct 56 ms 127836 KB Output is correct
24 Correct 57 ms 128848 KB Output is correct
25 Correct 56 ms 128900 KB Output is correct
26 Correct 56 ms 129032 KB Output is correct
27 Correct 56 ms 128880 KB Output is correct
28 Correct 58 ms 129436 KB Output is correct
29 Correct 71 ms 130892 KB Output is correct
30 Correct 61 ms 129392 KB Output is correct
31 Correct 62 ms 129864 KB Output is correct
32 Correct 59 ms 129248 KB Output is correct
33 Correct 76 ms 132300 KB Output is correct
34 Correct 77 ms 132300 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 124524 KB Output is correct
2 Correct 53 ms 124504 KB Output is correct
3 Correct 50 ms 124492 KB Output is correct
4 Correct 51 ms 124428 KB Output is correct
5 Correct 51 ms 124448 KB Output is correct
6 Correct 51 ms 124440 KB Output is correct
7 Correct 50 ms 124524 KB Output is correct
8 Correct 51 ms 124472 KB Output is correct
9 Correct 55 ms 124536 KB Output is correct
10 Correct 50 ms 124660 KB Output is correct
11 Correct 51 ms 124664 KB Output is correct
12 Correct 51 ms 124620 KB Output is correct
13 Correct 51 ms 124624 KB Output is correct
14 Correct 52 ms 124772 KB Output is correct
15 Correct 53 ms 124668 KB Output is correct
16 Correct 52 ms 124876 KB Output is correct
17 Correct 56 ms 126064 KB Output is correct
18 Correct 55 ms 128224 KB Output is correct
19 Correct 55 ms 128856 KB Output is correct
20 Correct 55 ms 128740 KB Output is correct
21 Correct 51 ms 125072 KB Output is correct
22 Correct 55 ms 128256 KB Output is correct
23 Correct 55 ms 127740 KB Output is correct
24 Correct 58 ms 128844 KB Output is correct
25 Correct 55 ms 128804 KB Output is correct
26 Correct 55 ms 128952 KB Output is correct
27 Correct 56 ms 128864 KB Output is correct
28 Correct 58 ms 129448 KB Output is correct
29 Correct 69 ms 130808 KB Output is correct
30 Correct 59 ms 129276 KB Output is correct
31 Correct 63 ms 129868 KB Output is correct
32 Correct 59 ms 129228 KB Output is correct
33 Correct 77 ms 132300 KB Output is correct
34 Correct 75 ms 132332 KB Output is correct
35 Correct 67 ms 129716 KB Output is correct
36 Correct 57 ms 126916 KB Output is correct
37 Correct 73 ms 132940 KB Output is correct
38 Correct 93 ms 132904 KB Output is correct
39 Correct 76 ms 132664 KB Output is correct
40 Correct 75 ms 132684 KB Output is correct
41 Correct 74 ms 132688 KB Output is correct
42 Correct 59 ms 129184 KB Output is correct
43 Correct 59 ms 129096 KB Output is correct
44 Correct 58 ms 128992 KB Output is correct
45 Correct 92 ms 137288 KB Output is correct
46 Correct 90 ms 137288 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 124424 KB Output is correct
2 Correct 52 ms 124540 KB Output is correct
3 Correct 51 ms 124492 KB Output is correct
4 Correct 51 ms 124492 KB Output is correct
5 Correct 51 ms 124508 KB Output is correct
6 Correct 53 ms 124480 KB Output is correct
7 Correct 51 ms 124480 KB Output is correct
8 Correct 51 ms 124496 KB Output is correct
9 Correct 50 ms 124532 KB Output is correct
10 Correct 53 ms 124684 KB Output is correct
11 Correct 53 ms 124748 KB Output is correct
12 Correct 51 ms 124620 KB Output is correct
13 Correct 51 ms 124620 KB Output is correct
14 Correct 54 ms 124760 KB Output is correct
15 Correct 51 ms 124760 KB Output is correct
16 Correct 51 ms 124796 KB Output is correct
17 Correct 55 ms 126072 KB Output is correct
18 Correct 55 ms 128204 KB Output is correct
19 Correct 56 ms 128824 KB Output is correct
20 Correct 55 ms 128700 KB Output is correct
21 Correct 52 ms 125072 KB Output is correct
22 Correct 56 ms 128236 KB Output is correct
23 Correct 55 ms 127716 KB Output is correct
24 Correct 57 ms 128796 KB Output is correct
25 Correct 55 ms 128848 KB Output is correct
26 Correct 55 ms 128932 KB Output is correct
27 Correct 56 ms 128916 KB Output is correct
28 Correct 58 ms 129416 KB Output is correct
29 Correct 69 ms 130892 KB Output is correct
30 Correct 59 ms 129268 KB Output is correct
31 Correct 63 ms 129896 KB Output is correct
32 Correct 58 ms 129240 KB Output is correct
33 Correct 78 ms 132300 KB Output is correct
34 Correct 78 ms 132252 KB Output is correct
35 Correct 67 ms 129652 KB Output is correct
36 Correct 56 ms 126832 KB Output is correct
37 Correct 76 ms 132968 KB Output is correct
38 Correct 77 ms 132660 KB Output is correct
39 Correct 75 ms 132680 KB Output is correct
40 Correct 75 ms 132664 KB Output is correct
41 Correct 75 ms 132684 KB Output is correct
42 Correct 59 ms 129228 KB Output is correct
43 Correct 59 ms 129136 KB Output is correct
44 Correct 60 ms 129024 KB Output is correct
45 Correct 90 ms 137248 KB Output is correct
46 Correct 88 ms 137220 KB Output is correct
47 Correct 356 ms 199104 KB Output is correct
48 Correct 236 ms 259716 KB Output is correct
49 Runtime error 185 ms 262144 KB Execution killed with signal 9
50 Halted 0 ms 0 KB -