oj.uz

Submission #230520

# Submission time Handle Problem Language Result Execution time Memory
230520 2020-05-10T09:54:09 Z AlexLuchianov Jakarta Skyscrapers (APIO15_skyscraper) C++14
57 / 100
 1000 ms 66812 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <queue>
#include <map>

using namespace std;

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 30000;
int v[1 + nmax][2];
vector<int> g[1 + nmax];

map<int, int> dp[1 + nmax];

int seen[1 + nmax];

queue<pair<int,int>> q;

void processlevel(int node, int cost){
  if(seen[node] == 1)
    return ;
  seen[node] = 1;
  for(int h = 0; h < g[node].size(); h++){
    int jump2 = g[node][h];
    if(dp[node][jump2] == 0){
      dp[node][jump2] = cost;
      q.push({node, jump2});
    }
  }
}

int main()
{
  int n, m;
  cin >> n >> m;
  for(int i = 0;i < m; i++) {
    cin >> v[i][0] >> v[i][1];
    g[v[i][0]].push_back(v[i][1]);
  }
  processlevel(v[0][0], 1);

  while(0 < q.size()){
    int node = q.front().first;
    int jump = q.front().second;
    int cost = dp[node][jump];
    q.pop();

    if(0 <= node - jump)
      if(dp[node - jump][jump] == 0) {
        dp[node - jump][jump] = cost + 1;
        processlevel(node - jump, cost + 1);
        q.push({node - jump, jump});
      }
    if(node + jump < n)
      if(dp[node + jump][jump] == 0) {
        dp[node + jump][jump] = cost + 1;
        processlevel(node + jump, cost + 1);
        q.push({node + jump, jump});
      }
  }

  cout << dp[v[1][0]][v[1][1]] - 1;
  return 0;
}

Compilation message

skyscraper.cpp: In function 'void processlevel(int, int)':
skyscraper.cpp:28:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int h = 0; h < g[node].size(); h++){
                  ~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2432 KB Output is correct
2 Correct 5 ms 2432 KB Output is correct
3 Correct 5 ms 2432 KB Output is correct
4 Correct 6 ms 2432 KB Output is correct
5 Correct 5 ms 2432 KB Output is correct
6 Correct 6 ms 2432 KB Output is correct
7 Correct 5 ms 2432 KB Output is correct
8 Correct 6 ms 2432 KB Output is correct
9 Correct 5 ms 2432 KB Output is correct
10 Correct 6 ms 2560 KB Output is correct
11 Correct 8 ms 2688 KB Output is correct
12 Correct 7 ms 2432 KB Output is correct
13 Correct 7 ms 2560 KB Output is correct
14 Correct 8 ms 2688 KB Output is correct
15 Correct 9 ms 2816 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2432 KB Output is correct
2 Correct 5 ms 2432 KB Output is correct
3 Correct 5 ms 2432 KB Output is correct
4 Correct 6 ms 2432 KB Output is correct
5 Correct 5 ms 2432 KB Output is correct
6 Correct 6 ms 2432 KB Output is correct
7 Correct 6 ms 2432 KB Output is correct
8 Correct 7 ms 2432 KB Output is correct
9 Correct 6 ms 2432 KB Output is correct
10 Correct 8 ms 2560 KB Output is correct
11 Correct 8 ms 2688 KB Output is correct
12 Correct 7 ms 2432 KB Output is correct
13 Correct 6 ms 2432 KB Output is correct
14 Correct 8 ms 2688 KB Output is correct
15 Correct 9 ms 2816 KB Output is correct
16 Correct 6 ms 2432 KB Output is correct
17 Correct 11 ms 3200 KB Output is correct
18 Correct 6 ms 2432 KB Output is correct
19 Correct 6 ms 2432 KB Output is correct
20 Correct 7 ms 2560 KB Output is correct
21 Correct 6 ms 2432 KB Output is correct
22 Correct 6 ms 2432 KB Output is correct
23 Correct 8 ms 2816 KB Output is correct
24 Correct 10 ms 3072 KB Output is correct
25 Correct 9 ms 2816 KB Output is correct
26 Correct 8 ms 2816 KB Output is correct
27 Correct 8 ms 2816 KB Output is correct
28 Correct 12 ms 3584 KB Output is correct
29 Correct 23 ms 5376 KB Output is correct
30 Correct 9 ms 3200 KB Output is correct
31 Correct 13 ms 3968 KB Output is correct
32 Correct 10 ms 3584 KB Output is correct
33 Correct 49 ms 8064 KB Output is correct
34 Correct 49 ms 8184 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2432 KB Output is correct
2 Correct 5 ms 2432 KB Output is correct
3 Correct 6 ms 2432 KB Output is correct
4 Correct 6 ms 2432 KB Output is correct
5 Correct 6 ms 2432 KB Output is correct
6 Correct 6 ms 2432 KB Output is correct
7 Correct 6 ms 2432 KB Output is correct
8 Correct 6 ms 2432 KB Output is correct
9 Correct 6 ms 2432 KB Output is correct
10 Correct 6 ms 2560 KB Output is correct
11 Correct 8 ms 2688 KB Output is correct
12 Correct 6 ms 2432 KB Output is correct
13 Correct 7 ms 2432 KB Output is correct
14 Correct 8 ms 2688 KB Output is correct
15 Correct 8 ms 2688 KB Output is correct
16 Correct 7 ms 2432 KB Output is correct
17 Correct 11 ms 3200 KB Output is correct
18 Correct 6 ms 2432 KB Output is correct
19 Correct 7 ms 2432 KB Output is correct
20 Correct 7 ms 2688 KB Output is correct
21 Correct 7 ms 2432 KB Output is correct
22 Correct 6 ms 2432 KB Output is correct
23 Correct 7 ms 2816 KB Output is correct
24 Correct 10 ms 3072 KB Output is correct
25 Correct 8 ms 2816 KB Output is correct
26 Correct 8 ms 2816 KB Output is correct
27 Correct 8 ms 2816 KB Output is correct
28 Correct 12 ms 3584 KB Output is correct
29 Correct 24 ms 5376 KB Output is correct
30 Correct 9 ms 3200 KB Output is correct
31 Correct 13 ms 3968 KB Output is correct
32 Correct 10 ms 3584 KB Output is correct
33 Correct 54 ms 8184 KB Output is correct
34 Correct 54 ms 8056 KB Output is correct
35 Correct 63 ms 7672 KB Output is correct
36 Correct 13 ms 3328 KB Output is correct
37 Correct 112 ms 10928 KB Output is correct
38 Correct 104 ms 10488 KB Output is correct
39 Correct 111 ms 10484 KB Output is correct
40 Correct 101 ms 10488 KB Output is correct
41 Correct 113 ms 10488 KB Output is correct
42 Correct 25 ms 3100 KB Output is correct
43 Correct 24 ms 3072 KB Output is correct
44 Correct 24 ms 2944 KB Output is correct
45 Correct 362 ms 25444 KB Output is correct
46 Correct 370 ms 25624 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2432 KB Output is correct
2 Correct 5 ms 2432 KB Output is correct
3 Correct 6 ms 2432 KB Output is correct
4 Correct 6 ms 2432 KB Output is correct
5 Correct 5 ms 2432 KB Output is correct
6 Correct 6 ms 2432 KB Output is correct
7 Correct 6 ms 2432 KB Output is correct
8 Correct 6 ms 2432 KB Output is correct
9 Correct 6 ms 2432 KB Output is correct
10 Correct 6 ms 2560 KB Output is correct
11 Correct 8 ms 2688 KB Output is correct
12 Correct 6 ms 2432 KB Output is correct
13 Correct 7 ms 2432 KB Output is correct
14 Correct 8 ms 2688 KB Output is correct
15 Correct 10 ms 2816 KB Output is correct
16 Correct 6 ms 2432 KB Output is correct
17 Correct 12 ms 3200 KB Output is correct
18 Correct 6 ms 2432 KB Output is correct
19 Correct 6 ms 2432 KB Output is correct
20 Correct 7 ms 2560 KB Output is correct
21 Correct 6 ms 2432 KB Output is correct
22 Correct 6 ms 2432 KB Output is correct
23 Correct 8 ms 2816 KB Output is correct
24 Correct 9 ms 3072 KB Output is correct
25 Correct 8 ms 2816 KB Output is correct
26 Correct 8 ms 2816 KB Output is correct
27 Correct 8 ms 2816 KB Output is correct
28 Correct 11 ms 3584 KB Output is correct
29 Correct 24 ms 5376 KB Output is correct
30 Correct 9 ms 3200 KB Output is correct
31 Correct 13 ms 3968 KB Output is correct
32 Correct 10 ms 3584 KB Output is correct
33 Correct 50 ms 8056 KB Output is correct
34 Correct 50 ms 8056 KB Output is correct
35 Correct 64 ms 7672 KB Output is correct
36 Correct 13 ms 3328 KB Output is correct
37 Correct 110 ms 10872 KB Output is correct
38 Correct 103 ms 10488 KB Output is correct
39 Correct 118 ms 10492 KB Output is correct
40 Correct 103 ms 10488 KB Output is correct
41 Correct 109 ms 10596 KB Output is correct
42 Correct 25 ms 3200 KB Output is correct
43 Correct 24 ms 3072 KB Output is correct
44 Correct 23 ms 2944 KB Output is correct
45 Correct 377 ms 25464 KB Output is correct
46 Correct 392 ms 25596 KB Output is correct
47 Correct 805 ms 37756 KB Output is correct
48 Correct 25 ms 3072 KB Output is correct
49 Correct 27 ms 3072 KB Output is correct
50 Correct 19 ms 3072 KB Output is correct
51 Correct 199 ms 18300 KB Output is correct
52 Correct 206 ms 19704 KB Output is correct
53 Correct 52 ms 7548 KB Output is correct
54 Correct 7 ms 3200 KB Output is correct
55 Correct 8 ms 3712 KB Output is correct
56 Correct 30 ms 5112 KB Output is correct
57 Correct 200 ms 22904 KB Output is correct
58 Correct 27 ms 6008 KB Output is correct
59 Correct 41 ms 7416 KB Output is correct
60 Correct 50 ms 8700 KB Output is correct
61 Correct 51 ms 8060 KB Output is correct
62 Correct 280 ms 27000 KB Output is correct
63 Execution timed out 1096 ms 66812 KB Time limit exceeded
64 Halted 0 ms 0 KB -