oj.uz

Submission #242941

# Submission time Handle Problem Language Result Execution time Memory
242941 2020-06-30T01:25:47 Z kai824 Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 252 ms 262144 KB 
#include"bits/stdc++.h"
using namespace std;

#define int long long
#define mp make_pair
#define pii pair<int,int>

vector<pair<pii,int> > adjl[30000][180];//position, power, weight... if power==179, then it's dummy
bool used[30000][180];
int dist[30000][180],a,b,c;

priority_queue<pair<int,pii>,vector<pair<int,pii> >, greater<pair<int,pii> > > dijk;
//weight, pos, power

int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    int n,m,s,d,start,end;
    cin>>n>>m;//m doges, n buildings
    for(int x=0;x<n;x++){
      for(int y=0;y<179;y++){
        adjl[x][y].emplace_back(mp(x,179),0);
        dist[x][y]=LLONG_MAX;
        if(y>0){
          if(x+y<n)adjl[x][y].emplace_back(mp(x+y,y),1);
          if(x-y>=0)adjl[x][y].emplace_back(mp(x-y,y),1);
        }
      }
      dist[x][179]=LLONG_MAX;
    }
    for(int x=0;x<m;x++){
      cin>>s>>d;//position s, power d
      if(x==0)start=s;
      else if(x==1)end=s;
      if((d*d)>=n){
        for(int i=1;i<=n;i++){
          if(s-(d*i)>=0){
            adjl[s][179].emplace_back(mp(s-(d*i),179),i);
          }else if(s+(d*i)>=n)break;
          if(s+(d*i)<n){
            adjl[s][179].emplace_back(mp(s+(d*i),179),i);
          }
        }
      }else{
        adjl[s][179].emplace_back(mp(s,d),0);
        /*if(used[s][d]==false){
          for(int i=1;i<=n;i++){
            if(s-(d*i)>=0){
              adjl[s-(d*i)][d].emplace_back(mp(s-(d*i)+d,d),1);
              adjl[s-(d*i)+d][d].emplace_back(mp(s-(d*i),d),1);
            }else if(s+(d*i)>=n)break;
            if(s+(d*i)<n){
              adjl[s+(d*i)][d].emplace_back(mp(s+(d*i)-d,d),1);
              adjl[s+(d*i)-d][d].emplace_back(mp(s+(d*i),d),1);
            }
          }
        }*/
      }
    }

    dijk.emplace(0,mp(start,179));//pos, power...
    dist[start][179]=0;
    while(!dijk.empty()){
      c=dijk.top().first;
      a=dijk.top().second.first;
      b=dijk.top().second.second;
      if(a==end){
        cout<<c;
        return 0;
      }
      dijk.pop();

      for(int i=0;i<adjl[a][b].size();i++){
        if(dist[adjl[a][b][i].first.first][adjl[a][b][i].first.second]>c+adjl[a][b][i].second){
          dist[adjl[a][b][i].first.first][adjl[a][b][i].first.second]=c+adjl[a][b][i].second;
          dijk.emplace(c+adjl[a][b][i].second,adjl[a][b][i].first );
        }
      }
    }
    if(dist[end][179]==LLONG_MAX)cout<<"-1";
    else cout<<dist[end][179];
    return 0;
}
/*
*/

Compilation message

skyscraper.cpp: In function 'int32_t main()':
skyscraper.cpp:72:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=0;i<adjl[a][b].size();i++){
                   ~^~~~~~~~~~~~~~~~~~
skyscraper.cpp:61:21: warning: 'start' may be used uninitialized in this function [-Wmaybe-uninitialized]
     dist[start][179]=0;
     ~~~~~~~~~~~~~~~~^~
skyscraper.cpp:79:21: warning: 'end' may be used uninitialized in this function [-Wmaybe-uninitialized]
     if(dist[end][179]==LLONG_MAX)cout<<"-1";
        ~~~~~~~~~~~~~^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 127224 KB Output is correct
2 Correct 76 ms 127096 KB Output is correct
3 Correct 77 ms 127224 KB Output is correct
4 Correct 79 ms 127224 KB Output is correct
5 Correct 79 ms 127184 KB Output is correct
6 Correct 79 ms 127224 KB Output is correct
7 Correct 76 ms 127224 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 127224 KB Output is correct
2 Correct 86 ms 127096 KB Output is correct
3 Correct 79 ms 127224 KB Output is correct
4 Correct 79 ms 127224 KB Output is correct
5 Correct 86 ms 127224 KB Output is correct
6 Correct 79 ms 127224 KB Output is correct
7 Correct 86 ms 127224 KB Output is correct
8 Correct 80 ms 127480 KB Output is correct
9 Correct 77 ms 127788 KB Output is correct
10 Correct 80 ms 128248 KB Output is correct
11 Correct 80 ms 128248 KB Output is correct
12 Correct 89 ms 128376 KB Output is correct
13 Correct 77 ms 128248 KB Output is correct
14 Correct 78 ms 128376 KB Output is correct
15 Correct 78 ms 128376 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 127224 KB Output is correct
2 Correct 82 ms 127352 KB Output is correct
3 Correct 84 ms 127224 KB Output is correct
4 Correct 79 ms 127224 KB Output is correct
5 Correct 84 ms 127196 KB Output is correct
6 Correct 78 ms 127224 KB Output is correct
7 Correct 79 ms 127228 KB Output is correct
8 Correct 79 ms 127480 KB Output is correct
9 Correct 81 ms 127608 KB Output is correct
10 Correct 88 ms 128248 KB Output is correct
11 Correct 82 ms 128376 KB Output is correct
12 Correct 84 ms 128376 KB Output is correct
13 Correct 80 ms 128252 KB Output is correct
14 Correct 80 ms 128376 KB Output is correct
15 Correct 81 ms 128376 KB Output is correct
16 Correct 82 ms 130040 KB Output is correct
17 Correct 98 ms 141560 KB Output is correct
18 Correct 129 ms 162296 KB Output is correct
19 Correct 137 ms 167548 KB Output is correct
20 Correct 138 ms 167544 KB Output is correct
21 Correct 87 ms 134160 KB Output is correct
22 Correct 129 ms 163064 KB Output is correct
23 Correct 132 ms 159224 KB Output is correct
24 Correct 136 ms 165656 KB Output is correct
25 Correct 140 ms 167672 KB Output is correct
26 Correct 148 ms 167800 KB Output is correct
27 Correct 140 ms 167672 KB Output is correct
28 Correct 143 ms 167800 KB Output is correct
29 Correct 176 ms 167672 KB Output is correct
30 Correct 144 ms 167544 KB Output is correct
31 Correct 155 ms 167800 KB Output is correct
32 Correct 154 ms 168056 KB Output is correct
33 Correct 166 ms 169208 KB Output is correct
34 Correct 162 ms 169168 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 127224 KB Output is correct
2 Correct 78 ms 127100 KB Output is correct
3 Correct 91 ms 127188 KB Output is correct
4 Correct 87 ms 127224 KB Output is correct
5 Correct 80 ms 127224 KB Output is correct
6 Correct 79 ms 127224 KB Output is correct
7 Correct 78 ms 127236 KB Output is correct
8 Correct 77 ms 127480 KB Output is correct
9 Correct 80 ms 127608 KB Output is correct
10 Correct 78 ms 128220 KB Output is correct
11 Correct 83 ms 128248 KB Output is correct
12 Correct 103 ms 128376 KB Output is correct
13 Correct 91 ms 128248 KB Output is correct
14 Correct 92 ms 128376 KB Output is correct
15 Correct 98 ms 128280 KB Output is correct
16 Correct 98 ms 130168 KB Output is correct
17 Correct 128 ms 141432 KB Output is correct
18 Correct 144 ms 162296 KB Output is correct
19 Correct 160 ms 167672 KB Output is correct
20 Correct 146 ms 167544 KB Output is correct
21 Correct 88 ms 133884 KB Output is correct
22 Correct 127 ms 163064 KB Output is correct
23 Correct 131 ms 159352 KB Output is correct
24 Correct 145 ms 165752 KB Output is correct
25 Correct 141 ms 167672 KB Output is correct
26 Correct 144 ms 167724 KB Output is correct
27 Correct 153 ms 167800 KB Output is correct
28 Correct 148 ms 167868 KB Output is correct
29 Correct 169 ms 167672 KB Output is correct
30 Correct 144 ms 167544 KB Output is correct
31 Correct 154 ms 167672 KB Output is correct
32 Correct 150 ms 168056 KB Output is correct
33 Correct 182 ms 169208 KB Output is correct
34 Correct 171 ms 169168 KB Output is correct
35 Correct 133 ms 158072 KB Output is correct
36 Correct 114 ms 148856 KB Output is correct
37 Correct 172 ms 170488 KB Output is correct
38 Correct 154 ms 171128 KB Output is correct
39 Correct 151 ms 171000 KB Output is correct
40 Correct 152 ms 171000 KB Output is correct
41 Correct 160 ms 171264 KB Output is correct
42 Correct 153 ms 168824 KB Output is correct
43 Correct 144 ms 168692 KB Output is correct
44 Correct 143 ms 168700 KB Output is correct
45 Correct 194 ms 179308 KB Output is correct
46 Correct 171 ms 179192 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 127224 KB Output is correct
2 Correct 76 ms 127096 KB Output is correct
3 Correct 79 ms 127256 KB Output is correct
4 Correct 77 ms 127224 KB Output is correct
5 Correct 89 ms 127224 KB Output is correct
6 Correct 79 ms 127352 KB Output is correct
7 Correct 87 ms 127224 KB Output is correct
8 Correct 79 ms 127480 KB Output is correct
9 Correct 80 ms 127608 KB Output is correct
10 Correct 80 ms 128248 KB Output is correct
11 Correct 79 ms 128248 KB Output is correct
12 Correct 80 ms 128248 KB Output is correct
13 Correct 88 ms 128376 KB Output is correct
14 Correct 80 ms 128376 KB Output is correct
15 Correct 80 ms 128376 KB Output is correct
16 Correct 84 ms 130040 KB Output is correct
17 Correct 110 ms 141432 KB Output is correct
18 Correct 134 ms 162296 KB Output is correct
19 Correct 136 ms 167544 KB Output is correct
20 Correct 137 ms 167544 KB Output is correct
21 Correct 89 ms 133880 KB Output is correct
22 Correct 130 ms 163064 KB Output is correct
23 Correct 128 ms 159352 KB Output is correct
24 Correct 140 ms 165752 KB Output is correct
25 Correct 149 ms 167672 KB Output is correct
26 Correct 152 ms 167712 KB Output is correct
27 Correct 145 ms 167800 KB Output is correct
28 Correct 165 ms 167800 KB Output is correct
29 Correct 177 ms 167672 KB Output is correct
30 Correct 148 ms 167544 KB Output is correct
31 Correct 170 ms 167672 KB Output is correct
32 Correct 142 ms 167928 KB Output is correct
33 Correct 172 ms 169296 KB Output is correct
34 Correct 163 ms 169296 KB Output is correct
35 Correct 142 ms 157816 KB Output is correct
36 Correct 111 ms 148752 KB Output is correct
37 Correct 148 ms 170488 KB Output is correct
38 Correct 156 ms 171256 KB Output is correct
39 Correct 152 ms 171000 KB Output is correct
40 Correct 150 ms 171000 KB Output is correct
41 Correct 154 ms 171128 KB Output is correct
42 Correct 149 ms 168824 KB Output is correct
43 Correct 152 ms 168696 KB Output is correct
44 Correct 144 ms 168700 KB Output is correct
45 Correct 186 ms 179312 KB Output is correct
46 Correct 161 ms 179192 KB Output is correct
47 Runtime error 252 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
48 Halted 0 ms 0 KB -