답안 #242979

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
242979	2020-06-30T03:51:31 Z	neihcr7j	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	318 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 * 2];

int dijkstra() {
  fill(dist, dist + maxm, oo);
  dist[b[0]] = 0;
  L[0].push(b[0]);

  int M = maxn * 2 - 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	132 ms	204664 KB	Output is correct
2	Correct	128 ms	204664 KB	Output is correct
3	Correct	131 ms	204664 KB	Output is correct
4	Correct	128 ms	204664 KB	Output is correct
5	Correct	132 ms	204792 KB	Output is correct
6	Correct	148 ms	204664 KB	Output is correct
7	Correct	153 ms	204664 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	127 ms	204664 KB	Output is correct
2	Correct	139 ms	204756 KB	Output is correct
3	Correct	130 ms	204664 KB	Output is correct
4	Correct	129 ms	204664 KB	Output is correct
5	Correct	148 ms	204744 KB	Output is correct
6	Correct	133 ms	204664 KB	Output is correct
7	Correct	127 ms	204664 KB	Output is correct
8	Correct	130 ms	204792 KB	Output is correct
9	Correct	141 ms	204920 KB	Output is correct
10	Correct	131 ms	205048 KB	Output is correct
11	Correct	151 ms	205048 KB	Output is correct
12	Correct	128 ms	205176 KB	Output is correct
13	Correct	130 ms	205076 KB	Output is correct
14	Correct	128 ms	205048 KB	Output is correct
15	Correct	131 ms	205140 KB	Output is correct

Subtask #3
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	125 ms	204664 KB	Output is correct
2	Correct	131 ms	204824 KB	Output is correct
3	Correct	127 ms	204664 KB	Output is correct
4	Correct	146 ms	204664 KB	Output is correct
5	Correct	128 ms	204664 KB	Output is correct
6	Correct	145 ms	204664 KB	Output is correct
7	Correct	133 ms	204664 KB	Output is correct
8	Correct	130 ms	204740 KB	Output is correct
9	Correct	134 ms	204924 KB	Output is correct
10	Correct	131 ms	205036 KB	Output is correct
11	Correct	130 ms	205048 KB	Output is correct
12	Correct	132 ms	205176 KB	Output is correct
13	Correct	134 ms	205048 KB	Output is correct
14	Correct	154 ms	205048 KB	Output is correct
15	Correct	132 ms	205176 KB	Output is correct
16	Correct	138 ms	205432 KB	Output is correct
17	Correct	144 ms	208376 KB	Output is correct
18	Correct	178 ms	212856 KB	Output is correct
19	Correct	182 ms	214136 KB	Output is correct
20	Correct	167 ms	214136 KB	Output is correct
21	Correct	134 ms	206328 KB	Output is correct
22	Correct	161 ms	212984 KB	Output is correct
23	Correct	186 ms	212600 KB	Output is correct
24	Correct	178 ms	214264 KB	Output is correct
25	Correct	171 ms	214136 KB	Output is correct
26	Correct	201 ms	214760 KB	Output is correct
27	Correct	179 ms	214392 KB	Output is correct
28	Correct	177 ms	214520 KB	Output is correct
29	Correct	172 ms	214264 KB	Output is correct
30	Correct	172 ms	214136 KB	Output is correct
31	Correct	171 ms	214188 KB	Output is correct
32	Correct	173 ms	214140 KB	Output is correct
33	Correct	186 ms	214520 KB	Output is correct
34	Correct	178 ms	214520 KB	Output is correct

Subtask #4
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	129 ms	204664 KB	Output is correct
2	Correct	146 ms	204664 KB	Output is correct
3	Correct	132 ms	204792 KB	Output is correct
4	Correct	127 ms	204664 KB	Output is correct
5	Correct	128 ms	204664 KB	Output is correct
6	Correct	130 ms	204664 KB	Output is correct
7	Correct	129 ms	204664 KB	Output is correct
8	Correct	138 ms	205068 KB	Output is correct
9	Correct	144 ms	204796 KB	Output is correct
10	Correct	131 ms	205048 KB	Output is correct
11	Correct	145 ms	205176 KB	Output is correct
12	Correct	130 ms	205048 KB	Output is correct
13	Correct	128 ms	205048 KB	Output is correct
14	Correct	134 ms	205048 KB	Output is correct
15	Correct	133 ms	205048 KB	Output is correct
16	Correct	136 ms	205432 KB	Output is correct
17	Correct	149 ms	208376 KB	Output is correct
18	Correct	166 ms	212860 KB	Output is correct
19	Correct	183 ms	214008 KB	Output is correct
20	Correct	170 ms	214136 KB	Output is correct
21	Correct	136 ms	206328 KB	Output is correct
22	Correct	174 ms	213112 KB	Output is correct
23	Correct	167 ms	212472 KB	Output is correct
24	Correct	177 ms	214264 KB	Output is correct
25	Correct	165 ms	214140 KB	Output is correct
26	Correct	179 ms	214648 KB	Output is correct
27	Correct	177 ms	214392 KB	Output is correct
28	Correct	206 ms	214648 KB	Output is correct
29	Correct	179 ms	214424 KB	Output is correct
30	Correct	174 ms	214136 KB	Output is correct
31	Correct	172 ms	214264 KB	Output is correct
32	Correct	168 ms	214136 KB	Output is correct
33	Correct	183 ms	214592 KB	Output is correct
34	Correct	177 ms	214520 KB	Output is correct
35	Correct	178 ms	212984 KB	Output is correct
36	Correct	156 ms	210296 KB	Output is correct
37	Correct	196 ms	215928 KB	Output is correct
38	Correct	198 ms	216440 KB	Output is correct
39	Correct	202 ms	216440 KB	Output is correct
40	Correct	196 ms	216440 KB	Output is correct
41	Correct	201 ms	216440 KB	Output is correct
42	Correct	182 ms	215544 KB	Output is correct
43	Correct	196 ms	215156 KB	Output is correct
44	Correct	176 ms	214900 KB	Output is correct
45	Correct	220 ms	218388 KB	Output is correct
46	Correct	236 ms	218232 KB	Output is correct

Subtask #5
0 / 43.0

#	결과	실행 시간	메모리	Grader output
1	Correct	126 ms	204664 KB	Output is correct
2	Correct	128 ms	204724 KB	Output is correct
3	Correct	130 ms	204664 KB	Output is correct
4	Correct	126 ms	204664 KB	Output is correct
5	Correct	142 ms	204792 KB	Output is correct
6	Correct	133 ms	204640 KB	Output is correct
7	Correct	144 ms	204664 KB	Output is correct
8	Correct	127 ms	204792 KB	Output is correct
9	Correct	132 ms	204920 KB	Output is correct
10	Correct	132 ms	205048 KB	Output is correct
11	Correct	145 ms	205176 KB	Output is correct
12	Correct	128 ms	205048 KB	Output is correct
13	Correct	152 ms	205144 KB	Output is correct
14	Correct	130 ms	205048 KB	Output is correct
15	Correct	149 ms	205048 KB	Output is correct
16	Correct	137 ms	205436 KB	Output is correct
17	Correct	144 ms	208504 KB	Output is correct
18	Correct	167 ms	212992 KB	Output is correct
19	Correct	188 ms	214136 KB	Output is correct
20	Correct	173 ms	214136 KB	Output is correct
21	Correct	136 ms	206344 KB	Output is correct
22	Correct	167 ms	213008 KB	Output is correct
23	Correct	174 ms	212600 KB	Output is correct
24	Correct	179 ms	214264 KB	Output is correct
25	Correct	172 ms	214136 KB	Output is correct
26	Correct	178 ms	214776 KB	Output is correct
27	Correct	198 ms	214392 KB	Output is correct
28	Correct	181 ms	214648 KB	Output is correct
29	Correct	199 ms	214392 KB	Output is correct
30	Correct	173 ms	214136 KB	Output is correct
31	Correct	169 ms	214264 KB	Output is correct
32	Correct	167 ms	214136 KB	Output is correct
33	Correct	181 ms	214728 KB	Output is correct
34	Correct	192 ms	214648 KB	Output is correct
35	Correct	179 ms	213240 KB	Output is correct
36	Correct	149 ms	210296 KB	Output is correct
37	Correct	201 ms	215928 KB	Output is correct
38	Correct	201 ms	216416 KB	Output is correct
39	Correct	226 ms	216440 KB	Output is correct
40	Correct	206 ms	216440 KB	Output is correct
41	Correct	199 ms	216440 KB	Output is correct
42	Correct	174 ms	215412 KB	Output is correct
43	Correct	171 ms	215156 KB	Output is correct
44	Correct	189 ms	214900 KB	Output is correct
45	Correct	205 ms	218232 KB	Output is correct
46	Correct	206 ms	218252 KB	Output is correct
47	Runtime error	318 ms	262144 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
48	Halted	0 ms	0 KB	-

답안 #242979

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