oj.uz

답안 #240091

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
240091 2020-06-18T02:16:43 Z neihcr7j Jakarta Skyscrapers (APIO15_skyscraper) C++14
57 / 100
 566 ms 262148 KB 
#include<bits/stdc++.h>
 
#define oo 1000000000
#define maxm 4000000
#define maxn 50005
#define block 250
 
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 inode(int x) {return x % n;}
int dnode(int x) {return (x - inode(x)) / n;}
 
int dist[maxm];
 
int dijkstra() {
  priority_queue < pair < int, int > > p;
 
  fill(dist, dist + maxm, oo);
 
  dist[b[0]] = 0;
  p.push({0, b[0]});
 
  while (!p.empty()) {
    int u = p.top().second; p.pop();
 
    for (auto i : g[u]) {
      int v = i.first, w = i.second;
 
      if (dist[v] > dist[u] + w) {
       // cerr << u << ' ' << v << ' ' << w << '\n';
        dist[v] = dist[u] + w;
        p.push({-dist[v], v});
      }
    }
  }
 
  //for (int i = 0; i < 25; ++i)
    //cerr << i << ' ' << dist[i] << '\n';
  return (dist[b[1]] != oo ? dist[b[1]] : -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

# 결과 실행 시간 메모리 Grader output
1 Correct 69 ms 109944 KB Output is correct
2 Correct 68 ms 109944 KB Output is correct
3 Correct 70 ms 109944 KB Output is correct
4 Correct 68 ms 109944 KB Output is correct
5 Correct 80 ms 110072 KB Output is correct
6 Correct 70 ms 109944 KB Output is correct
7 Correct 69 ms 110004 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 70 ms 109944 KB Output is correct
2 Correct 68 ms 109944 KB Output is correct
3 Correct 68 ms 109944 KB Output is correct
4 Correct 81 ms 109944 KB Output is correct
5 Correct 70 ms 109944 KB Output is correct
6 Correct 68 ms 109944 KB Output is correct
7 Correct 71 ms 110076 KB Output is correct
8 Correct 80 ms 110200 KB Output is correct
9 Correct 83 ms 110328 KB Output is correct
10 Correct 83 ms 110840 KB Output is correct
11 Correct 73 ms 110840 KB Output is correct
12 Correct 73 ms 110840 KB Output is correct
13 Correct 83 ms 110840 KB Output is correct
14 Correct 90 ms 110840 KB Output is correct
15 Correct 73 ms 110840 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 79 ms 109944 KB Output is correct
2 Correct 79 ms 109948 KB Output is correct
3 Correct 71 ms 109924 KB Output is correct
4 Correct 80 ms 109944 KB Output is correct
5 Correct 69 ms 109944 KB Output is correct
6 Correct 70 ms 110072 KB Output is correct
7 Correct 82 ms 109944 KB Output is correct
8 Correct 70 ms 110200 KB Output is correct
9 Correct 77 ms 110432 KB Output is correct
10 Correct 72 ms 110840 KB Output is correct
11 Correct 76 ms 110840 KB Output is correct
12 Correct 83 ms 110840 KB Output is correct
13 Correct 74 ms 110840 KB Output is correct
14 Correct 76 ms 110844 KB Output is correct
15 Correct 73 ms 110840 KB Output is correct
16 Correct 74 ms 111692 KB Output is correct
17 Correct 121 ms 117880 KB Output is correct
18 Correct 178 ms 130040 KB Output is correct
19 Correct 179 ms 133164 KB Output is correct
20 Correct 192 ms 133176 KB Output is correct
21 Correct 86 ms 113784 KB Output is correct
22 Correct 170 ms 130540 KB Output is correct
23 Correct 178 ms 128380 KB Output is correct
24 Correct 177 ms 131972 KB Output is correct
25 Correct 182 ms 133240 KB Output is correct
26 Correct 228 ms 133116 KB Output is correct
27 Correct 233 ms 133240 KB Output is correct
28 Correct 190 ms 133368 KB Output is correct
29 Correct 219 ms 133112 KB Output is correct
30 Correct 219 ms 133188 KB Output is correct
31 Correct 214 ms 133112 KB Output is correct
32 Correct 215 ms 133120 KB Output is correct
33 Correct 246 ms 133112 KB Output is correct
34 Correct 232 ms 133244 KB Output is correct

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 70 ms 109944 KB Output is correct
2 Correct 70 ms 109944 KB Output is correct
3 Correct 69 ms 109944 KB Output is correct
4 Correct 68 ms 109944 KB Output is correct
5 Correct 69 ms 110072 KB Output is correct
6 Correct 69 ms 109944 KB Output is correct
7 Correct 71 ms 109944 KB Output is correct
8 Correct 79 ms 110224 KB Output is correct
9 Correct 73 ms 110456 KB Output is correct
10 Correct 76 ms 110812 KB Output is correct
11 Correct 75 ms 110840 KB Output is correct
12 Correct 73 ms 110840 KB Output is correct
13 Correct 76 ms 110816 KB Output is correct
14 Correct 76 ms 111096 KB Output is correct
15 Correct 79 ms 110860 KB Output is correct
16 Correct 75 ms 111608 KB Output is correct
17 Correct 109 ms 118008 KB Output is correct
18 Correct 162 ms 130168 KB Output is correct
19 Correct 180 ms 133112 KB Output is correct
20 Correct 181 ms 133112 KB Output is correct
21 Correct 97 ms 113656 KB Output is correct
22 Correct 174 ms 130368 KB Output is correct
23 Correct 180 ms 128248 KB Output is correct
24 Correct 194 ms 131960 KB Output is correct
25 Correct 178 ms 133112 KB Output is correct
26 Correct 209 ms 133240 KB Output is correct
27 Correct 206 ms 133112 KB Output is correct
28 Correct 179 ms 133112 KB Output is correct
29 Correct 226 ms 133244 KB Output is correct
30 Correct 218 ms 133112 KB Output is correct
31 Correct 245 ms 133112 KB Output is correct
32 Correct 208 ms 133240 KB Output is correct
33 Correct 256 ms 133112 KB Output is correct
34 Correct 252 ms 133112 KB Output is correct
35 Correct 202 ms 127096 KB Output is correct
36 Correct 135 ms 122104 KB Output is correct
37 Correct 242 ms 133368 KB Output is correct
38 Correct 288 ms 134392 KB Output is correct
39 Correct 255 ms 134396 KB Output is correct
40 Correct 246 ms 134264 KB Output is correct
41 Correct 248 ms 134264 KB Output is correct
42 Correct 212 ms 133752 KB Output is correct
43 Correct 217 ms 133624 KB Output is correct
44 Correct 184 ms 133636 KB Output is correct
45 Correct 376 ms 134008 KB Output is correct
46 Correct 351 ms 134136 KB Output is correct

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 93 ms 109944 KB Output is correct
2 Correct 90 ms 109944 KB Output is correct
3 Correct 84 ms 109944 KB Output is correct
4 Correct 84 ms 109944 KB Output is correct
5 Correct 85 ms 109944 KB Output is correct
6 Correct 88 ms 110072 KB Output is correct
7 Correct 90 ms 109944 KB Output is correct
8 Correct 83 ms 110200 KB Output is correct
9 Correct 81 ms 110456 KB Output is correct
10 Correct 73 ms 110840 KB Output is correct
11 Correct 74 ms 110840 KB Output is correct
12 Correct 83 ms 110840 KB Output is correct
13 Correct 81 ms 110840 KB Output is correct
14 Correct 73 ms 110892 KB Output is correct
15 Correct 73 ms 110840 KB Output is correct
16 Correct 75 ms 111772 KB Output is correct
17 Correct 114 ms 117860 KB Output is correct
18 Correct 161 ms 130016 KB Output is correct
19 Correct 198 ms 133112 KB Output is correct
20 Correct 181 ms 133116 KB Output is correct
21 Correct 82 ms 113784 KB Output is correct
22 Correct 167 ms 130476 KB Output is correct
23 Correct 155 ms 128248 KB Output is correct
24 Correct 176 ms 131960 KB Output is correct
25 Correct 181 ms 133088 KB Output is correct
26 Correct 208 ms 133240 KB Output is correct
27 Correct 229 ms 133112 KB Output is correct
28 Correct 184 ms 133116 KB Output is correct
29 Correct 239 ms 133240 KB Output is correct
30 Correct 233 ms 133144 KB Output is correct
31 Correct 223 ms 133112 KB Output is correct
32 Correct 213 ms 133112 KB Output is correct
33 Correct 230 ms 133240 KB Output is correct
34 Correct 246 ms 133344 KB Output is correct
35 Correct 211 ms 127224 KB Output is correct
36 Correct 143 ms 122152 KB Output is correct
37 Correct 261 ms 133624 KB Output is correct
38 Correct 276 ms 134264 KB Output is correct
39 Correct 263 ms 134424 KB Output is correct
40 Correct 257 ms 134264 KB Output is correct
41 Correct 287 ms 134264 KB Output is correct
42 Correct 212 ms 133624 KB Output is correct
43 Correct 215 ms 133624 KB Output is correct
44 Correct 184 ms 133636 KB Output is correct
45 Correct 318 ms 134112 KB Output is correct
46 Correct 323 ms 134136 KB Output is correct
47 Runtime error 566 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
48 Halted 0 ms 0 KB -