답안 #243867

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
243867	2020-07-02T03:36:01 Z	Leonardo_Paes	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	316 ms	238324 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, magic = 2000, inf = 0x3f3f3f3f;
int b[maxn], p[maxn], dist1[maxn], dist2[maxn][magic+5];
vector<int> doges[maxn];
bool mark[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(i);
    }
    priority_queue<pip, vector<pip>, greater<pip>> fila;
    memset(dist1, inf, sizeof dist1);
    memset(dist2, inf, sizeof dist2);
    fila.push({0, {b[0], 0}});
    mark[0] = 1;
    while(!fila.empty()){
        int d = fila.top().f, u = fila.top().s.f, id = fila.top().s.s, power = p[fila.top().s.s];
        fila.pop();
        if(power <= magic){
            if(dist2[u][power] == inf) dist2[u][power] = d;
            if(u + power < n and dist2[u + power][power] == inf){
                fila.push({d + 1, {u + power, id}});
                dist2[u + power][power] = d + 1;
            }
            if(u - power >= 0 and dist2[u - power][power] == inf){
                fila.push({d + 1, {u - power, id}});
                dist2[u - power][power] = d + 1;
            }
        }
        else{
            if(dist1[u] == inf) dist1[u] = d;
            if(mark[id]) continue;
            mark[id] = 1;
            for(int v=u+power, qtd=1; v<n; v+=power, qtd++) fila.push({d + qtd, {v, id}});
            for(int v=u-power, qtd=1; v>=0; v-=power, qtd++) fila.push({d + qtd, {v, id}});
        }
        if(!doges[u].empty()){
            for(auto v : doges[u]) fila.push({d, {u, v}});
            doges[u].clear();
        }
    }
    int ans = dist1[b[1]];
    for(int i=1; i<=magic; 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	119 ms	236664 KB	Output is correct
2	Correct	124 ms	236664 KB	Output is correct
3	Correct	122 ms	236664 KB	Output is correct
4	Correct	133 ms	236664 KB	Output is correct
5	Correct	122 ms	236664 KB	Output is correct
6	Correct	123 ms	236664 KB	Output is correct
7	Correct	122 ms	236664 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	126 ms	236664 KB	Output is correct
2	Correct	129 ms	236680 KB	Output is correct
3	Correct	121 ms	236664 KB	Output is correct
4	Correct	130 ms	236664 KB	Output is correct
5	Correct	135 ms	236664 KB	Output is correct
6	Correct	125 ms	236668 KB	Output is correct
7	Correct	122 ms	236708 KB	Output is correct
8	Correct	120 ms	236664 KB	Output is correct
9	Correct	120 ms	236664 KB	Output is correct
10	Correct	131 ms	236664 KB	Output is correct
11	Correct	123 ms	236924 KB	Output is correct
12	Correct	126 ms	236792 KB	Output is correct
13	Correct	127 ms	236792 KB	Output is correct
14	Correct	124 ms	236792 KB	Output is correct
15	Correct	123 ms	236792 KB	Output is correct

Subtask #3
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	131 ms	236688 KB	Output is correct
2	Correct	126 ms	236664 KB	Output is correct
3	Correct	131 ms	236624 KB	Output is correct
4	Correct	123 ms	236664 KB	Output is correct
5	Correct	131 ms	236720 KB	Output is correct
6	Correct	120 ms	236664 KB	Output is correct
7	Correct	133 ms	236664 KB	Output is correct
8	Correct	123 ms	236664 KB	Output is correct
9	Correct	122 ms	236664 KB	Output is correct
10	Correct	131 ms	236664 KB	Output is correct
11	Correct	122 ms	236792 KB	Output is correct
12	Correct	131 ms	236772 KB	Output is correct
13	Correct	128 ms	236792 KB	Output is correct
14	Correct	136 ms	236796 KB	Output is correct
15	Correct	134 ms	236792 KB	Output is correct
16	Correct	131 ms	236664 KB	Output is correct
17	Correct	128 ms	236920 KB	Output is correct
18	Correct	121 ms	236664 KB	Output is correct
19	Correct	132 ms	236664 KB	Output is correct
20	Correct	124 ms	236792 KB	Output is correct
21	Correct	121 ms	236664 KB	Output is correct
22	Correct	121 ms	236696 KB	Output is correct
23	Correct	133 ms	236664 KB	Output is correct
24	Correct	126 ms	236792 KB	Output is correct
25	Correct	126 ms	236792 KB	Output is correct
26	Correct	135 ms	236792 KB	Output is correct
27	Correct	126 ms	236792 KB	Output is correct
28	Correct	129 ms	236860 KB	Output is correct
29	Correct	141 ms	236664 KB	Output is correct
30	Correct	125 ms	236712 KB	Output is correct
31	Correct	124 ms	236664 KB	Output is correct
32	Correct	129 ms	236664 KB	Output is correct
33	Correct	150 ms	236792 KB	Output is correct
34	Correct	146 ms	236792 KB	Output is correct

Subtask #4
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	132 ms	236664 KB	Output is correct
2	Correct	129 ms	236792 KB	Output is correct
3	Correct	137 ms	236664 KB	Output is correct
4	Correct	141 ms	236664 KB	Output is correct
5	Correct	124 ms	236656 KB	Output is correct
6	Correct	135 ms	236792 KB	Output is correct
7	Correct	122 ms	236792 KB	Output is correct
8	Correct	134 ms	236664 KB	Output is correct
9	Correct	132 ms	236664 KB	Output is correct
10	Correct	126 ms	236792 KB	Output is correct
11	Correct	125 ms	236792 KB	Output is correct
12	Correct	121 ms	236792 KB	Output is correct
13	Correct	133 ms	236792 KB	Output is correct
14	Correct	126 ms	236792 KB	Output is correct
15	Correct	124 ms	236768 KB	Output is correct
16	Correct	121 ms	236664 KB	Output is correct
17	Correct	124 ms	236792 KB	Output is correct
18	Correct	122 ms	236792 KB	Output is correct
19	Correct	133 ms	236792 KB	Output is correct
20	Correct	128 ms	236792 KB	Output is correct
21	Correct	120 ms	236664 KB	Output is correct
22	Correct	120 ms	236664 KB	Output is correct
23	Correct	122 ms	236792 KB	Output is correct
24	Correct	125 ms	236792 KB	Output is correct
25	Correct	126 ms	236792 KB	Output is correct
26	Correct	133 ms	236792 KB	Output is correct
27	Correct	122 ms	236792 KB	Output is correct
28	Correct	125 ms	236792 KB	Output is correct
29	Correct	130 ms	236664 KB	Output is correct
30	Correct	124 ms	236664 KB	Output is correct
31	Correct	132 ms	236704 KB	Output is correct
32	Correct	131 ms	236664 KB	Output is correct
33	Correct	140 ms	236792 KB	Output is correct
34	Correct	137 ms	236796 KB	Output is correct
35	Correct	160 ms	237432 KB	Output is correct
36	Correct	131 ms	236888 KB	Output is correct
37	Correct	178 ms	237752 KB	Output is correct
38	Correct	172 ms	237880 KB	Output is correct
39	Correct	179 ms	237968 KB	Output is correct
40	Correct	176 ms	237880 KB	Output is correct
41	Correct	167 ms	237880 KB	Output is correct
42	Correct	139 ms	237876 KB	Output is correct
43	Correct	133 ms	237816 KB	Output is correct
44	Correct	135 ms	237860 KB	Output is correct
45	Correct	219 ms	237884 KB	Output is correct
46	Correct	210 ms	237812 KB	Output is correct

Subtask #5
0 / 43.0

#	결과	실행 시간	메모리	Grader output
1	Correct	122 ms	236664 KB	Output is correct
2	Correct	135 ms	236664 KB	Output is correct
3	Correct	127 ms	236792 KB	Output is correct
4	Correct	127 ms	236664 KB	Output is correct
5	Correct	134 ms	236668 KB	Output is correct
6	Correct	124 ms	236664 KB	Output is correct
7	Correct	126 ms	236692 KB	Output is correct
8	Correct	124 ms	236668 KB	Output is correct
9	Correct	121 ms	236664 KB	Output is correct
10	Correct	123 ms	236668 KB	Output is correct
11	Correct	123 ms	236792 KB	Output is correct
12	Correct	121 ms	236792 KB	Output is correct
13	Correct	125 ms	236792 KB	Output is correct
14	Correct	127 ms	236792 KB	Output is correct
15	Correct	128 ms	236900 KB	Output is correct
16	Correct	131 ms	236664 KB	Output is correct
17	Correct	137 ms	236792 KB	Output is correct
18	Correct	124 ms	236664 KB	Output is correct
19	Correct	130 ms	236752 KB	Output is correct
20	Correct	125 ms	236716 KB	Output is correct
21	Correct	123 ms	236664 KB	Output is correct
22	Correct	123 ms	236664 KB	Output is correct
23	Correct	133 ms	236792 KB	Output is correct
24	Correct	125 ms	236744 KB	Output is correct
25	Correct	125 ms	236792 KB	Output is correct
26	Correct	130 ms	236792 KB	Output is correct
27	Correct	127 ms	236792 KB	Output is correct
28	Correct	141 ms	236792 KB	Output is correct
29	Correct	126 ms	236664 KB	Output is correct
30	Correct	126 ms	236672 KB	Output is correct
31	Correct	129 ms	236664 KB	Output is correct
32	Correct	123 ms	236664 KB	Output is correct
33	Correct	139 ms	236712 KB	Output is correct
34	Correct	141 ms	236792 KB	Output is correct
35	Correct	164 ms	237564 KB	Output is correct
36	Correct	127 ms	236792 KB	Output is correct
37	Correct	176 ms	237752 KB	Output is correct
38	Correct	178 ms	237880 KB	Output is correct
39	Correct	164 ms	237884 KB	Output is correct
40	Correct	164 ms	237880 KB	Output is correct
41	Correct	173 ms	237868 KB	Output is correct
42	Correct	144 ms	237816 KB	Output is correct
43	Correct	143 ms	237856 KB	Output is correct
44	Correct	133 ms	237928 KB	Output is correct
45	Correct	205 ms	237816 KB	Output is correct
46	Correct	212 ms	237792 KB	Output is correct
47	Incorrect	316 ms	238324 KB	Output isn't correct
48	Halted	0 ms	0 KB	-

답안 #243867

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