Submission #511220

#	Time	Username	Problem	Language	Result	Execution time	Memory
511220		CaoHuuKhuongDuy	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	0 / 100	2 ms	1000 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];
vector <int> num[N];
queue <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;
    update(x,0,val);
}
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]}});
      }
     // cout<<f[1][0]<<endl;
    int val,x,dist;
    // for (int i=0;i<=can;i++)
    // {
    //   //res=min(res,f[a[n]][i]);
    //   cout<<f[a[n]][i]<<endl;
    // }
    while (!q.empty())
      {
        val=q.front().first;
        x=q.front().second.first;
        dist=q.front().second.second;
        q.pop();
        if (f[x][dist]!=val) continue;
        //cout<<x<<" "<<dist<<" "<<f[x][dist]<<endl;
        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;
          }
        for (int xnew:num[x])
          {
            int dem=0;
            for (int i=x;i<=n;i+=p[xnew])
              {
                update(i,0,dem++);
              }
            dem=0;
            for (int i=x;i>=1;i-=p[xnew])
              update(i,0,dem++);
            //   f[i][0]=min(f[i][0],dem++);
          }
      }
     // cout<<f[5][1]<<"sdsd"<<endl;
    int res=oo;
    //cout<<f[1][2]<<endl;
    for (int i=0;i<=can;i++)
    {
      res=min(res,f[a[2]][i]);
     // cout<<f[a[2]][i]<<endl;
    }
    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;
       // cout<<i<<" "<<j<<" "<<f[i][j]<<" "<<oo<<endl;
      }
     // return 0;
        //cout<<f[4][0]<<endl;
    for (int i=1;i<=m;i++)
      {
        cin>>a[i]>>p[i];
        a[i]++;
        if (p[i]>=can) num[a[i]].push_back(i);
        else check[a[i]][p[i]]=true;
            // f[a[i]][0]=0;
            // q.push({0,{a[i],0}});
        //   }
        // else 
        //   {
        //     f[a[i]][p[i]]=0;
        //     q.push({0,{a[i],p[i]}});
        //   }
      }
    cout<<solve();
    return 0;
}

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