Submission #512579

#	Time	Username	Problem	Language	Result	Execution time	Memory
512579		CaoHuuKhuongDuy	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	781 ms	27360 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
const int N=3e4+9;
const int oo=1e9+9;
typedef pair <int,int> ii;
typedef pair <int,ii> iii;
int can,n,m,a[N],p[N],f[N][176];
bool First[N],check[N][176],doge[N],FIrst[N];
vector <int> num[N];
priority_queue <iii,vector<iii>,greater<iii> > q;
void update(int x,int dist,int val)
{
    if (f[x][dist]>val)
      {
        f[x][dist]=val;
        q.push({val,{x,dist}});
      }
    if (num[x].size()==0||dist==0) return;
}
int solve()
{
    if (p[1]>=can) 
      {
        f[a[1]][0]=0;
        q.push({0,{a[1],0}});
      }
    else 
      {
        f[a[1]][p[1]]=0;
        q.push({0,{a[1],p[1]}});
      }
    int val,x,dist;
    while (!q.empty())
      {
        val=q.top().first;
        x=q.top().second.first;
        dist=q.top().second.second;
        q.pop();
        if (x==a[2]) return f[x][dist];
       // cout<<x<<" "<<dist<<" "<<val<<" "<<q.size()<<endl;
        if (f[x][dist]!=val) continue;
        if (!First[x])
          {
            First[x]=true;
            for (int i=0;i<can;i++)
              if (check[x][i]||i==0) update(x,i,val);
          }
        if (dist!=0)
          {
            if (x+dist<=n) update(x+dist,dist,f[x][dist]+1);
            if (x-dist>=1) update(x-dist,dist,f[x][dist]+1);
            continue;
          }
        if (FIrst[x]) continue;
        FIrst[x]=true;
        for (int xnew:num[x])
          {
            int dem=0;
            for (int i=x+p[xnew];i<=n;i+=p[xnew])
            {
              // cout<<i<<endl;
              dem++;
              update(i,0,val+dem);
            }
            dem=0;
            for (int i=x-p[xnew];i>=1;i-=p[xnew])
            {
                //cout<<i<<endl;
              dem++;
              update(i,0,val+dem);
            }
          }
         // break;
      }
    int res=oo;
    for (int i=0;i<=can;i++)
      res=min(res,f[a[2]][i]);
    if (res==oo) res=-1;
    return res;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
  // freopen("test.inp","r",stdin);
    cin>>n>>m;
    can=sqrt(n);
    for (int i=0;i<=n;i++)
      for (int j=0;j<=can;j++)
        f[i][j]=oo;
    for (int i=1;i<=m;i++)
      {
        cin>>a[i]>>p[i];
        doge[a[i]]=true;
        a[i]++;
        if (p[i]>=can) num[a[i]].push_back(i);
        else check[a[i]][p[i]]=true;
      }
    cout<<solve();
    return 0;
}

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