답안 #242981

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

skyscraper

#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], 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 (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	103 ms	171000 KB	Output is correct
2	Correct	105 ms	171000 KB	Output is correct
3	Correct	104 ms	171000 KB	Output is correct
4	Correct	104 ms	171000 KB	Output is correct
5	Correct	102 ms	171000 KB	Output is correct
6	Correct	114 ms	171128 KB	Output is correct
7	Correct	117 ms	171000 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	120 ms	171000 KB	Output is correct
2	Correct	104 ms	171000 KB	Output is correct
3	Correct	104 ms	171000 KB	Output is correct
4	Correct	105 ms	171000 KB	Output is correct
5	Correct	104 ms	171000 KB	Output is correct
6	Correct	119 ms	171000 KB	Output is correct
7	Correct	116 ms	171000 KB	Output is correct
8	Correct	108 ms	171128 KB	Output is correct
9	Correct	122 ms	171256 KB	Output is correct
10	Correct	106 ms	171420 KB	Output is correct
11	Correct	118 ms	171384 KB	Output is correct
12	Correct	104 ms	171384 KB	Output is correct
13	Correct	107 ms	171384 KB	Output is correct
14	Correct	105 ms	171448 KB	Output is correct
15	Correct	107 ms	171392 KB	Output is correct

Subtask #3
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	104 ms	171000 KB	Output is correct
2	Correct	114 ms	170976 KB	Output is correct
3	Correct	106 ms	171000 KB	Output is correct
4	Correct	106 ms	171000 KB	Output is correct
5	Correct	120 ms	171000 KB	Output is correct
6	Correct	111 ms	171000 KB	Output is correct
7	Correct	103 ms	171000 KB	Output is correct
8	Correct	102 ms	171128 KB	Output is correct
9	Correct	116 ms	171128 KB	Output is correct
10	Correct	105 ms	171384 KB	Output is correct
11	Correct	107 ms	171384 KB	Output is correct
12	Correct	107 ms	171384 KB	Output is correct
13	Correct	106 ms	171384 KB	Output is correct
14	Correct	103 ms	171384 KB	Output is correct
15	Correct	105 ms	171464 KB	Output is correct
16	Correct	113 ms	171768 KB	Output is correct
17	Correct	142 ms	174712 KB	Output is correct
18	Correct	157 ms	179204 KB	Output is correct
19	Correct	144 ms	180344 KB	Output is correct
20	Correct	144 ms	180472 KB	Output is correct
21	Correct	109 ms	172664 KB	Output is correct
22	Correct	140 ms	179348 KB	Output is correct
23	Correct	143 ms	178888 KB	Output is correct
24	Correct	163 ms	180576 KB	Output is correct
25	Correct	160 ms	180472 KB	Output is correct
26	Correct	155 ms	180984 KB	Output is correct
27	Correct	163 ms	180984 KB	Output is correct
28	Correct	160 ms	180984 KB	Output is correct
29	Correct	150 ms	180600 KB	Output is correct
30	Correct	146 ms	180472 KB	Output is correct
31	Correct	158 ms	180604 KB	Output is correct
32	Correct	149 ms	180472 KB	Output is correct
33	Correct	156 ms	180984 KB	Output is correct
34	Correct	155 ms	180960 KB	Output is correct

Subtask #4
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	103 ms	171000 KB	Output is correct
2	Correct	104 ms	171036 KB	Output is correct
3	Correct	103 ms	171000 KB	Output is correct
4	Correct	106 ms	171000 KB	Output is correct
5	Correct	112 ms	171000 KB	Output is correct
6	Correct	101 ms	171000 KB	Output is correct
7	Correct	102 ms	171000 KB	Output is correct
8	Correct	103 ms	171128 KB	Output is correct
9	Correct	109 ms	171256 KB	Output is correct
10	Correct	107 ms	171384 KB	Output is correct
11	Correct	123 ms	171384 KB	Output is correct
12	Correct	105 ms	171384 KB	Output is correct
13	Correct	108 ms	171384 KB	Output is correct
14	Correct	107 ms	171384 KB	Output is correct
15	Correct	120 ms	171384 KB	Output is correct
16	Correct	105 ms	171768 KB	Output is correct
17	Correct	118 ms	174712 KB	Output is correct
18	Correct	140 ms	179240 KB	Output is correct
19	Correct	144 ms	180488 KB	Output is correct
20	Correct	145 ms	180472 KB	Output is correct
21	Correct	114 ms	172664 KB	Output is correct
22	Correct	160 ms	179448 KB	Output is correct
23	Correct	147 ms	178936 KB	Output is correct
24	Correct	147 ms	180472 KB	Output is correct
25	Correct	149 ms	180476 KB	Output is correct
26	Correct	157 ms	180988 KB	Output is correct
27	Correct	170 ms	180728 KB	Output is correct
28	Correct	181 ms	180984 KB	Output is correct
29	Correct	156 ms	180600 KB	Output is correct
30	Correct	161 ms	180472 KB	Output is correct
31	Correct	152 ms	180472 KB	Output is correct
32	Correct	169 ms	180604 KB	Output is correct
33	Correct	167 ms	180916 KB	Output is correct
34	Correct	165 ms	180888 KB	Output is correct
35	Correct	158 ms	179192 KB	Output is correct
36	Correct	146 ms	176632 KB	Output is correct
37	Correct	175 ms	182136 KB	Output is correct
38	Correct	177 ms	182476 KB	Output is correct
39	Correct	180 ms	182520 KB	Output is correct
40	Correct	180 ms	182524 KB	Output is correct
41	Correct	178 ms	182648 KB	Output is correct
42	Correct	149 ms	181620 KB	Output is correct
43	Correct	157 ms	181364 KB	Output is correct
44	Correct	153 ms	180980 KB	Output is correct
45	Correct	179 ms	184440 KB	Output is correct
46	Correct	182 ms	184440 KB	Output is correct

Subtask #5
0 / 43.0

#	결과	실행 시간	메모리	Grader output
1	Correct	104 ms	171000 KB	Output is correct
2	Correct	122 ms	171000 KB	Output is correct
3	Correct	119 ms	171000 KB	Output is correct
4	Correct	106 ms	171000 KB	Output is correct
5	Correct	119 ms	171000 KB	Output is correct
6	Correct	103 ms	171008 KB	Output is correct
7	Correct	106 ms	171004 KB	Output is correct
8	Correct	107 ms	171100 KB	Output is correct
9	Correct	108 ms	171256 KB	Output is correct
10	Correct	110 ms	171384 KB	Output is correct
11	Correct	112 ms	171512 KB	Output is correct
12	Correct	118 ms	171384 KB	Output is correct
13	Correct	104 ms	171384 KB	Output is correct
14	Correct	126 ms	171384 KB	Output is correct
15	Correct	110 ms	171384 KB	Output is correct
16	Correct	120 ms	171768 KB	Output is correct
17	Correct	120 ms	174968 KB	Output is correct
18	Correct	145 ms	179324 KB	Output is correct
19	Correct	144 ms	180344 KB	Output is correct
20	Correct	146 ms	180472 KB	Output is correct
21	Correct	127 ms	172664 KB	Output is correct
22	Correct	146 ms	179320 KB	Output is correct
23	Correct	142 ms	178868 KB	Output is correct
24	Correct	154 ms	180472 KB	Output is correct
25	Correct	144 ms	180472 KB	Output is correct
26	Correct	150 ms	180984 KB	Output is correct
27	Correct	160 ms	180856 KB	Output is correct
28	Correct	157 ms	180984 KB	Output is correct
29	Correct	154 ms	180728 KB	Output is correct
30	Correct	164 ms	180472 KB	Output is correct
31	Correct	154 ms	180600 KB	Output is correct
32	Correct	147 ms	180472 KB	Output is correct
33	Correct	177 ms	180856 KB	Output is correct
34	Correct	158 ms	180984 KB	Output is correct
35	Correct	153 ms	179120 KB	Output is correct
36	Correct	130 ms	176612 KB	Output is correct
37	Correct	172 ms	182136 KB	Output is correct
38	Correct	173 ms	182520 KB	Output is correct
39	Correct	170 ms	182520 KB	Output is correct
40	Correct	183 ms	182520 KB	Output is correct
41	Correct	170 ms	182520 KB	Output is correct
42	Correct	162 ms	181620 KB	Output is correct
43	Correct	152 ms	181368 KB	Output is correct
44	Correct	148 ms	180980 KB	Output is correct
45	Correct	203 ms	184412 KB	Output is correct
46	Correct	205 ms	184312 KB	Output is correct
47	Correct	583 ms	239736 KB	Output is correct
48	Runtime error	455 ms	262144 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
49	Halted	0 ms	0 KB	-

답안 #242981

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