답안 #49027 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
49027	2018-05-21T12:15:09 Z	someone_aa	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	36 / 100	85 ms	19640 KB

skyscraper

#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
using namespace std;
const int maxn = 2100;
int dist[maxn][maxn];
bool visited[maxn][maxn];
int st[maxn], p[maxn], n, m;

set<int>ps[maxn];

int main() {
    cin>>n>>m;
    for(int i=0;i<m;i++) {
        cin>>st[i]>>p[i];
        ps[st[i]].insert(p[i]);
    }

    queue<pair<int,int> > q;
    q.push(mp(st[0], p[0]));
    visited[st[0]][0] = true;
    visited[st[0]][p[0]]=true;

    while(!q.empty()) {
        int currx = q.front().first;
        int currc = q.front().second;
        q.pop();

        if(currx - currc >= 0 && !visited[currx-currc][currc]) {
            visited[currx-currc][currc] = true;
            dist[currx-currc][currc] = dist[currx][currc] + 1;
            q.push(mp(currx-currc, currc));
        }

        if(currx + currc < n && !visited[currx+currc][currc]) {
            visited[currx+currc][currc] = true;
            dist[currx+currc][currc] = dist[currx][currc] + 1;
            q.push(mp(currx+currc, currc));
        }

        for(int i: ps[currx]) {
            if(currx - i >= 0 && !visited[currx-i][i]) {
                visited[currx-i][i] = true;
                dist[currx-i][i] = dist[currx][currc] + 1;
                q.push(mp(currx-i, i));
            }
            if(currx + i < n && !visited[currx+i][i]) {
                visited[currx+i][i] = true;
                dist[currx+i][i] = dist[currx][currc] + 1;
                q.push(mp(currx+i, i));
            }
        }
    }
    int result = INT_MAX;
    for(int i=0;i<maxn;i++) {
        if(visited[st[1]][i]) result = min(result, dist[st[1]][i]);
    }
    if(result == INT_MAX) cout<<"-1\n";
    else cout<<result<<"\n";
    return 0;
}

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	484 KB	Output is correct
3	Correct	2 ms	536 KB	Output is correct
4	Correct	2 ms	536 KB	Output is correct
5	Correct	2 ms	612 KB	Output is correct
6	Correct	2 ms	616 KB	Output is correct
7	Correct	3 ms	620 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	624 KB	Output is correct
2	Correct	3 ms	684 KB	Output is correct
3	Correct	14 ms	684 KB	Output is correct
4	Correct	3 ms	684 KB	Output is correct
5	Correct	3 ms	892 KB	Output is correct
6	Correct	2 ms	892 KB	Output is correct
7	Correct	3 ms	892 KB	Output is correct
8	Correct	3 ms	948 KB	Output is correct
9	Correct	2 ms	1080 KB	Output is correct
10	Correct	4 ms	1336 KB	Output is correct
11	Correct	5 ms	1472 KB	Output is correct
12	Correct	4 ms	1484 KB	Output is correct
13	Correct	4 ms	1484 KB	Output is correct
14	Correct	5 ms	1556 KB	Output is correct
15	Correct	5 ms	1584 KB	Output is correct

Subtask #3
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	1584 KB	Output is correct
2	Correct	2 ms	1584 KB	Output is correct
3	Correct	3 ms	1584 KB	Output is correct
4	Correct	2 ms	1584 KB	Output is correct
5	Correct	3 ms	1584 KB	Output is correct
6	Correct	3 ms	1584 KB	Output is correct
7	Correct	2 ms	1584 KB	Output is correct
8	Correct	4 ms	1584 KB	Output is correct
9	Correct	3 ms	1584 KB	Output is correct
10	Correct	3 ms	1584 KB	Output is correct
11	Correct	5 ms	1656 KB	Output is correct
12	Correct	4 ms	1656 KB	Output is correct
13	Correct	4 ms	1656 KB	Output is correct
14	Correct	5 ms	1776 KB	Output is correct
15	Correct	7 ms	1776 KB	Output is correct
16	Correct	2 ms	1776 KB	Output is correct
17	Correct	9 ms	6668 KB	Output is correct
18	Correct	3 ms	6668 KB	Output is correct
19	Correct	3 ms	6668 KB	Output is correct
20	Correct	13 ms	13312 KB	Output is correct
21	Correct	3 ms	13312 KB	Output is correct
22	Correct	2 ms	13312 KB	Output is correct
23	Correct	12 ms	13312 KB	Output is correct
24	Correct	16 ms	17584 KB	Output is correct
25	Correct	17 ms	18756 KB	Output is correct
26	Correct	35 ms	18756 KB	Output is correct
27	Correct	18 ms	18756 KB	Output is correct
28	Correct	23 ms	18756 KB	Output is correct
29	Correct	18 ms	18756 KB	Output is correct
30	Correct	16 ms	18756 KB	Output is correct
31	Correct	17 ms	18756 KB	Output is correct
32	Correct	14 ms	18756 KB	Output is correct
33	Correct	19 ms	18756 KB	Output is correct
34	Correct	18 ms	18756 KB	Output is correct

Subtask #4
0 / 21.0

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

Subtask #5
0 / 43.0

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

답안 #49027

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