#include <bits/stdc++.h>
using namespace std;
int const N=2005;
int const M=30005;
int const inf=1e9;
vector<pair<int,int>> adj[N];
int n,m;
int B[M],P[M];
int dist[N];
vector<int> doge[N];
int main(){
cin>>n>>m;
for (int i = 0; i < m; ++i){
cin>>B[i]>>P[i];
doge[B[i]].push_back(P[i]);
}
int di=0;
for (int i = 0; i < n; ++i){
sort(doge[i].begin(), doge[i].end());
reverse(doge[i].begin(), doge[i].end());
for (int j = 0; j < n; ++j)
{
if(i==j)
continue;
doge[i].push_back(-1);
di=abs(i-j);
for(int p=0;p<(doge[i].size())-1;p++)
if(doge[i][p]!=doge[i][p+1] && di%doge[i][p]==0){
adj[i].push_back({j,di/doge[i][p]});
break;
}
}
}
for (int i = 0; i < N; ++i)
dist[i]=inf;
set<pair<int,int>> d;
dist[B[0]]=0;
d.insert({0,B[0]});
while(d.size()){
auto p=*(d.begin());
int node=p.second;
int dis=p.first;
d.erase(d.begin());
for(auto i:adj[node]){
if(dist[i.first]>dis+i.second){
dist[i.first]=dis+i.second;
d.insert({dist[i.first],i.first});
}
}
}
if(dist[B[1]]==inf)
dist[B[1]]=-1;
cout<<dist[B[1]]<<endl;
}
Compilation message
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:27:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
27 | for(int p=0;p<(doge[i].size())-1;p++)
| ~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
536 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
1 ms |
348 KB |
Output is correct |
| 10 |
Correct |
1 ms |
604 KB |
Output is correct |
| 11 |
Correct |
1 ms |
604 KB |
Output is correct |
| 12 |
Correct |
2 ms |
604 KB |
Output is correct |
| 13 |
Correct |
1 ms |
604 KB |
Output is correct |
| 14 |
Correct |
1 ms |
604 KB |
Output is correct |
| 15 |
Correct |
1 ms |
604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
540 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
1 ms |
604 KB |
Output is correct |
| 11 |
Correct |
1 ms |
604 KB |
Output is correct |
| 12 |
Correct |
1 ms |
604 KB |
Output is correct |
| 13 |
Correct |
1 ms |
604 KB |
Output is correct |
| 14 |
Correct |
1 ms |
604 KB |
Output is correct |
| 15 |
Correct |
1 ms |
604 KB |
Output is correct |
| 16 |
Correct |
2 ms |
796 KB |
Output is correct |
| 17 |
Correct |
72 ms |
3756 KB |
Output is correct |
| 18 |
Correct |
941 ms |
14876 KB |
Output is correct |
| 19 |
Execution timed out |
1052 ms |
13076 KB |
Time limit exceeded |
| 20 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
344 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
1 ms |
604 KB |
Output is correct |
| 11 |
Correct |
1 ms |
604 KB |
Output is correct |
| 12 |
Correct |
2 ms |
604 KB |
Output is correct |
| 13 |
Correct |
1 ms |
604 KB |
Output is correct |
| 14 |
Correct |
1 ms |
604 KB |
Output is correct |
| 15 |
Correct |
1 ms |
612 KB |
Output is correct |
| 16 |
Correct |
2 ms |
708 KB |
Output is correct |
| 17 |
Correct |
73 ms |
3776 KB |
Output is correct |
| 18 |
Correct |
899 ms |
14576 KB |
Output is correct |
| 19 |
Execution timed out |
1056 ms |
14256 KB |
Time limit exceeded |
| 20 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
1 ms |
344 KB |
Output is correct |
| 9 |
Correct |
1 ms |
348 KB |
Output is correct |
| 10 |
Correct |
1 ms |
604 KB |
Output is correct |
| 11 |
Correct |
1 ms |
604 KB |
Output is correct |
| 12 |
Correct |
1 ms |
604 KB |
Output is correct |
| 13 |
Correct |
1 ms |
604 KB |
Output is correct |
| 14 |
Correct |
1 ms |
644 KB |
Output is correct |
| 15 |
Correct |
1 ms |
604 KB |
Output is correct |
| 16 |
Correct |
2 ms |
604 KB |
Output is correct |
| 17 |
Correct |
73 ms |
3668 KB |
Output is correct |
| 18 |
Correct |
875 ms |
14452 KB |
Output is correct |
| 19 |
Execution timed out |
1029 ms |
13000 KB |
Time limit exceeded |
| 20 |
Halted |
0 ms |
0 KB |
- |
