답안 #242969

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
242969	2020-06-30T03:39:28 Z	neihcr7j	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	22 / 100	174 ms	194776 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];

queue < int > L[maxn * 2];

int dijkstra() {
  fill(dist, dist + maxn, 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) continue;

      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	118 ms	185340 KB	Output is correct
2	Correct	118 ms	185208 KB	Output is correct
3	Correct	122 ms	185336 KB	Output is correct
4	Correct	117 ms	185336 KB	Output is correct
5	Correct	119 ms	185336 KB	Output is correct
6	Correct	117 ms	185336 KB	Output is correct
7	Correct	118 ms	185340 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	119 ms	185336 KB	Output is correct
2	Correct	122 ms	185332 KB	Output is correct
3	Correct	121 ms	185336 KB	Output is correct
4	Correct	134 ms	185336 KB	Output is correct
5	Correct	117 ms	185336 KB	Output is correct
6	Correct	118 ms	185388 KB	Output is correct
7	Correct	117 ms	185336 KB	Output is correct
8	Correct	120 ms	185492 KB	Output is correct
9	Correct	118 ms	185464 KB	Output is correct
10	Correct	121 ms	185592 KB	Output is correct
11	Correct	118 ms	185848 KB	Output is correct
12	Correct	118 ms	185720 KB	Output is correct
13	Correct	118 ms	185720 KB	Output is correct
14	Correct	119 ms	185720 KB	Output is correct
15	Correct	119 ms	185720 KB	Output is correct

Subtask #3
0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	118 ms	185336 KB	Output is correct
2	Correct	134 ms	185336 KB	Output is correct
3	Correct	124 ms	185416 KB	Output is correct
4	Correct	120 ms	185464 KB	Output is correct
5	Correct	122 ms	185336 KB	Output is correct
6	Correct	116 ms	185336 KB	Output is correct
7	Correct	115 ms	185336 KB	Output is correct
8	Correct	117 ms	185336 KB	Output is correct
9	Correct	118 ms	185464 KB	Output is correct
10	Correct	117 ms	185644 KB	Output is correct
11	Correct	119 ms	185720 KB	Output is correct
12	Correct	123 ms	185660 KB	Output is correct
13	Correct	123 ms	185732 KB	Output is correct
14	Correct	118 ms	185720 KB	Output is correct
15	Correct	121 ms	185720 KB	Output is correct
16	Correct	130 ms	186232 KB	Output is correct
17	Correct	132 ms	188664 KB	Output is correct
18	Correct	152 ms	193528 KB	Output is correct
19	Correct	156 ms	194776 KB	Output is correct
20	Correct	161 ms	194676 KB	Output is correct
21	Correct	128 ms	187128 KB	Output is correct
22	Correct	157 ms	193656 KB	Output is correct
23	Incorrect	155 ms	192760 KB	Output isn't correct
24	Halted	0 ms	0 KB	-

Subtask #4
0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	121 ms	185336 KB	Output is correct
2	Correct	120 ms	185256 KB	Output is correct
3	Correct	116 ms	185464 KB	Output is correct
4	Correct	132 ms	185336 KB	Output is correct
5	Correct	125 ms	185336 KB	Output is correct
6	Correct	122 ms	185336 KB	Output is correct
7	Correct	117 ms	185380 KB	Output is correct
8	Correct	120 ms	185360 KB	Output is correct
9	Correct	117 ms	185468 KB	Output is correct
10	Correct	116 ms	185720 KB	Output is correct
11	Correct	124 ms	185716 KB	Output is correct
12	Correct	122 ms	185732 KB	Output is correct
13	Correct	119 ms	185732 KB	Output is correct
14	Correct	117 ms	185720 KB	Output is correct
15	Correct	118 ms	185720 KB	Output is correct
16	Correct	125 ms	186104 KB	Output is correct
17	Correct	135 ms	188792 KB	Output is correct
18	Correct	153 ms	193528 KB	Output is correct
19	Correct	161 ms	194680 KB	Output is correct
20	Correct	156 ms	194680 KB	Output is correct
21	Correct	124 ms	187000 KB	Output is correct
22	Correct	156 ms	193656 KB	Output is correct
23	Incorrect	158 ms	192760 KB	Output isn't correct
24	Halted	0 ms	0 KB	-

Subtask #5
0 / 43.0

#	결과	실행 시간	메모리	Grader output
1	Correct	118 ms	185312 KB	Output is correct
2	Correct	116 ms	185208 KB	Output is correct
3	Correct	135 ms	185336 KB	Output is correct
4	Correct	117 ms	185336 KB	Output is correct
5	Correct	130 ms	185360 KB	Output is correct
6	Correct	121 ms	185340 KB	Output is correct
7	Correct	116 ms	185336 KB	Output is correct
8	Correct	120 ms	185440 KB	Output is correct
9	Correct	122 ms	185464 KB	Output is correct
10	Correct	138 ms	185592 KB	Output is correct
11	Correct	136 ms	185720 KB	Output is correct
12	Correct	117 ms	185720 KB	Output is correct
13	Correct	117 ms	185720 KB	Output is correct
14	Correct	138 ms	185720 KB	Output is correct
15	Correct	138 ms	185720 KB	Output is correct
16	Correct	129 ms	186104 KB	Output is correct
17	Correct	134 ms	188792 KB	Output is correct
18	Correct	174 ms	193524 KB	Output is correct
19	Correct	160 ms	194680 KB	Output is correct
20	Correct	164 ms	194680 KB	Output is correct
21	Correct	126 ms	186968 KB	Output is correct
22	Correct	156 ms	193656 KB	Output is correct
23	Incorrect	155 ms	192736 KB	Output isn't correct
24	Halted	0 ms	0 KB	-

답안 #242969

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 12.0 / 12.0

Subtask #3 0 / 14.0

Subtask #4 0 / 21.0

Subtask #5 0 / 43.0

Subtask #1
10.0 / 10.0

Subtask #2
12.0 / 12.0

Subtask #3
0 / 14.0

Subtask #4
0 / 21.0

Subtask #5
0 / 43.0