답안 #242982

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
242982	2020-06-30T03:55:26 Z	neihcr7j	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	826 ms	262148 KB

skyscraper

#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 (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	79 ms	130168 KB	Output is correct
2	Correct	80 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	79 ms	130168 KB	Output is correct
6	Correct	80 ms	130168 KB	Output is correct
7	Correct	80 ms	130168 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	79 ms	130168 KB	Output is correct
2	Correct	88 ms	130168 KB	Output is correct
3	Correct	92 ms	130168 KB	Output is correct
4	Correct	79 ms	130168 KB	Output is correct
5	Correct	79 ms	130172 KB	Output is correct
6	Correct	82 ms	130172 KB	Output is correct
7	Correct	81 ms	130168 KB	Output is correct
8	Correct	81 ms	130296 KB	Output is correct
9	Correct	80 ms	130296 KB	Output is correct
10	Correct	79 ms	130484 KB	Output is correct
11	Correct	91 ms	130552 KB	Output is correct
12	Correct	83 ms	130552 KB	Output is correct
13	Correct	80 ms	130552 KB	Output is correct
14	Correct	90 ms	130628 KB	Output is correct
15	Correct	94 ms	130552 KB	Output is correct

Subtask #3
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	89 ms	130168 KB	Output is correct
2	Correct	89 ms	130168 KB	Output is correct
3	Correct	80 ms	130168 KB	Output is correct
4	Correct	85 ms	130168 KB	Output is correct
5	Correct	91 ms	130168 KB	Output is correct
6	Correct	90 ms	130168 KB	Output is correct
7	Correct	82 ms	130168 KB	Output is correct
8	Correct	78 ms	130168 KB	Output is correct
9	Correct	90 ms	130364 KB	Output is correct
10	Correct	81 ms	130552 KB	Output is correct
11	Correct	80 ms	130552 KB	Output is correct
12	Correct	83 ms	130552 KB	Output is correct
13	Correct	82 ms	130552 KB	Output is correct
14	Correct	91 ms	130552 KB	Output is correct
15	Correct	80 ms	130552 KB	Output is correct
16	Correct	83 ms	130936 KB	Output is correct
17	Correct	108 ms	133880 KB	Output is correct
18	Correct	122 ms	138360 KB	Output is correct
19	Correct	119 ms	139512 KB	Output is correct
20	Correct	122 ms	139512 KB	Output is correct
21	Correct	97 ms	131832 KB	Output is correct
22	Correct	115 ms	138488 KB	Output is correct
23	Correct	116 ms	137976 KB	Output is correct
24	Correct	143 ms	139512 KB	Output is correct
25	Correct	123 ms	139512 KB	Output is correct
26	Correct	143 ms	139768 KB	Output is correct
27	Correct	128 ms	139896 KB	Output is correct
28	Correct	149 ms	140152 KB	Output is correct
29	Correct	126 ms	139896 KB	Output is correct
30	Correct	137 ms	139640 KB	Output is correct
31	Correct	127 ms	139692 KB	Output is correct
32	Correct	148 ms	139640 KB	Output is correct
33	Correct	138 ms	140132 KB	Output is correct
34	Correct	127 ms	140024 KB	Output is correct

Subtask #4
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	80 ms	130192 KB	Output is correct
2	Correct	80 ms	130168 KB	Output is correct
3	Correct	82 ms	130152 KB	Output is correct
4	Correct	80 ms	130092 KB	Output is correct
5	Correct	82 ms	130168 KB	Output is correct
6	Correct	82 ms	130168 KB	Output is correct
7	Correct	79 ms	130168 KB	Output is correct
8	Correct	80 ms	130296 KB	Output is correct
9	Correct	80 ms	130296 KB	Output is correct
10	Correct	80 ms	130552 KB	Output is correct
11	Correct	86 ms	130680 KB	Output is correct
12	Correct	92 ms	130552 KB	Output is correct
13	Correct	83 ms	130552 KB	Output is correct
14	Correct	81 ms	130552 KB	Output is correct
15	Correct	84 ms	130620 KB	Output is correct
16	Correct	86 ms	130936 KB	Output is correct
17	Correct	95 ms	133880 KB	Output is correct
18	Correct	115 ms	138360 KB	Output is correct
19	Correct	131 ms	139640 KB	Output is correct
20	Correct	123 ms	139640 KB	Output is correct
21	Correct	89 ms	131832 KB	Output is correct
22	Correct	121 ms	138616 KB	Output is correct
23	Correct	118 ms	137976 KB	Output is correct
24	Correct	137 ms	139640 KB	Output is correct
25	Correct	122 ms	139512 KB	Output is correct
26	Correct	131 ms	139640 KB	Output is correct
27	Correct	133 ms	139896 KB	Output is correct
28	Correct	132 ms	140152 KB	Output is correct
29	Correct	132 ms	139768 KB	Output is correct
30	Correct	127 ms	139640 KB	Output is correct
31	Correct	127 ms	139640 KB	Output is correct
32	Correct	134 ms	139768 KB	Output is correct
33	Correct	155 ms	140152 KB	Output is correct
34	Correct	136 ms	140152 KB	Output is correct
35	Correct	134 ms	138232 KB	Output is correct
36	Correct	102 ms	135416 KB	Output is correct
37	Correct	131 ms	141052 KB	Output is correct
38	Correct	153 ms	141432 KB	Output is correct
39	Correct	138 ms	140920 KB	Output is correct
40	Correct	136 ms	141048 KB	Output is correct
41	Correct	137 ms	141304 KB	Output is correct
42	Correct	142 ms	140216 KB	Output is correct
43	Correct	129 ms	140408 KB	Output is correct
44	Correct	132 ms	140148 KB	Output is correct
45	Correct	182 ms	143480 KB	Output is correct
46	Correct	147 ms	143352 KB	Output is correct

Subtask #5
0 / 43.0

#	결과	실행 시간	메모리	Grader output
1	Correct	79 ms	130168 KB	Output is correct
2	Correct	79 ms	130176 KB	Output is correct
3	Correct	81 ms	130168 KB	Output is correct
4	Correct	80 ms	130136 KB	Output is correct
5	Correct	83 ms	130312 KB	Output is correct
6	Correct	81 ms	130168 KB	Output is correct
7	Correct	84 ms	130296 KB	Output is correct
8	Correct	80 ms	130168 KB	Output is correct
9	Correct	80 ms	130296 KB	Output is correct
10	Correct	83 ms	130552 KB	Output is correct
11	Correct	83 ms	130552 KB	Output is correct
12	Correct	82 ms	130552 KB	Output is correct
13	Correct	90 ms	130680 KB	Output is correct
14	Correct	82 ms	130616 KB	Output is correct
15	Correct	85 ms	130808 KB	Output is correct
16	Correct	85 ms	130940 KB	Output is correct
17	Correct	95 ms	133880 KB	Output is correct
18	Correct	115 ms	138360 KB	Output is correct
19	Correct	122 ms	139512 KB	Output is correct
20	Correct	124 ms	139512 KB	Output is correct
21	Correct	86 ms	131836 KB	Output is correct
22	Correct	116 ms	138492 KB	Output is correct
23	Correct	119 ms	137976 KB	Output is correct
24	Correct	144 ms	139512 KB	Output is correct
25	Correct	122 ms	139616 KB	Output is correct
26	Correct	133 ms	139748 KB	Output is correct
27	Correct	130 ms	139896 KB	Output is correct
28	Correct	144 ms	140152 KB	Output is correct
29	Correct	132 ms	139896 KB	Output is correct
30	Correct	122 ms	139768 KB	Output is correct
31	Correct	123 ms	139640 KB	Output is correct
32	Correct	134 ms	139696 KB	Output is correct
33	Correct	135 ms	140156 KB	Output is correct
34	Correct	130 ms	140024 KB	Output is correct
35	Correct	122 ms	138232 KB	Output is correct
36	Correct	117 ms	135420 KB	Output is correct
37	Correct	132 ms	141048 KB	Output is correct
38	Correct	149 ms	141560 KB	Output is correct
39	Correct	153 ms	140924 KB	Output is correct
40	Correct	137 ms	140920 KB	Output is correct
41	Correct	137 ms	141304 KB	Output is correct
42	Correct	138 ms	140276 KB	Output is correct
43	Correct	128 ms	140404 KB	Output is correct
44	Correct	142 ms	140168 KB	Output is correct
45	Correct	185 ms	143608 KB	Output is correct
46	Correct	162 ms	143224 KB	Output is correct
47	Correct	596 ms	194296 KB	Output is correct
48	Correct	826 ms	242040 KB	Output is correct
49	Correct	741 ms	252024 KB	Output is correct
50	Runtime error	550 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
51	Halted	0 ms	0 KB	-

답안 #242982

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 12.0 / 12.0

Subtask #3 14.0 / 14.0

Subtask #4 21.0 / 21.0

Subtask #5 0 / 43.0

Subtask #1
10.0 / 10.0

Subtask #2
12.0 / 12.0

Subtask #3
14.0 / 14.0

Subtask #4
21.0 / 21.0

Subtask #5
0 / 43.0