Submission #124194

#	Time	Username	Problem	Language	Result	Execution time	Memory
124194		RafikHachana	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	10 / 100	3 ms	376 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>,bool> vis;
vector<bool> vi;

int bfs()
{
  queue<pair<pair<int,int>,int> > q;
  q.push({{0,0},0});
  vis[{0,0}] = true;
  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});
      vis[{pos+power,power}] = true;
    }
    if(!vis[{pos-power,power}] && pos-power>=0)
    {
      q.push({{pos-power,power},d+1});
      vis[{pos-power,power}] = true;
    }
    if(!vi[pos])
    {
      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});
      }
      vi[pos] = true;
    }
  }
  return -1;
}


main()
{
  cin>>m>>n;
  b.resize(n);
  p.resize(n);
  v.resize(m);
  vi.assign(m,false);
  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:51: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