oj.uz

Submission #124135

# Submission time Handle Problem Language Result Execution time Memory
124135 2019-07-02T14:53:54 Z AyaBenSaad Jakarta Skyscrapers (APIO15_skyscraper) C++14
57 / 100
 468 ms 49348 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 2e3 + 3; //number of skyscrapers
const int M = 3e4 + 4; //number of doges;
const int inf = 1e9;
 
int n, m, b[M], p[M], ok;
vector <pair <int, int> > adj[M];
int dis[N][N], vis[N];
 
void Dijkstra (int u) {
  priority_queue <pair <long long, int> > q;
  vis[u]++;
  q.push ({-1, u});
  while (q.size()) {
    int x = q.top().second;
    q.pop();
    for (auto e : adj[x]) {
      int v = e.first;
      long long c = e.second;
      if ((!vis[v]) || vis [v] > c + vis[x]){
        vis[v] = c + vis[x];
        q.push({-vis[v], v});
      }
    }
  }
}
 
int main () {
    scanf ("%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        scanf("%d %d", &b[i], &p[i]);
        for (int j = 0; j < n; j++) {
            if (abs(j-b[i]) % p[i] == 0) {
                if (dis[b[i]][j] == 0 || dis[b[i]][j] > abs(j-b[i]) / p[i]) dis[b[i]][j] = abs(j-b[i]) / p[i];
            }
        }  
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if ( dis[i][j]) adj[i].push_back({j, dis[i][j]});
        }
    }
    Dijkstra(b[0]);
    if (vis[b[1]]) printf("%d\n", vis[b[1]]-1);
    else puts("-1");
}

Compilation message

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

Subtask #1
10.0 / 10.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1016 KB Output is correct
2 Correct 3 ms 1016 KB Output is correct
3 Correct 3 ms 1016 KB Output is correct
4 Correct 3 ms 1016 KB Output is correct
5 Correct 3 ms 1016 KB Output is correct
6 Correct 3 ms 1016 KB Output is correct
7 Correct 2 ms 1016 KB Output is correct
8 Correct 3 ms 1144 KB Output is correct
9 Correct 3 ms 1144 KB Output is correct
10 Correct 3 ms 1528 KB Output is correct
11 Correct 5 ms 1528 KB Output is correct
12 Correct 5 ms 1144 KB Output is correct
13 Correct 5 ms 1656 KB Output is correct
14 Correct 5 ms 1400 KB Output is correct
15 Correct 5 ms 1400 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1020 KB Output is correct
2 Correct 3 ms 1016 KB Output is correct
3 Correct 3 ms 1016 KB Output is correct
4 Correct 2 ms 1016 KB Output is correct
5 Correct 3 ms 1016 KB Output is correct
6 Correct 3 ms 1016 KB Output is correct
7 Correct 3 ms 1016 KB Output is correct
8 Correct 3 ms 1144 KB Output is correct
9 Correct 3 ms 1144 KB Output is correct
10 Correct 6 ms 1460 KB Output is correct
11 Correct 5 ms 1528 KB Output is correct
12 Correct 4 ms 1144 KB Output is correct
13 Correct 5 ms 1656 KB Output is correct
14 Correct 4 ms 1400 KB Output is correct
15 Correct 4 ms 1272 KB Output is correct
16 Correct 5 ms 2040 KB Output is correct
17 Correct 17 ms 5752 KB Output is correct
18 Correct 23 ms 6648 KB Output is correct
19 Correct 19 ms 4856 KB Output is correct
20 Correct 121 ms 48892 KB Output is correct
21 Correct 7 ms 2808 KB Output is correct
22 Correct 19 ms 5368 KB Output is correct
23 Correct 21 ms 6264 KB Output is correct
24 Correct 38 ms 10232 KB Output is correct
25 Correct 40 ms 10104 KB Output is correct
26 Correct 35 ms 2040 KB Output is correct
27 Correct 35 ms 1784 KB Output is correct
28 Correct 42 ms 13148 KB Output is correct
29 Correct 21 ms 1912 KB Output is correct
30 Correct 13 ms 1656 KB Output is correct
31 Correct 18 ms 1836 KB Output is correct
32 Correct 17 ms 1784 KB Output is correct
33 Correct 36 ms 2296 KB Output is correct
34 Correct 36 ms 2296 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1016 KB Output is correct
2 Correct 2 ms 1016 KB Output is correct
3 Correct 2 ms 1072 KB Output is correct
4 Correct 3 ms 1016 KB Output is correct
5 Correct 3 ms 1016 KB Output is correct
6 Correct 2 ms 1016 KB Output is correct
7 Correct 3 ms 1016 KB Output is correct
8 Correct 3 ms 1144 KB Output is correct
9 Correct 3 ms 1144 KB Output is correct
10 Correct 4 ms 1532 KB Output is correct
11 Correct 5 ms 1528 KB Output is correct
12 Correct 4 ms 1144 KB Output is correct
13 Correct 5 ms 1656 KB Output is correct
14 Correct 5 ms 1372 KB Output is correct
15 Correct 5 ms 1372 KB Output is correct
16 Correct 5 ms 2084 KB Output is correct
17 Correct 17 ms 5752 KB Output is correct
18 Correct 23 ms 6636 KB Output is correct
19 Correct 19 ms 4884 KB Output is correct
20 Correct 121 ms 48888 KB Output is correct
21 Correct 8 ms 2680 KB Output is correct
22 Correct 20 ms 5368 KB Output is correct
23 Correct 21 ms 6264 KB Output is correct
24 Correct 38 ms 10204 KB Output is correct
25 Correct 40 ms 10360 KB Output is correct
26 Correct 35 ms 2040 KB Output is correct
27 Correct 35 ms 1784 KB Output is correct
28 Correct 43 ms 13308 KB Output is correct
29 Correct 20 ms 1908 KB Output is correct
30 Correct 13 ms 1656 KB Output is correct
31 Correct 18 ms 1912 KB Output is correct
32 Correct 17 ms 1912 KB Output is correct
33 Correct 35 ms 2296 KB Output is correct
34 Correct 36 ms 2296 KB Output is correct
35 Correct 225 ms 14328 KB Output is correct
36 Correct 42 ms 8696 KB Output is correct
37 Correct 239 ms 19644 KB Output is correct
38 Correct 362 ms 19676 KB Output is correct
39 Correct 359 ms 19820 KB Output is correct
40 Correct 360 ms 19732 KB Output is correct
41 Correct 357 ms 19644 KB Output is correct
42 Correct 380 ms 2496 KB Output is correct
43 Correct 380 ms 2120 KB Output is correct
44 Correct 468 ms 49260 KB Output is correct
45 Correct 351 ms 6008 KB Output is correct
46 Correct 355 ms 6100 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1016 KB Output is correct
2 Correct 2 ms 1012 KB Output is correct
3 Correct 3 ms 1016 KB Output is correct
4 Correct 2 ms 1016 KB Output is correct
5 Correct 3 ms 1016 KB Output is correct
6 Correct 3 ms 1016 KB Output is correct
7 Correct 3 ms 1016 KB Output is correct
8 Correct 3 ms 1016 KB Output is correct
9 Correct 3 ms 1144 KB Output is correct
10 Correct 3 ms 1400 KB Output is correct
11 Correct 5 ms 1528 KB Output is correct
12 Correct 4 ms 1144 KB Output is correct
13 Correct 5 ms 1528 KB Output is correct
14 Correct 4 ms 1332 KB Output is correct
15 Correct 5 ms 1272 KB Output is correct
16 Correct 5 ms 1912 KB Output is correct
17 Correct 17 ms 5752 KB Output is correct
18 Correct 26 ms 6660 KB Output is correct
19 Correct 19 ms 4856 KB Output is correct
20 Correct 122 ms 48872 KB Output is correct
21 Correct 7 ms 2680 KB Output is correct
22 Correct 20 ms 5496 KB Output is correct
23 Correct 21 ms 6264 KB Output is correct
24 Correct 41 ms 10220 KB Output is correct
25 Correct 40 ms 10104 KB Output is correct
26 Correct 36 ms 2044 KB Output is correct
27 Correct 35 ms 1756 KB Output is correct
28 Correct 42 ms 13176 KB Output is correct
29 Correct 20 ms 1912 KB Output is correct
30 Correct 13 ms 1656 KB Output is correct
31 Correct 18 ms 1912 KB Output is correct
32 Correct 17 ms 1784 KB Output is correct
33 Correct 35 ms 2268 KB Output is correct
34 Correct 35 ms 2296 KB Output is correct
35 Correct 224 ms 14300 KB Output is correct
36 Correct 42 ms 8696 KB Output is correct
37 Correct 242 ms 19796 KB Output is correct
38 Correct 363 ms 19764 KB Output is correct
39 Correct 359 ms 20004 KB Output is correct
40 Correct 359 ms 19784 KB Output is correct
41 Correct 358 ms 19744 KB Output is correct
42 Correct 379 ms 2528 KB Output is correct
43 Correct 379 ms 2188 KB Output is correct
44 Correct 465 ms 49348 KB Output is correct
45 Correct 351 ms 6140 KB Output is correct
46 Correct 349 ms 6008 KB Output is correct
47 Runtime error 4 ms 1912 KB Execution killed with signal 11 (could be triggered by violating memory limits)
48 Halted 0 ms 0 KB -