oj.uz

Submission #166852

# Submission time Handle Problem Language Result Execution time Memory
166852 2019-12-04T10:51:15 Z Hideo Jakarta Skyscrapers (APIO15_skyscraper) C++14
57 / 100
 1000 ms 63856 KB 
#include <bits/stdc++.h>
using namespace std;

int n, m;
int pw[100005];
int pos[100005];
vector <int> doges[100005];

int dist[50005][300];

priority_queue<pair<int,pair<int,int> > > pq;

int main() {
  scanf("%d %d", &n, &m);
  for (int i = 0; i < m; i++) {
    scanf("%d %d", &pos[i], &pw[i]);
    doges[pos[i]].push_back(i);
  }

  for (int i = 0; i <= 50000; i++) {
    for (int j = 0; j < 300; j++) {
      dist[i][j] = 1000000000;
    }
  }
  pq.push(make_pair(0, make_pair(pos[0], 0)));
  dist[pos[0]][0] = 0;
  int limit = (int) sqrt(n);
  int res = 1000000000;

  while (!pq.empty()) {
    pair<int,pair<int,int> > now = pq.top();
    pq.pop();
    int posnow = now.second.first;
    int distnow = -now.first;
    if (posnow == pos[1]) {
      res = min(res, distnow);
    }
    int pownow = now.second.second;
    if (pownow == 0) {
      for (int i = 0; i < (int)doges[posnow].size(); i++) {
        if (pw[doges[posnow][i]] <= limit) {
          pair <int,pair<int,int> > nxt;
          if (dist[posnow][pw[doges[posnow][i]]] > distnow) {
            dist[posnow][pw[doges[posnow][i]]] = distnow;
            int distnext = distnow;
            pq.push(make_pair(-distnext, make_pair(posnow, pw[doges[posnow][i]])));
          }
        } else {
          int powernow = pw[doges[posnow][i]];
          for (int j = 1; posnow - j*powernow >= 0; ++j) {
            int posnext = posnow - j*powernow;
            int distnext = distnow + j;
            if (dist[posnext][0] > distnext) {
              dist[posnext][0] = distnext;
              pq.push(make_pair(-distnext, make_pair(posnext, 0)));
            }
          }
          for (int j = 1; posnow + j*powernow < n; ++j) {
            int posnext = posnow + j*powernow;
            int distnext = distnow + j;
            if (dist[posnext][0] > distnext) {
              dist[posnext][0] = distnext;
              pq.push(make_pair(-distnext, make_pair(posnext, 0)));
            }
          }
        }
      }
    } else {
      if (dist[posnow][0] > distnow) {
        dist[posnow][0] = distnow;
        pq.push(make_pair(-dist[posnow][0], make_pair(posnow, 0)));
      }
      if (posnow + pownow < n && dist[posnow + pownow][pownow] > dist[posnow][pownow] + 1) {
        int distnext = dist[posnow][pownow] + 1;
        int posnext = posnow + pownow;
        dist[posnext][pownow] = dist[posnow][pownow] + 1;
        pq.push(make_pair(-distnext, make_pair(posnext, pownow)));
      }
      if (posnow - pownow >= 0 && dist[posnow - pownow][pownow] > dist[posnow][pownow] + 1) {
        int distnext = dist[posnow][pownow] + 1;
        int posnext = posnow - pownow;
        dist[posnext][pownow] = dist[posnow][pownow] + 1;
        pq.push(make_pair(-distnext, make_pair(posnext, pownow)));
      }
    }
  }
  if (res == 1000000000) res = -1;
  printf("%d\n",res);
}

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:14:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &n, &m);
   ~~~~~^~~~~~~~~~~~~~~~~
skyscraper.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &pos[i], &pw[i]);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 61432 KB Output is correct
2 Correct 58 ms 61436 KB Output is correct
3 Correct 59 ms 61432 KB Output is correct
4 Correct 60 ms 61340 KB Output is correct
5 Correct 60 ms 61404 KB Output is correct
6 Correct 60 ms 61432 KB Output is correct
7 Correct 59 ms 61432 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 61432 KB Output is correct
2 Correct 59 ms 61304 KB Output is correct
3 Correct 60 ms 61316 KB Output is correct
4 Correct 60 ms 61432 KB Output is correct
5 Correct 60 ms 61432 KB Output is correct
6 Correct 60 ms 61432 KB Output is correct
7 Correct 59 ms 61304 KB Output is correct
8 Correct 60 ms 61456 KB Output is correct
9 Correct 60 ms 61432 KB Output is correct
10 Correct 60 ms 61432 KB Output is correct
11 Correct 61 ms 61560 KB Output is correct
12 Correct 60 ms 61360 KB Output is correct
13 Correct 60 ms 61432 KB Output is correct
14 Correct 61 ms 61388 KB Output is correct
15 Correct 60 ms 61432 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 61432 KB Output is correct
2 Correct 59 ms 61400 KB Output is correct
3 Correct 59 ms 61400 KB Output is correct
4 Correct 60 ms 61304 KB Output is correct
5 Correct 58 ms 61432 KB Output is correct
6 Correct 58 ms 61432 KB Output is correct
7 Correct 59 ms 61532 KB Output is correct
8 Correct 60 ms 61432 KB Output is correct
9 Correct 60 ms 61304 KB Output is correct
10 Correct 60 ms 61432 KB Output is correct
11 Correct 61 ms 61388 KB Output is correct
12 Correct 61 ms 61432 KB Output is correct
13 Correct 60 ms 61460 KB Output is correct
14 Correct 61 ms 61560 KB Output is correct
15 Correct 61 ms 61404 KB Output is correct
16 Correct 60 ms 61436 KB Output is correct
17 Correct 61 ms 61456 KB Output is correct
18 Correct 61 ms 61436 KB Output is correct
19 Correct 60 ms 61448 KB Output is correct
20 Correct 61 ms 61432 KB Output is correct
21 Correct 60 ms 61432 KB Output is correct
22 Correct 61 ms 61432 KB Output is correct
23 Correct 61 ms 61440 KB Output is correct
24 Correct 63 ms 61568 KB Output is correct
25 Correct 61 ms 61404 KB Output is correct
26 Correct 61 ms 61432 KB Output is correct
27 Correct 61 ms 61436 KB Output is correct
28 Correct 63 ms 61432 KB Output is correct
29 Correct 68 ms 61432 KB Output is correct
30 Correct 63 ms 61432 KB Output is correct
31 Correct 65 ms 61488 KB Output is correct
32 Correct 63 ms 61428 KB Output is correct
33 Correct 71 ms 61432 KB Output is correct
34 Correct 71 ms 61432 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 61416 KB Output is correct
2 Correct 60 ms 61432 KB Output is correct
3 Correct 60 ms 61432 KB Output is correct
4 Correct 60 ms 61432 KB Output is correct
5 Correct 60 ms 61388 KB Output is correct
6 Correct 61 ms 61432 KB Output is correct
7 Correct 60 ms 61432 KB Output is correct
8 Correct 59 ms 61432 KB Output is correct
9 Correct 59 ms 61304 KB Output is correct
10 Correct 60 ms 61436 KB Output is correct
11 Correct 61 ms 61404 KB Output is correct
12 Correct 61 ms 61472 KB Output is correct
13 Correct 61 ms 61436 KB Output is correct
14 Correct 61 ms 61432 KB Output is correct
15 Correct 60 ms 61432 KB Output is correct
16 Correct 60 ms 61432 KB Output is correct
17 Correct 62 ms 61432 KB Output is correct
18 Correct 60 ms 61432 KB Output is correct
19 Correct 61 ms 61436 KB Output is correct
20 Correct 60 ms 61464 KB Output is correct
21 Correct 60 ms 61432 KB Output is correct
22 Correct 59 ms 61432 KB Output is correct
23 Correct 61 ms 61412 KB Output is correct
24 Correct 61 ms 61432 KB Output is correct
25 Correct 63 ms 61432 KB Output is correct
26 Correct 61 ms 61432 KB Output is correct
27 Correct 62 ms 61432 KB Output is correct
28 Correct 62 ms 61560 KB Output is correct
29 Correct 68 ms 61452 KB Output is correct
30 Correct 61 ms 61432 KB Output is correct
31 Correct 66 ms 61468 KB Output is correct
32 Correct 63 ms 61416 KB Output is correct
33 Correct 70 ms 61560 KB Output is correct
34 Correct 72 ms 61560 KB Output is correct
35 Correct 74 ms 61788 KB Output is correct
36 Correct 63 ms 61560 KB Output is correct
37 Correct 76 ms 61816 KB Output is correct
38 Correct 77 ms 61944 KB Output is correct
39 Correct 79 ms 61996 KB Output is correct
40 Correct 79 ms 62036 KB Output is correct
41 Correct 78 ms 61944 KB Output is correct
42 Correct 65 ms 61944 KB Output is correct
43 Correct 66 ms 61944 KB Output is correct
44 Correct 66 ms 61944 KB Output is correct
45 Correct 78 ms 61880 KB Output is correct
46 Correct 79 ms 61948 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 61320 KB Output is correct
2 Correct 61 ms 61432 KB Output is correct
3 Correct 60 ms 61304 KB Output is correct
4 Correct 60 ms 61432 KB Output is correct
5 Correct 60 ms 61384 KB Output is correct
6 Correct 60 ms 61404 KB Output is correct
7 Correct 60 ms 61392 KB Output is correct
8 Correct 61 ms 61432 KB Output is correct
9 Correct 60 ms 61432 KB Output is correct
10 Correct 60 ms 61324 KB Output is correct
11 Correct 61 ms 61480 KB Output is correct
12 Correct 60 ms 61432 KB Output is correct
13 Correct 60 ms 61432 KB Output is correct
14 Correct 61 ms 61432 KB Output is correct
15 Correct 60 ms 61432 KB Output is correct
16 Correct 60 ms 61432 KB Output is correct
17 Correct 71 ms 61496 KB Output is correct
18 Correct 61 ms 61432 KB Output is correct
19 Correct 60 ms 61404 KB Output is correct
20 Correct 61 ms 61432 KB Output is correct
21 Correct 64 ms 61432 KB Output is correct
22 Correct 61 ms 61432 KB Output is correct
23 Correct 61 ms 61432 KB Output is correct
24 Correct 62 ms 61432 KB Output is correct
25 Correct 61 ms 61432 KB Output is correct
26 Correct 61 ms 61660 KB Output is correct
27 Correct 59 ms 61408 KB Output is correct
28 Correct 62 ms 61432 KB Output is correct
29 Correct 67 ms 61432 KB Output is correct
30 Correct 61 ms 61432 KB Output is correct
31 Correct 65 ms 61432 KB Output is correct
32 Correct 67 ms 61432 KB Output is correct
33 Correct 70 ms 61432 KB Output is correct
34 Correct 72 ms 61560 KB Output is correct
35 Correct 73 ms 61816 KB Output is correct
36 Correct 64 ms 61560 KB Output is correct
37 Correct 77 ms 61816 KB Output is correct
38 Correct 80 ms 62072 KB Output is correct
39 Correct 78 ms 61948 KB Output is correct
40 Correct 79 ms 62072 KB Output is correct
41 Correct 79 ms 61948 KB Output is correct
42 Correct 67 ms 61944 KB Output is correct
43 Correct 66 ms 61872 KB Output is correct
44 Correct 66 ms 61944 KB Output is correct
45 Correct 79 ms 61944 KB Output is correct
46 Correct 80 ms 61944 KB Output is correct
47 Correct 152 ms 62520 KB Output is correct
48 Correct 69 ms 62292 KB Output is correct
49 Correct 69 ms 62200 KB Output is correct
50 Correct 67 ms 62012 KB Output is correct
51 Correct 118 ms 63140 KB Output is correct
52 Correct 127 ms 63032 KB Output is correct
53 Correct 82 ms 62584 KB Output is correct
54 Correct 63 ms 61432 KB Output is correct
55 Correct 65 ms 61404 KB Output is correct
56 Correct 76 ms 62840 KB Output is correct
57 Correct 147 ms 61660 KB Output is correct
58 Correct 74 ms 62044 KB Output is correct
59 Correct 79 ms 62072 KB Output is correct
60 Correct 84 ms 62072 KB Output is correct
61 Correct 78 ms 62072 KB Output is correct
62 Correct 111 ms 62968 KB Output is correct
63 Correct 107 ms 63064 KB Output is correct
64 Correct 111 ms 62984 KB Output is correct
65 Correct 363 ms 63856 KB Output is correct
66 Execution timed out 1057 ms 63728 KB Time limit exceeded
67 Halted 0 ms 0 KB -