oj.uz

답안 #242942

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
242942 2020-06-30T01:30:16 Z kai824 Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 362 ms 262148 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[30005][180];//position, power, weight... if power==179, then it's dummy
bool used[30005][180];
int dist[30005][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){
          used[s][d]=true;
          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);
              used[s-(d*i)][d]=true;
            }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);
              used[s+(d*i)][d]=true;
            }
          }
        }
      }
    }

    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:75:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=0;i<adjl[a][b].size();i++){
                   ~^~~~~~~~~~~~~~~~~~
skyscraper.cpp:64:21: warning: 'start' may be used uninitialized in this function [-Wmaybe-uninitialized]
     dist[start][179]=0;
     ~~~~~~~~~~~~~~~~^~
skyscraper.cpp:82: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

# 결과 실행 시간 메모리 Grader output
1 Correct 78 ms 127228 KB Output is correct
2 Correct 77 ms 127224 KB Output is correct
3 Correct 109 ms 127224 KB Output is correct
4 Correct 82 ms 127224 KB Output is correct
5 Correct 80 ms 127300 KB Output is correct
6 Correct 79 ms 127224 KB Output is correct
7 Correct 79 ms 127224 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 81 ms 127224 KB Output is correct
2 Correct 86 ms 127200 KB Output is correct
3 Correct 79 ms 127224 KB Output is correct
4 Correct 79 ms 127224 KB Output is correct
5 Correct 78 ms 127352 KB Output is correct
6 Correct 78 ms 127224 KB Output is correct
7 Correct 79 ms 127224 KB Output is correct
8 Correct 79 ms 127480 KB Output is correct
9 Correct 79 ms 127608 KB Output is correct
10 Correct 79 ms 127992 KB Output is correct
11 Correct 80 ms 128120 KB Output is correct
12 Correct 81 ms 127992 KB Output is correct
13 Correct 79 ms 127992 KB Output is correct
14 Correct 81 ms 128120 KB Output is correct
15 Correct 80 ms 128120 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 78 ms 127224 KB Output is correct
2 Correct 82 ms 127224 KB Output is correct
3 Correct 79 ms 127224 KB Output is correct
4 Correct 79 ms 127228 KB Output is correct
5 Correct 79 ms 127352 KB Output is correct
6 Correct 78 ms 127224 KB Output is correct
7 Correct 79 ms 127356 KB Output is correct
8 Correct 81 ms 127480 KB Output is correct
9 Correct 81 ms 127608 KB Output is correct
10 Correct 80 ms 127992 KB Output is correct
11 Correct 84 ms 128164 KB Output is correct
12 Correct 86 ms 127992 KB Output is correct
13 Correct 81 ms 127992 KB Output is correct
14 Correct 83 ms 128248 KB Output is correct
15 Correct 80 ms 128120 KB Output is correct
16 Correct 85 ms 128836 KB Output is correct
17 Correct 97 ms 133496 KB Output is correct
18 Correct 100 ms 140152 KB Output is correct
19 Correct 101 ms 141944 KB Output is correct
20 Correct 109 ms 141816 KB Output is correct
21 Correct 84 ms 130168 KB Output is correct
22 Correct 98 ms 140408 KB Output is correct
23 Correct 111 ms 139128 KB Output is correct
24 Correct 110 ms 141688 KB Output is correct
25 Correct 100 ms 141944 KB Output is correct
26 Correct 109 ms 142416 KB Output is correct
27 Correct 103 ms 142328 KB Output is correct
28 Correct 106 ms 143224 KB Output is correct
29 Correct 137 ms 146936 KB Output is correct
30 Correct 109 ms 143096 KB Output is correct
31 Correct 133 ms 144376 KB Output is correct
32 Correct 113 ms 143096 KB Output is correct
33 Correct 165 ms 150200 KB Output is correct
34 Correct 160 ms 150140 KB Output is correct

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 77 ms 127224 KB Output is correct
2 Correct 80 ms 127224 KB Output is correct
3 Correct 81 ms 127224 KB Output is correct
4 Correct 79 ms 127160 KB Output is correct
5 Correct 80 ms 127224 KB Output is correct
6 Correct 79 ms 127224 KB Output is correct
7 Correct 79 ms 127224 KB Output is correct
8 Correct 80 ms 127480 KB Output is correct
9 Correct 78 ms 127608 KB Output is correct
10 Correct 88 ms 127992 KB Output is correct
11 Correct 88 ms 128120 KB Output is correct
12 Correct 81 ms 127992 KB Output is correct
13 Correct 83 ms 127992 KB Output is correct
14 Correct 82 ms 128124 KB Output is correct
15 Correct 81 ms 128248 KB Output is correct
16 Correct 83 ms 128800 KB Output is correct
17 Correct 87 ms 133496 KB Output is correct
18 Correct 99 ms 140280 KB Output is correct
19 Correct 111 ms 141944 KB Output is correct
20 Correct 98 ms 141820 KB Output is correct
21 Correct 83 ms 130040 KB Output is correct
22 Correct 104 ms 140408 KB Output is correct
23 Correct 100 ms 139128 KB Output is correct
24 Correct 103 ms 141688 KB Output is correct
25 Correct 101 ms 141944 KB Output is correct
26 Correct 107 ms 142456 KB Output is correct
27 Correct 106 ms 142328 KB Output is correct
28 Correct 106 ms 143356 KB Output is correct
29 Correct 135 ms 147040 KB Output is correct
30 Correct 112 ms 143096 KB Output is correct
31 Correct 130 ms 144376 KB Output is correct
32 Correct 108 ms 143100 KB Output is correct
33 Correct 179 ms 150136 KB Output is correct
34 Correct 160 ms 150144 KB Output is correct
35 Correct 136 ms 142460 KB Output is correct
36 Correct 94 ms 136184 KB Output is correct
37 Correct 158 ms 150392 KB Output is correct
38 Correct 142 ms 149752 KB Output is correct
39 Correct 134 ms 149624 KB Output is correct
40 Correct 151 ms 149624 KB Output is correct
41 Correct 134 ms 149752 KB Output is correct
42 Correct 109 ms 143480 KB Output is correct
43 Correct 109 ms 143348 KB Output is correct
44 Correct 107 ms 142836 KB Output is correct
45 Correct 179 ms 159228 KB Output is correct
46 Correct 185 ms 159416 KB Output is correct

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 80 ms 127224 KB Output is correct
2 Correct 80 ms 127352 KB Output is correct
3 Correct 80 ms 127224 KB Output is correct
4 Correct 78 ms 127224 KB Output is correct
5 Correct 79 ms 127352 KB Output is correct
6 Correct 88 ms 127224 KB Output is correct
7 Correct 80 ms 127224 KB Output is correct
8 Correct 81 ms 127480 KB Output is correct
9 Correct 79 ms 127608 KB Output is correct
10 Correct 80 ms 127992 KB Output is correct
11 Correct 83 ms 128120 KB Output is correct
12 Correct 94 ms 127992 KB Output is correct
13 Correct 80 ms 127992 KB Output is correct
14 Correct 79 ms 128124 KB Output is correct
15 Correct 82 ms 128120 KB Output is correct
16 Correct 82 ms 128760 KB Output is correct
17 Correct 91 ms 133624 KB Output is correct
18 Correct 117 ms 140152 KB Output is correct
19 Correct 100 ms 141944 KB Output is correct
20 Correct 100 ms 141816 KB Output is correct
21 Correct 83 ms 130124 KB Output is correct
22 Correct 96 ms 140408 KB Output is correct
23 Correct 99 ms 139128 KB Output is correct
24 Correct 105 ms 141768 KB Output is correct
25 Correct 100 ms 141944 KB Output is correct
26 Correct 107 ms 142584 KB Output is correct
27 Correct 104 ms 142200 KB Output is correct
28 Correct 106 ms 143188 KB Output is correct
29 Correct 136 ms 146936 KB Output is correct
30 Correct 115 ms 143328 KB Output is correct
31 Correct 120 ms 144376 KB Output is correct
32 Correct 108 ms 143096 KB Output is correct
33 Correct 161 ms 150136 KB Output is correct
34 Correct 155 ms 150228 KB Output is correct
35 Correct 114 ms 142456 KB Output is correct
36 Correct 91 ms 136056 KB Output is correct
37 Correct 143 ms 150392 KB Output is correct
38 Correct 160 ms 149752 KB Output is correct
39 Correct 139 ms 149624 KB Output is correct
40 Correct 137 ms 149576 KB Output is correct
41 Correct 157 ms 149716 KB Output is correct
42 Correct 120 ms 143480 KB Output is correct
43 Correct 113 ms 143276 KB Output is correct
44 Correct 103 ms 142940 KB Output is correct
45 Correct 183 ms 159352 KB Output is correct
46 Correct 167 ms 159416 KB Output is correct
47 Runtime error 362 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
48 Halted 0 ms 0 KB -