oj.uz

Submission #543631

# Submission time Handle Problem Language Result Execution time Memory
543631 2022-03-31T04:34:37 Z leductoan Jakarta Skyscrapers (APIO15_skyscraper) C++14
57 / 100
 1000 ms 168668 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 123616 KB Output is correct
2 Correct 56 ms 123604 KB Output is correct
3 Correct 56 ms 123568 KB Output is correct
4 Correct 61 ms 123612 KB Output is correct
5 Correct 58 ms 123708 KB Output is correct
6 Correct 58 ms 123660 KB Output is correct
7 Correct 56 ms 123596 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 123572 KB Output is correct
2 Correct 55 ms 123596 KB Output is correct
3 Correct 66 ms 123672 KB Output is correct
4 Correct 56 ms 123640 KB Output is correct
5 Correct 61 ms 123596 KB Output is correct
6 Correct 59 ms 123568 KB Output is correct
7 Correct 57 ms 123680 KB Output is correct
8 Correct 58 ms 123668 KB Output is correct
9 Correct 56 ms 123668 KB Output is correct
10 Correct 61 ms 123932 KB Output is correct
11 Correct 62 ms 123892 KB Output is correct
12 Correct 66 ms 123864 KB Output is correct
13 Correct 57 ms 123792 KB Output is correct
14 Correct 59 ms 123836 KB Output is correct
15 Correct 62 ms 123848 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 123588 KB Output is correct
2 Correct 65 ms 123628 KB Output is correct
3 Correct 56 ms 123592 KB Output is correct
4 Correct 57 ms 123576 KB Output is correct
5 Correct 59 ms 123600 KB Output is correct
6 Correct 63 ms 123656 KB Output is correct
7 Correct 58 ms 123640 KB Output is correct
8 Correct 60 ms 123624 KB Output is correct
9 Correct 59 ms 123760 KB Output is correct
10 Correct 59 ms 123724 KB Output is correct
11 Correct 67 ms 123904 KB Output is correct
12 Correct 62 ms 123868 KB Output is correct
13 Correct 56 ms 123868 KB Output is correct
14 Correct 59 ms 123792 KB Output is correct
15 Correct 62 ms 124016 KB Output is correct
16 Correct 60 ms 123876 KB Output is correct
17 Correct 60 ms 124680 KB Output is correct
18 Correct 57 ms 126024 KB Output is correct
19 Correct 58 ms 126464 KB Output is correct
20 Correct 61 ms 126548 KB Output is correct
21 Correct 56 ms 124188 KB Output is correct
22 Correct 62 ms 126104 KB Output is correct
23 Correct 66 ms 125828 KB Output is correct
24 Correct 59 ms 126396 KB Output is correct
25 Correct 58 ms 126524 KB Output is correct
26 Correct 58 ms 126476 KB Output is correct
27 Correct 60 ms 126480 KB Output is correct
28 Correct 60 ms 126540 KB Output is correct
29 Correct 68 ms 126412 KB Output is correct
30 Correct 72 ms 126368 KB Output is correct
31 Correct 61 ms 126464 KB Output is correct
32 Correct 61 ms 126436 KB Output is correct
33 Correct 70 ms 126544 KB Output is correct
34 Correct 70 ms 126544 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 123572 KB Output is correct
2 Correct 63 ms 123616 KB Output is correct
3 Correct 63 ms 123660 KB Output is correct
4 Correct 57 ms 123648 KB Output is correct
5 Correct 57 ms 123668 KB Output is correct
6 Correct 56 ms 123676 KB Output is correct
7 Correct 57 ms 123596 KB Output is correct
8 Correct 62 ms 123648 KB Output is correct
9 Correct 58 ms 123724 KB Output is correct
10 Correct 56 ms 123724 KB Output is correct
11 Correct 60 ms 123852 KB Output is correct
12 Correct 69 ms 123844 KB Output is correct
13 Correct 60 ms 123912 KB Output is correct
14 Correct 56 ms 123824 KB Output is correct
15 Correct 57 ms 123840 KB Output is correct
16 Correct 58 ms 123852 KB Output is correct
17 Correct 61 ms 124816 KB Output is correct
18 Correct 66 ms 126220 KB Output is correct
19 Correct 68 ms 126472 KB Output is correct
20 Correct 60 ms 126540 KB Output is correct
21 Correct 58 ms 124348 KB Output is correct
22 Correct 58 ms 126148 KB Output is correct
23 Correct 61 ms 125836 KB Output is correct
24 Correct 61 ms 126372 KB Output is correct
25 Correct 67 ms 126504 KB Output is correct
26 Correct 60 ms 126476 KB Output is correct
27 Correct 58 ms 126476 KB Output is correct
28 Correct 61 ms 126448 KB Output is correct
29 Correct 65 ms 126464 KB Output is correct
30 Correct 75 ms 126360 KB Output is correct
31 Correct 62 ms 126388 KB Output is correct
32 Correct 61 ms 126496 KB Output is correct
33 Correct 69 ms 126532 KB Output is correct
34 Correct 70 ms 126524 KB Output is correct
35 Correct 72 ms 126672 KB Output is correct
36 Correct 62 ms 125264 KB Output is correct
37 Correct 95 ms 127704 KB Output is correct
38 Correct 79 ms 127876 KB Output is correct
39 Correct 81 ms 127880 KB Output is correct
40 Correct 80 ms 128032 KB Output is correct
41 Correct 88 ms 127988 KB Output is correct
42 Correct 64 ms 127368 KB Output is correct
43 Correct 61 ms 127364 KB Output is correct
44 Correct 59 ms 127476 KB Output is correct
45 Correct 101 ms 127576 KB Output is correct
46 Correct 105 ms 127588 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 123672 KB Output is correct
2 Correct 59 ms 123620 KB Output is correct
3 Correct 62 ms 123588 KB Output is correct
4 Correct 59 ms 123664 KB Output is correct
5 Correct 57 ms 123604 KB Output is correct
6 Correct 61 ms 123588 KB Output is correct
7 Correct 55 ms 123680 KB Output is correct
8 Correct 56 ms 123620 KB Output is correct
9 Correct 67 ms 123764 KB Output is correct
10 Correct 71 ms 123820 KB Output is correct
11 Correct 60 ms 123852 KB Output is correct
12 Correct 59 ms 123764 KB Output is correct
13 Correct 58 ms 123868 KB Output is correct
14 Correct 62 ms 123876 KB Output is correct
15 Correct 66 ms 123900 KB Output is correct
16 Correct 62 ms 123976 KB Output is correct
17 Correct 70 ms 124804 KB Output is correct
18 Correct 58 ms 126140 KB Output is correct
19 Correct 59 ms 126372 KB Output is correct
20 Correct 59 ms 126548 KB Output is correct
21 Correct 58 ms 124164 KB Output is correct
22 Correct 67 ms 126140 KB Output is correct
23 Correct 74 ms 125828 KB Output is correct
24 Correct 61 ms 126384 KB Output is correct
25 Correct 58 ms 126412 KB Output is correct
26 Correct 59 ms 126496 KB Output is correct
27 Correct 70 ms 126472 KB Output is correct
28 Correct 61 ms 126540 KB Output is correct
29 Correct 70 ms 126412 KB Output is correct
30 Correct 67 ms 126336 KB Output is correct
31 Correct 66 ms 126512 KB Output is correct
32 Correct 60 ms 126376 KB Output is correct
33 Correct 69 ms 126476 KB Output is correct
34 Correct 68 ms 126540 KB Output is correct
35 Correct 70 ms 126756 KB Output is correct
36 Correct 66 ms 125260 KB Output is correct
37 Correct 100 ms 127676 KB Output is correct
38 Correct 83 ms 127896 KB Output is correct
39 Correct 80 ms 127988 KB Output is correct
40 Correct 82 ms 127936 KB Output is correct
41 Correct 87 ms 127912 KB Output is correct
42 Correct 65 ms 127416 KB Output is correct
43 Correct 65 ms 127360 KB Output is correct
44 Correct 67 ms 127420 KB Output is correct
45 Correct 111 ms 127652 KB Output is correct
46 Correct 110 ms 127564 KB Output is correct
47 Correct 300 ms 145056 KB Output is correct
48 Correct 80 ms 157412 KB Output is correct
49 Correct 82 ms 160228 KB Output is correct
50 Correct 95 ms 163232 KB Output is correct
51 Correct 146 ms 167636 KB Output is correct
52 Correct 157 ms 167568 KB Output is correct
53 Correct 90 ms 166348 KB Output is correct
54 Correct 82 ms 165284 KB Output is correct
55 Correct 88 ms 165336 KB Output is correct
56 Correct 92 ms 167032 KB Output is correct
57 Correct 182 ms 165600 KB Output is correct
58 Correct 95 ms 166076 KB Output is correct
59 Correct 95 ms 166344 KB Output is correct
60 Correct 97 ms 166468 KB Output is correct
61 Correct 95 ms 166512 KB Output is correct
62 Correct 183 ms 168668 KB Output is correct
63 Correct 86 ms 166348 KB Output is correct
64 Correct 85 ms 166060 KB Output is correct
65 Correct 380 ms 166292 KB Output is correct
66 Execution timed out 1074 ms 166488 KB Time limit exceeded
67 Halted 0 ms 0 KB -