oj.uz

답안 #242984

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
242984 2020-06-30T03:58:54 Z neihcr7j Jakarta Skyscrapers (APIO15_skyscraper) C++14
57 / 100
 749 ms 262148 KB 
#include<bits/stdc++.h>

#define oo 1000000000
#define maxm 4000000
#define maxn 30005
#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], vis[maxm];

queue < int > L[maxn];

int dijkstra() {
  fill(dist, dist + maxm, 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 || vis[u]) continue;
      vis[u] = 1;

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

  return (dist[b[1]] == oo ? -1 : dist[b[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 (b[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

# 결과 실행 시간 메모리 Grader output
1 Correct 80 ms 130072 KB Output is correct
2 Correct 80 ms 130296 KB Output is correct
3 Correct 82 ms 130172 KB Output is correct
4 Correct 94 ms 130168 KB Output is correct
5 Correct 91 ms 130296 KB Output is correct
6 Correct 80 ms 130168 KB Output is correct
7 Correct 82 ms 130168 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 80 ms 130168 KB Output is correct
2 Correct 81 ms 130132 KB Output is correct
3 Correct 80 ms 130168 KB Output is correct
4 Correct 82 ms 130168 KB Output is correct
5 Correct 80 ms 130168 KB Output is correct
6 Correct 81 ms 130168 KB Output is correct
7 Correct 81 ms 130124 KB Output is correct
8 Correct 85 ms 130328 KB Output is correct
9 Correct 80 ms 130296 KB Output is correct
10 Correct 83 ms 130552 KB Output is correct
11 Correct 91 ms 130552 KB Output is correct
12 Correct 83 ms 130680 KB Output is correct
13 Correct 84 ms 130552 KB Output is correct
14 Correct 83 ms 130552 KB Output is correct
15 Correct 83 ms 130552 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 94 ms 130168 KB Output is correct
2 Correct 88 ms 130144 KB Output is correct
3 Correct 83 ms 130168 KB Output is correct
4 Correct 80 ms 130204 KB Output is correct
5 Correct 86 ms 130208 KB Output is correct
6 Correct 85 ms 130168 KB Output is correct
7 Correct 82 ms 130168 KB Output is correct
8 Correct 92 ms 130240 KB Output is correct
9 Correct 80 ms 130296 KB Output is correct
10 Correct 81 ms 130552 KB Output is correct
11 Correct 92 ms 130564 KB Output is correct
12 Correct 82 ms 130552 KB Output is correct
13 Correct 87 ms 130536 KB Output is correct
14 Correct 82 ms 130552 KB Output is correct
15 Correct 81 ms 130552 KB Output is correct
16 Correct 83 ms 130936 KB Output is correct
17 Correct 105 ms 133880 KB Output is correct
18 Correct 117 ms 138360 KB Output is correct
19 Correct 134 ms 139512 KB Output is correct
20 Correct 141 ms 139552 KB Output is correct
21 Correct 89 ms 131808 KB Output is correct
22 Correct 127 ms 138468 KB Output is correct
23 Correct 130 ms 138052 KB Output is correct
24 Correct 137 ms 139384 KB Output is correct
25 Correct 122 ms 139640 KB Output is correct
26 Correct 130 ms 139640 KB Output is correct
27 Correct 140 ms 139932 KB Output is correct
28 Correct 137 ms 140024 KB Output is correct
29 Correct 128 ms 139768 KB Output is correct
30 Correct 120 ms 139640 KB Output is correct
31 Correct 125 ms 139768 KB Output is correct
32 Correct 123 ms 139644 KB Output is correct
33 Correct 133 ms 140152 KB Output is correct
34 Correct 129 ms 140024 KB Output is correct

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 89 ms 130168 KB Output is correct
2 Correct 80 ms 130168 KB Output is correct
3 Correct 82 ms 130168 KB Output is correct
4 Correct 87 ms 130168 KB Output is correct
5 Correct 82 ms 130168 KB Output is correct
6 Correct 87 ms 130168 KB Output is correct
7 Correct 79 ms 130168 KB Output is correct
8 Correct 79 ms 130296 KB Output is correct
9 Correct 90 ms 130300 KB Output is correct
10 Correct 87 ms 130520 KB Output is correct
11 Correct 82 ms 130532 KB Output is correct
12 Correct 82 ms 130552 KB Output is correct
13 Correct 83 ms 130552 KB Output is correct
14 Correct 86 ms 130536 KB Output is correct
15 Correct 91 ms 130552 KB Output is correct
16 Correct 92 ms 130940 KB Output is correct
17 Correct 99 ms 133880 KB Output is correct
18 Correct 122 ms 138360 KB Output is correct
19 Correct 132 ms 139640 KB Output is correct
20 Correct 123 ms 139640 KB Output is correct
21 Correct 96 ms 131832 KB Output is correct
22 Correct 132 ms 138592 KB Output is correct
23 Correct 128 ms 137976 KB Output is correct
24 Correct 123 ms 139512 KB Output is correct
25 Correct 122 ms 139512 KB Output is correct
26 Correct 126 ms 139640 KB Output is correct
27 Correct 128 ms 139896 KB Output is correct
28 Correct 121 ms 140024 KB Output is correct
29 Correct 126 ms 139768 KB Output is correct
30 Correct 131 ms 139768 KB Output is correct
31 Correct 122 ms 139640 KB Output is correct
32 Correct 138 ms 139640 KB Output is correct
33 Correct 139 ms 140152 KB Output is correct
34 Correct 140 ms 140024 KB Output is correct
35 Correct 132 ms 137976 KB Output is correct
36 Correct 105 ms 135288 KB Output is correct
37 Correct 144 ms 140792 KB Output is correct
38 Correct 151 ms 141176 KB Output is correct
39 Correct 151 ms 140536 KB Output is correct
40 Correct 152 ms 140536 KB Output is correct
41 Correct 146 ms 141176 KB Output is correct
42 Correct 126 ms 140276 KB Output is correct
43 Correct 128 ms 140404 KB Output is correct
44 Correct 126 ms 140148 KB Output is correct
45 Correct 168 ms 143636 KB Output is correct
46 Correct 143 ms 143100 KB Output is correct

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 90 ms 130168 KB Output is correct
2 Correct 81 ms 130168 KB Output is correct
3 Correct 81 ms 130168 KB Output is correct
4 Correct 80 ms 130168 KB Output is correct
5 Correct 87 ms 130092 KB Output is correct
6 Correct 91 ms 130168 KB Output is correct
7 Correct 79 ms 130168 KB Output is correct
8 Correct 88 ms 130296 KB Output is correct
9 Correct 88 ms 130424 KB Output is correct
10 Correct 81 ms 130552 KB Output is correct
11 Correct 93 ms 130552 KB Output is correct
12 Correct 82 ms 130552 KB Output is correct
13 Correct 85 ms 130680 KB Output is correct
14 Correct 81 ms 130552 KB Output is correct
15 Correct 88 ms 130552 KB Output is correct
16 Correct 91 ms 130936 KB Output is correct
17 Correct 96 ms 133880 KB Output is correct
18 Correct 124 ms 138360 KB Output is correct
19 Correct 137 ms 139512 KB Output is correct
20 Correct 122 ms 139512 KB Output is correct
21 Correct 87 ms 131832 KB Output is correct
22 Correct 115 ms 138516 KB Output is correct
23 Correct 123 ms 138104 KB Output is correct
24 Correct 135 ms 139512 KB Output is correct
25 Correct 131 ms 139560 KB Output is correct
26 Correct 138 ms 139640 KB Output is correct
27 Correct 137 ms 139988 KB Output is correct
28 Correct 126 ms 140128 KB Output is correct
29 Correct 147 ms 139768 KB Output is correct
30 Correct 137 ms 139640 KB Output is correct
31 Correct 129 ms 139640 KB Output is correct
32 Correct 134 ms 139640 KB Output is correct
33 Correct 136 ms 140024 KB Output is correct
34 Correct 142 ms 140024 KB Output is correct
35 Correct 132 ms 137976 KB Output is correct
36 Correct 104 ms 135292 KB Output is correct
37 Correct 131 ms 140920 KB Output is correct
38 Correct 134 ms 141176 KB Output is correct
39 Correct 137 ms 140676 KB Output is correct
40 Correct 135 ms 140536 KB Output is correct
41 Correct 140 ms 141044 KB Output is correct
42 Correct 122 ms 140276 KB Output is correct
43 Correct 134 ms 140480 KB Output is correct
44 Correct 129 ms 140148 KB Output is correct
45 Correct 157 ms 143352 KB Output is correct
46 Correct 140 ms 143224 KB Output is correct
47 Correct 464 ms 193944 KB Output is correct
48 Correct 683 ms 241768 KB Output is correct
49 Correct 749 ms 251600 KB Output is correct
50 Runtime error 549 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
51 Halted 0 ms 0 KB -