Submission #124113

#	Time	Username	Problem	Language	Result	Execution time	Memory
124113		RafikHachana	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	0 / 100	2 ms	380 KiB

skyscraper

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

//#define int long long

vector<vector<int> > g;
int n,m;
vector<int> b,p;
vector<vector<int> > v;

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]> d + abs(b[it]-b[u])/p[u])
      {
        dist[it]=  d + abs(b[it]-b[u])/p[u];
        q.push({dist[it],it});
      }
    }
    for(int i=0)*/

    for(int j=b[u]-p[u];j>=0;j-=p[u])
    {
      for(auto it:v[j])
      {
        if(dist[it]> d + abs(b[it]-b[u])/p[u])
        {
          dist[it]=  d + abs(b[it]-b[u])/p[u];
          q.push({dist[it],it});
        }
      }
    }
    for(int j=b[u]+p[u];j<m;j+=p[u])
    {
      for(auto it:v[j])
      {
        if(dist[it]> d + abs(b[it]-b[u])/p[u])
        {
          dist[it]=  d + abs(b[it]-b[u])/p[u];
          q.push({dist[it],it});
        }
      }
    }
  }
  if(dist[1]==1e9) cout<<-1<<endl;
  else cout<<dist[1]<<endl;
}


main()
{
  cin>>m>>n;
  b.resize(n);
  p.resize(n);
  v.resize(m);
  for(int i=0;i<n;i++)
  {
    cin>>b[i]>>p[i];
    v[b[i]].push_back(i);
  }
  /*g.resize(n);
  for(int i=0;i<n;i++)
  {
    for(int j=i-p[i];j>=0;j-=p[i])
    {
      g[i].push_back(v[j]);
    }
    for(int j=i+p[i];j<m;j+=p[i])
    {
      g.push_back(v[j]);
    }
  }*/
  dijsktra();
}

Compilation message (stderr)

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

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