oj.uz

Submission #242968

# Submission time Handle Problem Language Result Execution time Memory
242968 2020-06-30T03:34:49 Z neihcr7j Jakarta Skyscrapers (APIO15_skyscraper) C++14
22 / 100
 149 ms 161016 KB 
#include<bits/stdc++.h>

#define oo 1000000000
#define maxm 5000000
#define maxn 50005
#define block 100

using namespace std;
typedef long long ll;

int n, m;
int b[maxn], p[maxn];

vector < pair < int, int > > g[maxm];

int node(int u, int x) {return x * n + u;}

int dist[maxm];

queue < int > L[maxn];

int dijkstra() {
  fill(dist, dist + maxn, oo);
  dist[b[0]] = 0;
  L[0].push(b[0]);

  int M = maxn - 1;

  for (int i = 0; i <= M; ++i)
    while (!L[i].empty()) {
      int u = L[i].front(); L[i].pop();

      if (u == b[1])
        return i;

      if (dist[u] < i) continue;

      for (auto x : g[u]) {
        int v = x.first, w = x.second;
        if (dist[v] > dist[u] + w && dist[u] + w <= M) {
          dist[v] = dist[u] + w;
          L[dist[v]].push(v);
        }
      }
    }

  return -1;
}

int main(){

  #define TASK "ABC"
	//freopen(TASK".inp", "r", stdin); freopen(TASK".out", "w", stdout);
  ios_base::sync_with_stdio(0);

  cin >> n >> m;

  for (int i = 0; i < m; ++i)
    cin >> b[i] >> p[i];

  for (int j = 1; j <= block; ++j)
    for (int i = j; i < n; ++i)
      g[node(i, j)].push_back({node(i - j, j), 1});

  for (int j = 1; j <= block; ++j)
    for (int i = 0; i + j < n; ++i)
      g[node(i, j)].push_back({node(i + j, j), 1});

  for (int i = 0; i < n; ++i)
    for (int j = 1; j <= block; ++j)
      g[node(i, j)].push_back({i, 0});

  for (int i = 0; i < m; ++i)
    if (p[i] <= block)
      g[b[i]].push_back({node(b[i], p[i]), 0});


  for (int i = 0; i < m; ++i)
    if (p[i] > block)
      for (int j = b[i] % p[i]; j < n; j += p[i])
        if (i != j)
          g[b[i]].push_back({j, abs(j - b[i]) / p[i]});

  //for (int i = 0; i < 10; ++i)
   // for (auto j : g[i])
   //   cerr << i << ' ' << j.first << ' ' << j.second << '\n';
  cout << dijkstra();

  return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 151676 KB Output is correct
2 Correct 93 ms 151672 KB Output is correct
3 Correct 93 ms 151672 KB Output is correct
4 Correct 104 ms 151800 KB Output is correct
5 Correct 104 ms 151672 KB Output is correct
6 Correct 92 ms 151676 KB Output is correct
7 Correct 104 ms 151672 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 151672 KB Output is correct
2 Correct 101 ms 151672 KB Output is correct
3 Correct 95 ms 151672 KB Output is correct
4 Correct 92 ms 151672 KB Output is correct
5 Correct 93 ms 151672 KB Output is correct
6 Correct 92 ms 151672 KB Output is correct
7 Correct 93 ms 151672 KB Output is correct
8 Correct 92 ms 151800 KB Output is correct
9 Correct 93 ms 151800 KB Output is correct
10 Correct 95 ms 151928 KB Output is correct
11 Correct 93 ms 152056 KB Output is correct
12 Correct 95 ms 152104 KB Output is correct
13 Correct 95 ms 152056 KB Output is correct
14 Correct 96 ms 152056 KB Output is correct
15 Correct 111 ms 152056 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 151672 KB Output is correct
2 Correct 94 ms 151672 KB Output is correct
3 Correct 93 ms 151672 KB Output is correct
4 Correct 96 ms 151676 KB Output is correct
5 Correct 92 ms 151672 KB Output is correct
6 Correct 96 ms 151704 KB Output is correct
7 Correct 91 ms 151672 KB Output is correct
8 Correct 93 ms 151800 KB Output is correct
9 Correct 92 ms 151800 KB Output is correct
10 Correct 94 ms 151928 KB Output is correct
11 Correct 94 ms 152184 KB Output is correct
12 Correct 95 ms 152032 KB Output is correct
13 Correct 92 ms 152056 KB Output is correct
14 Correct 95 ms 152056 KB Output is correct
15 Correct 92 ms 152056 KB Output is correct
16 Correct 104 ms 152440 KB Output is correct
17 Correct 111 ms 155128 KB Output is correct
18 Correct 129 ms 159864 KB Output is correct
19 Correct 141 ms 161016 KB Output is correct
20 Correct 131 ms 161016 KB Output is correct
21 Correct 113 ms 153336 KB Output is correct
22 Correct 129 ms 159992 KB Output is correct
23 Incorrect 129 ms 159224 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 151672 KB Output is correct
2 Correct 112 ms 151672 KB Output is correct
3 Correct 103 ms 151672 KB Output is correct
4 Correct 94 ms 151672 KB Output is correct
5 Correct 98 ms 151672 KB Output is correct
6 Correct 91 ms 151672 KB Output is correct
7 Correct 90 ms 151672 KB Output is correct
8 Correct 93 ms 151800 KB Output is correct
9 Correct 95 ms 151800 KB Output is correct
10 Correct 95 ms 151940 KB Output is correct
11 Correct 94 ms 152036 KB Output is correct
12 Correct 97 ms 152056 KB Output is correct
13 Correct 92 ms 152056 KB Output is correct
14 Correct 96 ms 152056 KB Output is correct
15 Correct 98 ms 152104 KB Output is correct
16 Correct 99 ms 152448 KB Output is correct
17 Correct 107 ms 155128 KB Output is correct
18 Correct 128 ms 159864 KB Output is correct
19 Correct 132 ms 161016 KB Output is correct
20 Correct 147 ms 161016 KB Output is correct
21 Correct 112 ms 153336 KB Output is correct
22 Correct 131 ms 160032 KB Output is correct
23 Incorrect 149 ms 159096 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 151672 KB Output is correct
2 Correct 92 ms 151672 KB Output is correct
3 Correct 93 ms 151672 KB Output is correct
4 Correct 93 ms 151672 KB Output is correct
5 Correct 94 ms 151672 KB Output is correct
6 Correct 104 ms 151672 KB Output is correct
7 Correct 93 ms 151676 KB Output is correct
8 Correct 94 ms 151672 KB Output is correct
9 Correct 106 ms 151800 KB Output is correct
10 Correct 96 ms 151928 KB Output is correct
11 Correct 97 ms 152056 KB Output is correct
12 Correct 95 ms 151928 KB Output is correct
13 Correct 104 ms 152056 KB Output is correct
14 Correct 95 ms 152056 KB Output is correct
15 Correct 96 ms 152060 KB Output is correct
16 Correct 100 ms 152440 KB Output is correct
17 Correct 108 ms 155128 KB Output is correct
18 Correct 128 ms 159864 KB Output is correct
19 Correct 135 ms 161016 KB Output is correct
20 Correct 136 ms 161016 KB Output is correct
21 Correct 111 ms 153336 KB Output is correct
22 Correct 139 ms 160084 KB Output is correct
23 Incorrect 146 ms 159112 KB Output isn't correct
24 Halted 0 ms 0 KB -