답안 #243351

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
243351	2020-07-01T00:20:48 Z	Leonardo_Paes	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	22 / 100	47 ms	24056 KB

skyscraper

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef pair<int,pii> pip;
#define f first
#define s second
const int maxn = 3e4+10, root = 180, inf = 0x3f3f3f3f;
int b[maxn], p[maxn], dist1[maxn], dist2[maxn][root];
vector<int> doges[maxn];
int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int n, m;
    cin >> n >> m;
    for(int i=0; i<m; i++){
        cin >> b[i] >> p[i];
        doges[b[i]].push_back(p[i]);
    }
    priority_queue<pip, vector<pip>, greater<pip>> fila;
    memset(dist1, inf, sizeof dist1);
    memset(dist2, inf, sizeof dist2);
    fila.push({0, {b[0], p[0]}});
    while(!fila.empty()){
        int d = fila.top().f, u = fila.top().s.f, power = fila.top().s.s;
        fila.pop();
        if(power <= root){
            if(dist2[u][power] != inf) continue;
            dist2[u][power] = d;
            if(u + power < n) fila.push({d + 1, {u + power, power}});
            if(u - power >= 0) fila.push({d + 1, {u - power, power}});
            for(auto x : doges[u]){
                if(u + x < n) fila.push({d + 1, {u + x, x}});
                if(u - x >= 0) fila.push({d + 1, {u - x, x}});
            }
        }
        else{
            if(dist1[u] != inf) continue;
            dist1[u] = d;
            if(u + power < n) fila.push({d + 1, {u + power, power}});
            if(u - power >= 0) fila.push({d + 1, {u - power, power}});
            for(auto x : doges[u]){
                if(u + x < n) fila.push({d + 1, {u + x, x}});
                if(u - x >= 0) fila.push({d + 1, {u - x, x}});
            }
        }
    }
    int ans = dist1[b[1]];
    for(int i=1; i<=root; i++) ans = min(ans, dist2[b[1]][i]);
    cout << (ans == inf ? -1 : ans) << "\n";
    return 0;
}

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	16 ms	22272 KB	Output is correct
2	Correct	16 ms	22272 KB	Output is correct
3	Correct	16 ms	22400 KB	Output is correct
4	Correct	17 ms	22400 KB	Output is correct
5	Correct	19 ms	22272 KB	Output is correct
6	Correct	16 ms	22272 KB	Output is correct
7	Correct	16 ms	22272 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	17 ms	22272 KB	Output is correct
2	Correct	18 ms	22272 KB	Output is correct
3	Correct	17 ms	22272 KB	Output is correct
4	Correct	17 ms	22272 KB	Output is correct
5	Correct	18 ms	22272 KB	Output is correct
6	Correct	16 ms	22272 KB	Output is correct
7	Correct	16 ms	22272 KB	Output is correct
8	Correct	16 ms	22272 KB	Output is correct
9	Correct	16 ms	22400 KB	Output is correct
10	Correct	17 ms	22400 KB	Output is correct
11	Correct	32 ms	22980 KB	Output is correct
12	Correct	23 ms	23296 KB	Output is correct
13	Correct	16 ms	22400 KB	Output is correct
14	Correct	38 ms	24056 KB	Output is correct
15	Correct	38 ms	24056 KB	Output is correct

Subtask #3
0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	16 ms	22272 KB	Output is correct
2	Correct	16 ms	22272 KB	Output is correct
3	Correct	16 ms	22400 KB	Output is correct
4	Correct	16 ms	22272 KB	Output is correct
5	Correct	17 ms	22272 KB	Output is correct
6	Correct	16 ms	22272 KB	Output is correct
7	Correct	16 ms	22272 KB	Output is correct
8	Correct	16 ms	22272 KB	Output is correct
9	Correct	16 ms	22272 KB	Output is correct
10	Correct	17 ms	22400 KB	Output is correct
11	Correct	31 ms	22912 KB	Output is correct
12	Correct	27 ms	23296 KB	Output is correct
13	Correct	18 ms	22400 KB	Output is correct
14	Correct	40 ms	24056 KB	Output is correct
15	Correct	38 ms	24056 KB	Output is correct
16	Correct	16 ms	22400 KB	Output is correct
17	Correct	26 ms	22528 KB	Output is correct
18	Correct	16 ms	22400 KB	Output is correct
19	Correct	16 ms	22272 KB	Output is correct
20	Correct	17 ms	22400 KB	Output is correct
21	Correct	17 ms	22400 KB	Output is correct
22	Correct	16 ms	22272 KB	Output is correct
23	Incorrect	20 ms	22400 KB	Output isn't correct
24	Halted	0 ms	0 KB	-

Subtask #4
0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	18 ms	22272 KB	Output is correct
2	Correct	16 ms	22272 KB	Output is correct
3	Correct	18 ms	22272 KB	Output is correct
4	Correct	17 ms	22272 KB	Output is correct
5	Correct	17 ms	22272 KB	Output is correct
6	Correct	16 ms	22272 KB	Output is correct
7	Correct	16 ms	22272 KB	Output is correct
8	Correct	16 ms	22272 KB	Output is correct
9	Correct	16 ms	22272 KB	Output is correct
10	Correct	19 ms	22400 KB	Output is correct
11	Correct	30 ms	22852 KB	Output is correct
12	Correct	24 ms	23296 KB	Output is correct
13	Correct	18 ms	22400 KB	Output is correct
14	Correct	38 ms	24056 KB	Output is correct
15	Correct	40 ms	24056 KB	Output is correct
16	Correct	16 ms	22272 KB	Output is correct
17	Correct	26 ms	22528 KB	Output is correct
18	Correct	16 ms	22400 KB	Output is correct
19	Correct	17 ms	22272 KB	Output is correct
20	Correct	18 ms	22400 KB	Output is correct
21	Correct	16 ms	22272 KB	Output is correct
22	Correct	21 ms	22400 KB	Output is correct
23	Incorrect	20 ms	22400 KB	Output isn't correct
24	Halted	0 ms	0 KB	-

Subtask #5
0 / 43.0

#	결과	실행 시간	메모리	Grader output
1	Correct	16 ms	22272 KB	Output is correct
2	Correct	16 ms	22400 KB	Output is correct
3	Correct	16 ms	22400 KB	Output is correct
4	Correct	16 ms	22272 KB	Output is correct
5	Correct	16 ms	22272 KB	Output is correct
6	Correct	18 ms	22272 KB	Output is correct
7	Correct	17 ms	22272 KB	Output is correct
8	Correct	18 ms	22272 KB	Output is correct
9	Correct	16 ms	22272 KB	Output is correct
10	Correct	22 ms	22400 KB	Output is correct
11	Correct	31 ms	22912 KB	Output is correct
12	Correct	22 ms	23296 KB	Output is correct
13	Correct	18 ms	22400 KB	Output is correct
14	Correct	38 ms	24056 KB	Output is correct
15	Correct	47 ms	24056 KB	Output is correct
16	Correct	21 ms	22400 KB	Output is correct
17	Correct	29 ms	22656 KB	Output is correct
18	Correct	16 ms	22272 KB	Output is correct
19	Correct	16 ms	22272 KB	Output is correct
20	Correct	17 ms	22400 KB	Output is correct
21	Correct	17 ms	22272 KB	Output is correct
22	Correct	17 ms	22400 KB	Output is correct
23	Incorrect	19 ms	22400 KB	Output isn't correct
24	Halted	0 ms	0 KB	-

답안 #243351

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