Submission #511362

#	Time	Username	Problem	Language	Result	Execution time	Memory
511362		CaoHuuKhuongDuy	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	1032 ms	27500 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
#define gc() (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS++)) : *iS++)
namespace IO {
  const int SIZE = 1 << 23;
  char ibuf[SIZE], *iS, *iT;
  char obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1;
  bool flush() {
    fwrite(obuf, 1, oS - obuf, stdout);
    oS = obuf;
    return true;
  }
  #define gc() (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS++)) : *iS++)
  #define pc(x) (*oS++ = x) 
  int read() {
    int x = 0, f = 0;
    char c = gc();
    while (!isdigit(c)) f |= c == '-', c = gc();
    while (isdigit(c)) x = 10 * x + c - '0', c = gc();
    return f ? -x : x;
  }
  char qu[55]; int qlen;
  template <class T> void print(T x) {
    if (!x) pc('0');
    if (x < 0) pc('-'), x = -x;
    while (x) qu[++qlen] = x % 10 + '0', x /= 10;
    while (qlen) pc(qu[qlen--]);
  }
  template <class T> void print(T x, char charset) {
    print(x), pc(charset);
  }
  struct Flusher {
    ~Flusher() {
      flush();
    }
  } flusher;
}
using namespace IO;
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];
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];
        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);
          }
        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])
            {
              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;
    n=read();
    m=read();
    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++)
      {
        a[i]=read();
        p[i]=read();
        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: 0 / 43