oj.uz

답안 #240085

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
240085 2020-06-18T02:06:25 Z neihcr7j Jakarta Skyscrapers (APIO15_skyscraper) C++14
22 / 100
 211 ms 262148 KB 
#include<bits/stdc++.h>
 
#define oo 1000000000
#define maxm 9000000
#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 145 ms 246904 KB Output is correct
2 Correct 148 ms 246904 KB Output is correct
3 Correct 146 ms 246904 KB Output is correct
4 Correct 147 ms 246904 KB Output is correct
5 Correct 151 ms 247032 KB Output is correct
6 Correct 148 ms 247032 KB Output is correct
7 Correct 152 ms 246996 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 152 ms 246904 KB Output is correct
2 Correct 165 ms 246936 KB Output is correct
3 Correct 151 ms 246904 KB Output is correct
4 Correct 165 ms 246904 KB Output is correct
5 Correct 168 ms 247032 KB Output is correct
6 Correct 149 ms 247032 KB Output is correct
7 Correct 151 ms 247032 KB Output is correct
8 Correct 151 ms 247288 KB Output is correct
9 Correct 148 ms 247416 KB Output is correct
10 Correct 149 ms 247800 KB Output is correct
11 Correct 150 ms 247800 KB Output is correct
12 Correct 154 ms 247928 KB Output is correct
13 Correct 151 ms 247800 KB Output is correct
14 Correct 170 ms 247800 KB Output is correct
15 Correct 162 ms 247928 KB Output is correct

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 146 ms 246904 KB Output is correct
2 Correct 166 ms 246904 KB Output is correct
3 Correct 147 ms 247032 KB Output is correct
4 Correct 168 ms 246904 KB Output is correct
5 Correct 148 ms 247032 KB Output is correct
6 Correct 147 ms 247032 KB Output is correct
7 Correct 146 ms 247032 KB Output is correct
8 Correct 148 ms 247264 KB Output is correct
9 Correct 150 ms 247416 KB Output is correct
10 Correct 172 ms 247800 KB Output is correct
11 Correct 150 ms 247800 KB Output is correct
12 Correct 165 ms 247844 KB Output is correct
13 Correct 168 ms 247800 KB Output is correct
14 Correct 166 ms 247928 KB Output is correct
15 Correct 149 ms 247800 KB Output is correct
16 Correct 154 ms 248696 KB Output is correct
17 Correct 205 ms 254968 KB Output is correct
18 Runtime error 195 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
19 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 146 ms 247032 KB Output is correct
2 Correct 166 ms 246880 KB Output is correct
3 Correct 153 ms 246904 KB Output is correct
4 Correct 146 ms 246904 KB Output is correct
5 Correct 145 ms 247032 KB Output is correct
6 Correct 173 ms 247032 KB Output is correct
7 Correct 148 ms 247032 KB Output is correct
8 Correct 152 ms 247288 KB Output is correct
9 Correct 150 ms 247416 KB Output is correct
10 Correct 151 ms 247800 KB Output is correct
11 Correct 155 ms 247928 KB Output is correct
12 Correct 151 ms 247804 KB Output is correct
13 Correct 148 ms 247800 KB Output is correct
14 Correct 165 ms 247932 KB Output is correct
15 Correct 155 ms 247804 KB Output is correct
16 Correct 151 ms 248696 KB Output is correct
17 Correct 180 ms 254968 KB Output is correct
18 Runtime error 211 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
19 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 147 ms 247032 KB Output is correct
2 Correct 175 ms 246904 KB Output is correct
3 Correct 150 ms 247160 KB Output is correct
4 Correct 147 ms 246904 KB Output is correct
5 Correct 164 ms 247008 KB Output is correct
6 Correct 156 ms 247032 KB Output is correct
7 Correct 167 ms 247032 KB Output is correct
8 Correct 149 ms 247160 KB Output is correct
9 Correct 148 ms 247544 KB Output is correct
10 Correct 154 ms 247800 KB Output is correct
11 Correct 160 ms 247800 KB Output is correct
12 Correct 148 ms 247796 KB Output is correct
13 Correct 166 ms 247800 KB Output is correct
14 Correct 172 ms 247800 KB Output is correct
15 Correct 151 ms 247800 KB Output is correct
16 Correct 174 ms 248696 KB Output is correct
17 Correct 182 ms 254840 KB Output is correct
18 Runtime error 198 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
19 Halted 0 ms 0 KB -