Submission #543631

#	Time	Username	Problem	Language	Result	Execution time	Memory
543631		leductoan	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	1074 ms	168668 KiB

skyscraper

#include<bits/stdc++.h>

using namespace std;

#define task "DUT02XCRE"
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define zs(v) ((int)(v).size())
#define BIT(x, i) (((x) >> (i)) & 1)
#define CNTBIT __builtin_popcountll
#define ALL(v) (v).begin(),(v).end()
#define endl '\n'

typedef long double ld;
typedef long long ll;
typedef pair<int, int> pii;

const int dx[4]={-1, 0, 1, 0}, dy[4]={0, 1, 0, -1};
const int dxx[8]={-1, -1, 0, 1, 1, 1, 0, -1}, dyy[8]={0, 1, 1, 1, 0, -1, -1, -1};
const ll mod = 1000000007; /// 998244353
const ll base = 331;
const int N=30005;
const int M=175;

static struct FastInput {
  static constexpr int BUF_SIZE = 1 << 20;
  char buf[BUF_SIZE];
  size_t chars_read = 0;
  size_t buf_pos = 0;
  FILE *in = stdin;
  char cur = 0;

  inline char get_char() {
    if (buf_pos >= chars_read) {
      chars_read = fread(buf, 1, BUF_SIZE, in);
      buf_pos = 0;
      buf[0] = (chars_read == 0 ? -1 : buf[0]);
    }
    return cur = buf[buf_pos++];
  }

  inline void tie(int) {}

  inline explicit operator bool() {
    return cur != -1;
  }

  inline static bool is_blank(char c) {
    return c <= ' ';
  }

  inline bool skip_blanks() {
    while (is_blank(cur) && cur != -1) {
      get_char();
    }
    return cur != -1;
  }

  inline FastInput& operator>>(char& c) {
    skip_blanks();
    c = cur;
    return *this;
  }

  inline FastInput& operator>>(string& s) {
    if (skip_blanks()) {
      s.clear();
      do {
        s += cur;
      } while (!is_blank(get_char()));
    }
    return *this;
  }

  template <typename T>
  inline FastInput& read_integer(T& n) {
    // unsafe, doesn't check that characters are actually digits
    n = 0;
    if (skip_blanks()) {
      int sign = +1;
      if (cur == '-') {
        sign = -1;
        get_char();
      }
      do {
        n += n + (n << 3) + cur - '0';
      } while (!is_blank(get_char()));
      n *= sign;
    }
    return *this;
  }

  template <typename T>
  inline typename enable_if<is_integral<T>::value, FastInput&>::type operator>>(T& n) {
    return read_integer(n);
  }

  #if !defined(_WIN32) | defined(_WIN64)
  inline FastInput& operator>>(__int128& n) {
    return read_integer(n);
  }
  #endif

  template <typename T>
  inline typename enable_if<is_floating_point<T>::value, FastInput&>::type operator>>(T& n) {
    // not sure if really fast, for compatibility only
    n = 0;
    if (skip_blanks()) {
      string s;
      (*this) >> s;
      sscanf(s.c_str(), "%lf", &n);
    }
    return *this;
  }
} fast_input;

#define cin fast_input

static struct FastOutput {
  static constexpr int BUF_SIZE = 1 << 20;
  char buf[BUF_SIZE];
  size_t buf_pos = 0;
  static constexpr int TMP_SIZE = 1 << 20;
  char tmp[TMP_SIZE];
  FILE *out = stdout;

  inline void put_char(char c) {
    buf[buf_pos++] = c;
    if (buf_pos == BUF_SIZE) {
      fwrite(buf, 1, buf_pos, out);
      buf_pos = 0;
    }
  }

  ~FastOutput() {
    fwrite(buf, 1, buf_pos, out);
  }

  inline FastOutput& operator<<(char c) {
    put_char(c);
    return *this;
  }

  inline FastOutput& operator<<(const char* s) {
    while (*s) {
      put_char(*s++);
    }
    return *this;
  }

  inline FastOutput& operator<<(const string& s) {
    for (int i = 0; i < (int) s.size(); i++) {
      put_char(s[i]);
    }
    return *this;
  }

  template <typename T>
  inline char* integer_to_string(T n) {
    // beware of TMP_SIZE
    char* p = tmp + TMP_SIZE - 1;
    if (n == 0) {
      *--p = '0';
    } else {
      bool is_negative = false;
      if (n < 0) {
        is_negative = true;
        n = -n;
      }
      while (n > 0) {
        *--p = (char) ('0' + n % 10);
        n /= 10;
      }
      if (is_negative) {
        *--p = '-';
      }
    }
    return p;
  }

  template <typename T>
  inline typename enable_if<is_integral<T>::value, char*>::type stringify(T n) {
    return integer_to_string(n);
  }

  #if !defined(_WIN32) || defined(_WIN64)
  inline char* stringify(__int128 n) {
    return integer_to_string(n);
  }
  #endif

  template <typename T>
  inline typename enable_if<is_floating_point<T>::value, char*>::type stringify(T n) {
    sprintf(tmp, "%.17f", n);
    return tmp;
  }

  template <typename T>
  inline FastOutput& operator<<(const T& n) {
    auto p = stringify(n);
    for (; *p != 0; p++) {
      put_char(*p);
    }
    return *this;
  }
} fast_output;

#define cout fast_output
int n,m;
int p[N],b[N];
int id[N][M+5], cnt=0;
int f[N*M+5];
vector<pii> adj[N*M+5];
int occ[N];

void gogo()
{
    cin>>n>>m;
    for (int i=1;i<=m;++i) cin>>b[i]>>p[i], occ[b[i]]=p[i];
    for (int i=0;i<n;++i)
        for (int j=0;j<M;++j)
            id[i][j]=cnt++;

    for (int i=1;i<=m;++i)
        if (p[i]<M) adj[id[b[i]][0]].pb({id[b[i]][p[i]],0});


    for (int i=1;i<=m;++i) if (p[i]>=M)
    {
        for (int j=b[i]+p[i];j<n;j+=p[i]) if (occ[j])
            adj[id[b[i]][0]].pb(mp(id[j][0],(j-b[i])/p[i]));
        for (int j=b[i]-p[i];j>=0;j-=p[i]) if (occ[j])
            adj[id[b[i]][0]].pb(mp(id[j][0],(b[i]-j)/p[i]));
    }

//    for (pii i:adj[id[14][0]]) cout<<i.fi/M<<" "<<i.se<<endl;

    priority_queue<pii,vector<pii>,greater<pii>> q;
    for (int i=0;i<=cnt;++i) f[i]=1e9;
    f[id[b[1]][0]]=0;
    q.push(mp(0,id[b[1]][0]));
    while (q.size())
    {
        int u=q.top().se, len=q.top().fi;
//        cout<<u/M<<" "<<u%M<<" "<<len<<endl;
        q.pop();
        if (f[u]<len) continue;
        for (pii node:adj[u])
        {
            int v=node.fi;
            int w=node.se;
            if (f[v]>f[u]+w)
            {
                f[v]=f[u]+w;
                q.push(mp(f[v],v));
            }
        }
        int nu=u/M;
        for (pii node:adj[id[nu][0]])
        {
            int v=node.fi, w=node.se;
            if (f[v]>f[u]+w)
            {
                f[v]=f[u]+w;
                q.push(mp(f[v],v));
            }
        }
        int cur=u/M;
        int t=u%M;
        if (t>0&&t<M) for (int i:{-t,t})
        {
            if (cur+i>=0&&cur+i<n)
            {
                int nxt=cur+i;
                int v=id[nxt][t];
                if (f[v]>f[u]+1)
                {
                    f[v]=f[u]+1;
                    q.push(mp(f[v],v));
                }
            }
        }
        if (occ[cur]>0&&occ[cur]<M)
        {
            int t=occ[cur];
            for (int i:{-t,t})
            {
                if (cur+i>=0&&cur+i<n)
                {
                    int nxt=cur+i;
                    int v=id[nxt][t];
                    if (f[v]>f[u]+1)
                    {
                        f[v]=f[u]+1;
                        q.push(mp(f[v],v));
                    }
                }
            }
        }
    }

//    cout<<f[id[14][1]]<<endl;

//    int v=id[4][0];
//    while (v)
//    {
//        cout<<v/M<<" "<<v%M<<"\n";
//        v=trace[v];
//    }
    int ans=1e9;
    for (int j=0;j<M;++j) ans=min(ans,f[id[b[2]][j]]);
    cout<<(ans>1e8?-1:ans);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    if (fopen(task".inp", "r"))
    {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    gogo();
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:323:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  323 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:324:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  324 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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