답안 #45734 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
45734	2018-04-16T05:04:40 Z	mirbek01	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	36 / 100	116 ms	48636 KB

skyscraper

# include <bits/stdc++.h>

using namespace std;

const int N = 2002;

int n, m, b[N], p[N], d[N][N], dis[N];
vector < pair <int, int> > g[N];

int main(){
      cin >> n >> m;

      for(int i = 0; i < N; i ++){
            dis[i] = 1e9;
            for(int j = 0; j < N; j ++)
                  d[i][j] = 1e9;
      }

      for(int i = 1; i <= m; i ++){
            cin >> b[i] >> p[i];
            d[i][b[i]] = 0;
            for(int j = b[i]; j + p[i] < n; j += p[i])
                  d[i][j + p[i]] = d[i][j] + 1;
            for(int j = b[i]; j - p[i] >= 0; j -= p[i])
                  d[i][j - p[i]] = d[i][j] + 1;
      }

      for(int i = 1; i <= m; i ++){
            for(int j = 1; j <= m; j ++){
                  if(j == i) continue;
                  if(d[i][b[j]] != 1e9){
                        g[i].push_back({d[i][b[j]], j});
                  }
            }
      }

      set < pair <int, int> > st;
      dis[1] = 0;
      st.insert({-1e9, 1});

      while(!st.empty()){
            int v = st.begin()->second;
            st.erase(st.begin());
            for(int i = 0; i < g[v].size(); i ++){
                  int to = g[v][i].second, len = g[v][i].first;
                  if(dis[to] > dis[v] + len){
                        st.erase({dis[to], to});
                        dis[to] = dis[v] + len;
                        st.insert({dis[to], to});
                  }
            }
      }

      if(dis[2] == 1e9)
            cout << -1 << endl;
      else
            cout << dis[2] << endl;
}
/**
11 3
0 2
1 1
4 1
**/

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:44:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 0; i < g[v].size(); i ++){
                            ~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	16124 KB	Output is correct
2	Correct	13 ms	16124 KB	Output is correct
3	Correct	13 ms	16232 KB	Output is correct
4	Correct	14 ms	16240 KB	Output is correct
5	Correct	14 ms	16240 KB	Output is correct
6	Correct	13 ms	16244 KB	Output is correct
7	Correct	13 ms	16260 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	14 ms	16260 KB	Output is correct
2	Correct	14 ms	16308 KB	Output is correct
3	Correct	13 ms	16352 KB	Output is correct
4	Correct	13 ms	16352 KB	Output is correct
5	Correct	13 ms	16356 KB	Output is correct
6	Correct	14 ms	16356 KB	Output is correct
7	Correct	14 ms	16356 KB	Output is correct
8	Correct	13 ms	16356 KB	Output is correct
9	Correct	15 ms	16356 KB	Output is correct
10	Correct	16 ms	16364 KB	Output is correct
11	Correct	30 ms	18548 KB	Output is correct
12	Correct	95 ms	48356 KB	Output is correct
13	Correct	94 ms	48560 KB	Output is correct
14	Correct	29 ms	48560 KB	Output is correct
15	Correct	30 ms	48560 KB	Output is correct

Subtask #3
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	48560 KB	Output is correct
2	Correct	16 ms	48560 KB	Output is correct
3	Correct	13 ms	48560 KB	Output is correct
4	Correct	15 ms	48560 KB	Output is correct
5	Correct	13 ms	48560 KB	Output is correct
6	Correct	13 ms	48560 KB	Output is correct
7	Correct	14 ms	48560 KB	Output is correct
8	Correct	14 ms	48560 KB	Output is correct
9	Correct	14 ms	48560 KB	Output is correct
10	Correct	15 ms	48560 KB	Output is correct
11	Correct	34 ms	48560 KB	Output is correct
12	Correct	102 ms	48560 KB	Output is correct
13	Correct	98 ms	48636 KB	Output is correct
14	Correct	31 ms	48636 KB	Output is correct
15	Correct	31 ms	48636 KB	Output is correct
16	Correct	18 ms	48636 KB	Output is correct
17	Correct	29 ms	48636 KB	Output is correct
18	Correct	19 ms	48636 KB	Output is correct
19	Correct	16 ms	48636 KB	Output is correct
20	Correct	105 ms	48636 KB	Output is correct
21	Correct	18 ms	48636 KB	Output is correct
22	Correct	17 ms	48636 KB	Output is correct
23	Correct	19 ms	48636 KB	Output is correct
24	Correct	29 ms	48636 KB	Output is correct
25	Correct	28 ms	48636 KB	Output is correct
26	Correct	116 ms	48636 KB	Output is correct
27	Correct	94 ms	48636 KB	Output is correct
28	Correct	33 ms	48636 KB	Output is correct
29	Correct	18 ms	48636 KB	Output is correct
30	Correct	19 ms	48636 KB	Output is correct
31	Correct	22 ms	48636 KB	Output is correct
32	Correct	16 ms	48636 KB	Output is correct
33	Correct	42 ms	48636 KB	Output is correct
34	Correct	34 ms	48636 KB	Output is correct

Subtask #4
0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	14 ms	48636 KB	Output is correct
2	Correct	18 ms	48636 KB	Output is correct
3	Correct	16 ms	48636 KB	Output is correct
4	Correct	14 ms	48636 KB	Output is correct
5	Correct	14 ms	48636 KB	Output is correct
6	Correct	15 ms	48636 KB	Output is correct
7	Correct	16 ms	48636 KB	Output is correct
8	Correct	14 ms	48636 KB	Output is correct
9	Correct	14 ms	48636 KB	Output is correct
10	Correct	20 ms	48636 KB	Output is correct
11	Correct	44 ms	48636 KB	Output is correct
12	Correct	96 ms	48636 KB	Output is correct
13	Correct	96 ms	48636 KB	Output is correct
14	Correct	30 ms	48636 KB	Output is correct
15	Correct	30 ms	48636 KB	Output is correct
16	Correct	19 ms	48636 KB	Output is correct
17	Correct	28 ms	48636 KB	Output is correct
18	Correct	20 ms	48636 KB	Output is correct
19	Correct	16 ms	48636 KB	Output is correct
20	Correct	108 ms	48636 KB	Output is correct
21	Correct	18 ms	48636 KB	Output is correct
22	Correct	17 ms	48636 KB	Output is correct
23	Correct	26 ms	48636 KB	Output is correct
24	Correct	27 ms	48636 KB	Output is correct
25	Correct	32 ms	48636 KB	Output is correct
26	Correct	94 ms	48636 KB	Output is correct
27	Correct	96 ms	48636 KB	Output is correct
28	Correct	43 ms	48636 KB	Output is correct
29	Correct	20 ms	48636 KB	Output is correct
30	Correct	14 ms	48636 KB	Output is correct
31	Correct	16 ms	48636 KB	Output is correct
32	Correct	15 ms	48636 KB	Output is correct
33	Correct	30 ms	48636 KB	Output is correct
34	Correct	31 ms	48636 KB	Output is correct
35	Incorrect	19 ms	48636 KB	Output isn't correct
36	Halted	0 ms	0 KB	-

Subtask #5
0 / 43.0

#	결과	실행 시간	메모리	Grader output
1	Correct	14 ms	48636 KB	Output is correct
2	Correct	14 ms	48636 KB	Output is correct
3	Correct	13 ms	48636 KB	Output is correct
4	Correct	13 ms	48636 KB	Output is correct
5	Correct	15 ms	48636 KB	Output is correct
6	Correct	14 ms	48636 KB	Output is correct
7	Correct	14 ms	48636 KB	Output is correct
8	Correct	14 ms	48636 KB	Output is correct
9	Correct	14 ms	48636 KB	Output is correct
10	Correct	18 ms	48636 KB	Output is correct
11	Correct	31 ms	48636 KB	Output is correct
12	Correct	104 ms	48636 KB	Output is correct
13	Correct	94 ms	48636 KB	Output is correct
14	Correct	33 ms	48636 KB	Output is correct
15	Correct	31 ms	48636 KB	Output is correct
16	Correct	17 ms	48636 KB	Output is correct
17	Correct	28 ms	48636 KB	Output is correct
18	Correct	19 ms	48636 KB	Output is correct
19	Correct	16 ms	48636 KB	Output is correct
20	Correct	102 ms	48636 KB	Output is correct
21	Correct	20 ms	48636 KB	Output is correct
22	Correct	18 ms	48636 KB	Output is correct
23	Correct	19 ms	48636 KB	Output is correct
24	Correct	28 ms	48636 KB	Output is correct
25	Correct	28 ms	48636 KB	Output is correct
26	Correct	94 ms	48636 KB	Output is correct
27	Correct	98 ms	48636 KB	Output is correct
28	Correct	28 ms	48636 KB	Output is correct
29	Correct	18 ms	48636 KB	Output is correct
30	Correct	15 ms	48636 KB	Output is correct
31	Correct	17 ms	48636 KB	Output is correct
32	Correct	19 ms	48636 KB	Output is correct
33	Correct	33 ms	48636 KB	Output is correct
34	Correct	32 ms	48636 KB	Output is correct
35	Incorrect	18 ms	48636 KB	Output isn't correct
36	Halted	0 ms	0 KB	-

답안 #45734

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 12.0 / 12.0

Subtask #3 14.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
14.0 / 14.0

Subtask #4
0 / 21.0

Subtask #5
0 / 43.0