Submission #124146

#	Time	Username	Problem	Language	Result	Execution time	Memory
124146		RafikHachana	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	10 / 100	86 ms	25300 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;
}

map<pair<int,int>,int> vis;

int bfs()
{
  queue<pair<pair<int,int>,int> > q;
  q.push({{0,0},0});
  while(!q.empty())
  {
    int d = q.front().first.first;
    int u = q.front().first.second;
    int doge = q.front().second;
    q.pop();
    if(!vis[{u+p[doge],doge}] && u+p[doge]<m) q.push({{d+1,u+p[doge]},doge});
    if(!vis[{u-p[doge],doge}] && u-p[doge]>=0) q.push({{d+1,u-p[doge]},doge});
    for(auto it:v[u])
    {
      if(!vis[{u+p[it],it}] && u+p[it]<m) q.push({{d+1,u+p[it]},it});
      if(!vis[{u-p[it],it}] && u-p[it]>=0) q.push({{d+1,u-p[it]},it});
      if(it==1) return d;
    }
  }
  return -1;
}


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]);
    }
  }*/
  cout<<bfs()<<endl;
}

Compilation message (stderr)

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

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