#include <bits/stdc++.h>
#define MT make_tuple
using namespace std;
typedef tuple<int,int,int> trinca;
const int MAXN = 30010;
const int BUCKET = 175;
vector<trinca> grafo[MAXN][BUCKET];
int processado[MAXN][BUCKET],N,M,origem,destino;
int main(){
scanf("%d %d",&N,&M);
for(int i = 0;i<M;i++){
int B,P;
scanf("%d %d",&B,&P);
if(i == 0) origem = B;
else if(i == 1) destino = B;
if(P < BUCKET){
grafo[B][0].push_back(MT(B,P,0));
}
else{
for(int j = 1;B - j*P >= 0;j++){
grafo[B][0].push_back(MT(B - j*P,0,j));
}
for(int j = 1;B + j*P < N;j++){
grafo[B][0].push_back(MT(B + j*P,0,j));
}
}
}
priority_queue<trinca, vector<trinca>, greater<trinca> > Dijkstra;
Dijkstra.push(MT(0,origem,0));
while(!Dijkstra.empty()){
trinca davez = Dijkstra.top();
Dijkstra.pop();
int dist = get<0>(davez), v = get<1>(davez), power = get<2>(davez);
if(processado[v][power]) continue;
processado[v][power] = 1;
if(!processado[v][0]){
Dijkstra.push(MT(dist,v,0));
}
if(power < BUCKET && v - power >= 0){
if(!processado[v - power][power]) Dijkstra.push(MT(dist+1,v - power,power));
}
if(power < BUCKET && v + power < N){
if(!processado[v + power][power]) Dijkstra.push(MT(dist+1,v + power,power));
}
if(v == destino){
printf("%d\n",dist);
return 0;
}
for(trinca nova : grafo[v][power]){
int nv = get<0>(nova), npower = get<1>(nova), nadd = get<2>(nova);
if(!processado[nv][npower]) Dijkstra.push(MT(dist+nadd,nv,npower));
}
}
printf("-1\n");
return 0;
}
Compilation message
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:10:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&N,&M);
^
skyscraper.cpp:13:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&B,&P);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
100 ms |
123640 KB |
Output is correct |
| 2 |
Correct |
101 ms |
123640 KB |
Output is correct |
| 3 |
Correct |
102 ms |
123876 KB |
Output is correct |
| 4 |
Correct |
103 ms |
123876 KB |
Output is correct |
| 5 |
Correct |
103 ms |
123884 KB |
Output is correct |
| 6 |
Correct |
114 ms |
123884 KB |
Output is correct |
| 7 |
Correct |
116 ms |
123884 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
100 ms |
123884 KB |
Output is correct |
| 2 |
Correct |
102 ms |
123884 KB |
Output is correct |
| 3 |
Correct |
101 ms |
123884 KB |
Output is correct |
| 4 |
Correct |
102 ms |
123884 KB |
Output is correct |
| 5 |
Correct |
101 ms |
123996 KB |
Output is correct |
| 6 |
Correct |
119 ms |
123996 KB |
Output is correct |
| 7 |
Correct |
105 ms |
123996 KB |
Output is correct |
| 8 |
Correct |
104 ms |
123996 KB |
Output is correct |
| 9 |
Correct |
119 ms |
123996 KB |
Output is correct |
| 10 |
Correct |
115 ms |
124028 KB |
Output is correct |
| 11 |
Correct |
105 ms |
124028 KB |
Output is correct |
| 12 |
Correct |
102 ms |
124028 KB |
Output is correct |
| 13 |
Correct |
104 ms |
124028 KB |
Output is correct |
| 14 |
Correct |
105 ms |
124248 KB |
Output is correct |
| 15 |
Correct |
102 ms |
124248 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
106 ms |
124248 KB |
Output is correct |
| 2 |
Correct |
108 ms |
124248 KB |
Output is correct |
| 3 |
Correct |
102 ms |
124248 KB |
Output is correct |
| 4 |
Correct |
103 ms |
124248 KB |
Output is correct |
| 5 |
Correct |
103 ms |
124248 KB |
Output is correct |
| 6 |
Correct |
103 ms |
124248 KB |
Output is correct |
| 7 |
Correct |
108 ms |
124248 KB |
Output is correct |
| 8 |
Correct |
102 ms |
124248 KB |
Output is correct |
| 9 |
Correct |
132 ms |
124248 KB |
Output is correct |
| 10 |
Correct |
107 ms |
124248 KB |
Output is correct |
| 11 |
Correct |
111 ms |
124248 KB |
Output is correct |
| 12 |
Correct |
101 ms |
124248 KB |
Output is correct |
| 13 |
Correct |
105 ms |
124248 KB |
Output is correct |
| 14 |
Correct |
103 ms |
124248 KB |
Output is correct |
| 15 |
Correct |
106 ms |
124248 KB |
Output is correct |
| 16 |
Correct |
108 ms |
124248 KB |
Output is correct |
| 17 |
Correct |
107 ms |
124632 KB |
Output is correct |
| 18 |
Correct |
101 ms |
124632 KB |
Output is correct |
| 19 |
Correct |
105 ms |
124632 KB |
Output is correct |
| 20 |
Correct |
108 ms |
125396 KB |
Output is correct |
| 21 |
Correct |
104 ms |
125396 KB |
Output is correct |
| 22 |
Correct |
104 ms |
125396 KB |
Output is correct |
| 23 |
Correct |
109 ms |
125396 KB |
Output is correct |
| 24 |
Correct |
110 ms |
125396 KB |
Output is correct |
| 25 |
Correct |
106 ms |
125396 KB |
Output is correct |
| 26 |
Correct |
103 ms |
125396 KB |
Output is correct |
| 27 |
Correct |
106 ms |
125396 KB |
Output is correct |
| 28 |
Correct |
106 ms |
125396 KB |
Output is correct |
| 29 |
Correct |
117 ms |
125436 KB |
Output is correct |
| 30 |
Correct |
106 ms |
125436 KB |
Output is correct |
| 31 |
Correct |
108 ms |
125436 KB |
Output is correct |
| 32 |
Correct |
108 ms |
125436 KB |
Output is correct |
| 33 |
Correct |
125 ms |
125436 KB |
Output is correct |
| 34 |
Correct |
124 ms |
125436 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
115 ms |
125436 KB |
Output is correct |
| 2 |
Correct |
101 ms |
125436 KB |
Output is correct |
| 3 |
Correct |
103 ms |
125436 KB |
Output is correct |
| 4 |
Correct |
118 ms |
125436 KB |
Output is correct |
| 5 |
Correct |
105 ms |
125436 KB |
Output is correct |
| 6 |
Correct |
102 ms |
125436 KB |
Output is correct |
| 7 |
Correct |
102 ms |
125436 KB |
Output is correct |
| 8 |
Correct |
102 ms |
125436 KB |
Output is correct |
| 9 |
Correct |
102 ms |
125436 KB |
Output is correct |
| 10 |
Correct |
104 ms |
125436 KB |
Output is correct |
| 11 |
Correct |
102 ms |
125436 KB |
Output is correct |
| 12 |
Correct |
102 ms |
125436 KB |
Output is correct |
| 13 |
Correct |
103 ms |
125436 KB |
Output is correct |
| 14 |
Correct |
103 ms |
125436 KB |
Output is correct |
| 15 |
Correct |
102 ms |
125436 KB |
Output is correct |
| 16 |
Correct |
101 ms |
125436 KB |
Output is correct |
| 17 |
Correct |
104 ms |
125436 KB |
Output is correct |
| 18 |
Correct |
102 ms |
125436 KB |
Output is correct |
| 19 |
Correct |
102 ms |
125436 KB |
Output is correct |
| 20 |
Correct |
104 ms |
125436 KB |
Output is correct |
| 21 |
Correct |
102 ms |
125436 KB |
Output is correct |
| 22 |
Correct |
104 ms |
125436 KB |
Output is correct |
| 23 |
Correct |
105 ms |
125436 KB |
Output is correct |
| 24 |
Correct |
108 ms |
125436 KB |
Output is correct |
| 25 |
Correct |
102 ms |
125436 KB |
Output is correct |
| 26 |
Correct |
104 ms |
125436 KB |
Output is correct |
| 27 |
Correct |
103 ms |
125436 KB |
Output is correct |
| 28 |
Correct |
108 ms |
125436 KB |
Output is correct |
| 29 |
Correct |
119 ms |
125452 KB |
Output is correct |
| 30 |
Correct |
105 ms |
125452 KB |
Output is correct |
| 31 |
Correct |
110 ms |
125452 KB |
Output is correct |
| 32 |
Correct |
106 ms |
125452 KB |
Output is correct |
| 33 |
Correct |
124 ms |
125452 KB |
Output is correct |
| 34 |
Correct |
114 ms |
125452 KB |
Output is correct |
| 35 |
Correct |
118 ms |
125612 KB |
Output is correct |
| 36 |
Correct |
104 ms |
125612 KB |
Output is correct |
| 37 |
Correct |
119 ms |
126364 KB |
Output is correct |
| 38 |
Correct |
115 ms |
126364 KB |
Output is correct |
| 39 |
Correct |
114 ms |
126364 KB |
Output is correct |
| 40 |
Correct |
114 ms |
126364 KB |
Output is correct |
| 41 |
Correct |
114 ms |
126364 KB |
Output is correct |
| 42 |
Correct |
115 ms |
126364 KB |
Output is correct |
| 43 |
Correct |
110 ms |
126364 KB |
Output is correct |
| 44 |
Correct |
154 ms |
126364 KB |
Output is correct |
| 45 |
Correct |
222 ms |
130048 KB |
Output is correct |
| 46 |
Correct |
187 ms |
130048 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
104 ms |
130048 KB |
Output is correct |
| 2 |
Correct |
102 ms |
130048 KB |
Output is correct |
| 3 |
Correct |
103 ms |
130048 KB |
Output is correct |
| 4 |
Correct |
101 ms |
130048 KB |
Output is correct |
| 5 |
Correct |
100 ms |
130048 KB |
Output is correct |
| 6 |
Correct |
108 ms |
130048 KB |
Output is correct |
| 7 |
Correct |
100 ms |
130048 KB |
Output is correct |
| 8 |
Correct |
102 ms |
130048 KB |
Output is correct |
| 9 |
Correct |
103 ms |
130048 KB |
Output is correct |
| 10 |
Correct |
107 ms |
130048 KB |
Output is correct |
| 11 |
Correct |
103 ms |
130048 KB |
Output is correct |
| 12 |
Correct |
104 ms |
130048 KB |
Output is correct |
| 13 |
Correct |
103 ms |
130048 KB |
Output is correct |
| 14 |
Correct |
104 ms |
130048 KB |
Output is correct |
| 15 |
Correct |
105 ms |
130048 KB |
Output is correct |
| 16 |
Correct |
102 ms |
130048 KB |
Output is correct |
| 17 |
Correct |
105 ms |
130048 KB |
Output is correct |
| 18 |
Correct |
102 ms |
130048 KB |
Output is correct |
| 19 |
Correct |
102 ms |
130048 KB |
Output is correct |
| 20 |
Correct |
105 ms |
130048 KB |
Output is correct |
| 21 |
Correct |
101 ms |
130048 KB |
Output is correct |
| 22 |
Correct |
103 ms |
130048 KB |
Output is correct |
| 23 |
Correct |
111 ms |
130048 KB |
Output is correct |
| 24 |
Correct |
105 ms |
130048 KB |
Output is correct |
| 25 |
Correct |
102 ms |
130048 KB |
Output is correct |
| 26 |
Correct |
105 ms |
130048 KB |
Output is correct |
| 27 |
Correct |
104 ms |
130048 KB |
Output is correct |
| 28 |
Correct |
105 ms |
130048 KB |
Output is correct |
| 29 |
Correct |
121 ms |
130048 KB |
Output is correct |
| 30 |
Correct |
105 ms |
130048 KB |
Output is correct |
| 31 |
Correct |
109 ms |
130048 KB |
Output is correct |
| 32 |
Correct |
105 ms |
130048 KB |
Output is correct |
| 33 |
Correct |
124 ms |
130048 KB |
Output is correct |
| 34 |
Correct |
117 ms |
130048 KB |
Output is correct |
| 35 |
Correct |
114 ms |
130048 KB |
Output is correct |
| 36 |
Correct |
104 ms |
130048 KB |
Output is correct |
| 37 |
Correct |
117 ms |
130048 KB |
Output is correct |
| 38 |
Correct |
118 ms |
130048 KB |
Output is correct |
| 39 |
Correct |
129 ms |
130048 KB |
Output is correct |
| 40 |
Correct |
113 ms |
130048 KB |
Output is correct |
| 41 |
Correct |
116 ms |
130048 KB |
Output is correct |
| 42 |
Correct |
109 ms |
130048 KB |
Output is correct |
| 43 |
Correct |
112 ms |
130048 KB |
Output is correct |
| 44 |
Correct |
110 ms |
130048 KB |
Output is correct |
| 45 |
Correct |
219 ms |
130048 KB |
Output is correct |
| 46 |
Correct |
195 ms |
130048 KB |
Output is correct |
| 47 |
Correct |
139 ms |
137952 KB |
Output is correct |
| 48 |
Correct |
120 ms |
137952 KB |
Output is correct |
| 49 |
Correct |
117 ms |
137952 KB |
Output is correct |
| 50 |
Correct |
111 ms |
137952 KB |
Output is correct |
| 51 |
Correct |
155 ms |
148480 KB |
Output is correct |
| 52 |
Correct |
158 ms |
148796 KB |
Output is correct |
| 53 |
Correct |
119 ms |
148796 KB |
Output is correct |
| 54 |
Correct |
124 ms |
148796 KB |
Output is correct |
| 55 |
Correct |
126 ms |
148796 KB |
Output is correct |
| 56 |
Correct |
146 ms |
148796 KB |
Output is correct |
| 57 |
Correct |
105 ms |
148796 KB |
Output is correct |
| 58 |
Correct |
142 ms |
148796 KB |
Output is correct |
| 59 |
Correct |
142 ms |
148796 KB |
Output is correct |
| 60 |
Correct |
138 ms |
148796 KB |
Output is correct |
| 61 |
Correct |
135 ms |
148796 KB |
Output is correct |
| 62 |
Correct |
174 ms |
151168 KB |
Output is correct |
| 63 |
Correct |
553 ms |
193240 KB |
Output is correct |
| 64 |
Correct |
649 ms |
206848 KB |
Output is correct |
| 65 |
Execution timed out |
1070 ms |
213468 KB |
Time limit exceeded |
| 66 |
Halted |
0 ms |
0 KB |
- |
