Submission #124074

#	Time	Username	Problem	Language	Result	Execution time	Memory
124074		RafikHachana	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	36 / 100	1080 ms	64780 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;

#define int long long

vector<vector<pair<int,int> > > g;
int n,m;

void dijsktra()
{
  vector<int> dist(n,1e9);
  priority_queue<pair<int,int> , vector<pair<int,int> > , greater<pair<int,int> > > q;
  q.push({0,0});
  dist[0] = 0;
  while(!q.empty())
  {
    int d = q.top().first;
    int u = q.top().second;
    q.pop();
    for(auto it:g[u])
    {
      if(dist[it.second]> d + it.first)
      {
        dist[it.second] =  d + it.first;
        q.push({dist[it.second],it.second});
      }
    }
  }
  if(dist[1]==1e9) cout<<-1<<endl;
  else cout<<dist[1]<<endl;
}


main()
{
  cin>>m>>n;
  vector<int> b(n),p(n);
  for(int i=0;i<n;i++)
  {
    cin>>b[i]>>p[i];
  }
  g.resize(n);
  for(int i=0;i<n;i++)
  {
    for(int j=0;j<n;j++)
    {
      if(i==j) continue;
      if(b[i]%p[i]==b[j]%p[i]) g[i].push_back({abs(b[j]-b[i])/p[i],j});
    }
  }
  dijsktra();
}

Compilation message (stderr)

skyscraper.cpp:34:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 14 / 14
• Subtask 4: 0 / 21
• Subtask 5: 0 / 43