Submission #124162

#	Time	Username	Problem	Language	Result	Execution time	Memory
124162		RafikHachana	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	0 / 100	1045 ms	262148 KiB

skyscraper

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

//#define int long long

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

int target;

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().second;
    int pos= q.front().first.first;
    int power = q.front().first.second;
    q.pop();
    if(pos==target) return d;
    if(!vis[{pos+power,power}] && power+pos<m) q.push({{pos+power,power},d+1});
    if(!vis[{pos-power,power}] && pos-power>=0) q.push({{pos-power,power},d+1});
    for(auto it:v[pos])
    {
      if(!vis[{pos+it,it}] && it+pos<m) q.push({{pos+it,it},d+1});
      if(!vis[{pos-it,it}] && pos-it>=0) q.push({{pos-it,it},d+1});
    }
  }
  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]].insert(p[i]);
    if(i==1) target = b[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:37: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