oj.uz

Submission #456452

# Submission time Handle Problem Language Result Execution time Memory
456452 2021-08-06T19:08:36 Z elgamalsalman Jakarta Skyscrapers (APIO15_skyscraper) C++14
36 / 100
 624 ms 262148 KB 
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define ww first
#define vv second

typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;

int N, M, b[30'050], p[30'050], sssp[30'050];
vvi dogesAt;
vvii adj;

void dijkstra(int source) {
  memset(sssp, -1, sizeof sssp);
  priority_queue<ii> pq;
  pq.push({0, source});
  while (!pq.empty()) {
    ii u = pq.top(); pq.pop();
    u.ww = -u.ww;
    //cerr << "// pq.top() : {" << u.fi << ", " << u.se << "}\n";
    if (sssp[u.vv] != -1 && sssp[u.vv] <= u.ww) continue;
    sssp[u.vv] = u.ww;
    for (ii v : adj[u.vv]) {
      int newDis = u.ww + v.ww;
      if (sssp[v.vv] == -1 || sssp[v.vv] > newDis) {
	pq.push({-newDis, v.vv});
      }
    }
  }
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  cin >> N >> M;
  dogesAt.assign(N, vi());
  adj.assign(M, vii());
  for (int i = 0; i < M; i++) {
    cin >> b[i] >> p[i];
    dogesAt[b[i]].push_back(i);
  }

  for (int i = 0; i < M; i++) {
    for (int j = b[i], stepCount = 0; j < N; j += p[i], stepCount++) {
      for (int d : dogesAt[j]) adj[i].push_back({stepCount, d});
    }

    for (int j = b[i] - p[i], stepCount = 1; j >= 0; j -= p[i], stepCount++) {
      for (int d : dogesAt[j]) adj[i].push_back({stepCount, d});
    }
  }

  //cerr << "// adj:-\n";
  //for (int u = 0; u < M; u++) {
  //  cerr << "// " << u << " :";
  //  for (ii v : adj[u]) cerr << " {" << v.fi << ", " << v.se << "}";
  //  cerr << '\n';
  //}
  //cerr << '\n';

  dijkstra(0);

  //cerr << "// sssp :";
  //for (int i = 0; i < M; i++) cerr << ' ' << sssp[i];
  //cerr << '\n';

  cout << sssp[1] << '\n';
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 448 KB Output is correct
10 Correct 1 ms 612 KB Output is correct
11 Correct 24 ms 3780 KB Output is correct
12 Correct 386 ms 40784 KB Output is correct
13 Correct 401 ms 40860 KB Output is correct
14 Correct 13 ms 2512 KB Output is correct
15 Correct 14 ms 2512 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 356 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 320 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 588 KB Output is correct
11 Correct 22 ms 3780 KB Output is correct
12 Correct 411 ms 40712 KB Output is correct
13 Correct 390 ms 40896 KB Output is correct
14 Correct 13 ms 2512 KB Output is correct
15 Correct 14 ms 2512 KB Output is correct
16 Correct 1 ms 716 KB Output is correct
17 Correct 7 ms 1484 KB Output is correct
18 Correct 1 ms 588 KB Output is correct
19 Correct 1 ms 460 KB Output is correct
20 Correct 403 ms 40980 KB Output is correct
21 Correct 1 ms 588 KB Output is correct
22 Correct 1 ms 460 KB Output is correct
23 Correct 1 ms 588 KB Output is correct
24 Correct 3 ms 844 KB Output is correct
25 Correct 3 ms 716 KB Output is correct
26 Correct 338 ms 38016 KB Output is correct
27 Correct 346 ms 38832 KB Output is correct
28 Correct 2 ms 844 KB Output is correct
29 Correct 3 ms 840 KB Output is correct
30 Correct 1 ms 460 KB Output is correct
31 Correct 2 ms 588 KB Output is correct
32 Correct 1 ms 588 KB Output is correct
33 Correct 14 ms 2632 KB Output is correct
34 Correct 14 ms 2632 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 400 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 2 ms 588 KB Output is correct
11 Correct 22 ms 3708 KB Output is correct
12 Correct 389 ms 40780 KB Output is correct
13 Correct 392 ms 40920 KB Output is correct
14 Correct 14 ms 2492 KB Output is correct
15 Correct 14 ms 2512 KB Output is correct
16 Correct 2 ms 704 KB Output is correct
17 Correct 8 ms 1480 KB Output is correct
18 Correct 1 ms 588 KB Output is correct
19 Correct 1 ms 460 KB Output is correct
20 Correct 414 ms 41076 KB Output is correct
21 Correct 1 ms 588 KB Output is correct
22 Correct 1 ms 460 KB Output is correct
23 Correct 1 ms 588 KB Output is correct
24 Correct 3 ms 844 KB Output is correct
25 Correct 3 ms 716 KB Output is correct
26 Correct 359 ms 37944 KB Output is correct
27 Correct 347 ms 38832 KB Output is correct
28 Correct 2 ms 844 KB Output is correct
29 Correct 3 ms 844 KB Output is correct
30 Correct 1 ms 444 KB Output is correct
31 Correct 2 ms 588 KB Output is correct
32 Correct 2 ms 588 KB Output is correct
33 Correct 16 ms 2632 KB Output is correct
34 Correct 14 ms 2624 KB Output is correct
35 Correct 387 ms 47664 KB Output is correct
36 Correct 12 ms 2124 KB Output is correct
37 Correct 482 ms 48928 KB Output is correct
38 Correct 581 ms 56028 KB Output is correct
39 Correct 587 ms 58276 KB Output is correct
40 Correct 596 ms 56948 KB Output is correct
41 Correct 517 ms 55520 KB Output is correct
42 Runtime error 470 ms 262148 KB Execution killed with signal 9
43 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 416 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 588 KB Output is correct
11 Correct 24 ms 3780 KB Output is correct
12 Correct 405 ms 40748 KB Output is correct
13 Correct 398 ms 40972 KB Output is correct
14 Correct 13 ms 2512 KB Output is correct
15 Correct 14 ms 2468 KB Output is correct
16 Correct 1 ms 716 KB Output is correct
17 Correct 7 ms 1488 KB Output is correct
18 Correct 1 ms 588 KB Output is correct
19 Correct 1 ms 460 KB Output is correct
20 Correct 407 ms 41068 KB Output is correct
21 Correct 1 ms 588 KB Output is correct
22 Correct 1 ms 460 KB Output is correct
23 Correct 1 ms 588 KB Output is correct
24 Correct 3 ms 844 KB Output is correct
25 Correct 2 ms 716 KB Output is correct
26 Correct 349 ms 38000 KB Output is correct
27 Correct 386 ms 38832 KB Output is correct
28 Correct 2 ms 844 KB Output is correct
29 Correct 3 ms 844 KB Output is correct
30 Correct 1 ms 460 KB Output is correct
31 Correct 2 ms 588 KB Output is correct
32 Correct 1 ms 588 KB Output is correct
33 Correct 14 ms 2652 KB Output is correct
34 Correct 14 ms 2632 KB Output is correct
35 Correct 405 ms 47652 KB Output is correct
36 Correct 12 ms 2124 KB Output is correct
37 Correct 434 ms 48880 KB Output is correct
38 Correct 624 ms 56060 KB Output is correct
39 Correct 577 ms 58288 KB Output is correct
40 Correct 544 ms 56956 KB Output is correct
41 Correct 501 ms 55496 KB Output is correct
42 Runtime error 454 ms 262148 KB Execution killed with signal 9
43 Halted 0 ms 0 KB -