답안 #1094446

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1094446	2024-09-29T16:09:39 Z	ShaShi	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	22 / 100	14 ms	24156 KB

skyscraper

#include <bits/stdc++.h>
 
// #define int long long 
 
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
 
#define F first 
#define S second
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
#define kill(x) cout << x << "\n", exit(0);
#define pii pair<int, int>
#define pll pair<long long, long long>
#define endl "\n"
 
 
 
using namespace std;
typedef long long ll;
// typedef __int128_t lll;
typedef long double ld;

 
const int MAXN = (int)1e6 + 7;
const int MOD = 998244353;
const ll INF = (ll)1e9 + 7;

 
int n, m, k, tmp, t, tmp2, tmp3, tmp4, u, v, w, flag, q, ans, N, l, r, mid;
int dis[MAXN], ind[MAXN], val[MAXN];
vector<int> arr[MAXN];
priority_queue<pii, vector<pii>, greater<pii>> pq;


inline void relax(int v, int u) {
    if (val[v] == val[u]) return;
    if (dis[u] <= dis[v]+abs(ind[u]-ind[v])/val[v]) return;

    dis[u] = dis[v] + abs(ind[u]-ind[v])/val[v];

    pq.push({dis[u], u});
}


int32_t main() {
    #ifdef LOCAL
    freopen("inp.in", "r", stdin);
    freopen("res.out", "w", stdout);
    #else
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #endif


    cin >> n >> m;

    for (int i=1; i<=m; i++) {
        cin >> ind[i] >> val[i]; arr[ind[i]].pb(i);
    }

    val[2] = MAXN;

    fill_n(dis, m+7, INF); 

    dis[1] = 0; pq.push({0, 1});

    while (pq.size()) {
        auto cur = pq.top(); pq.pop();

        if (dis[cur.S] != cur.F) continue;

        // cout << "! " << cur.S << " " << cur.F << endl;

        v = cur.S;

        if (v == 2) kill(dis[v]);

        for (int i=ind[v]; i<=n; i+=val[v]) for (auto cur:arr[i]) relax(v, cur);
        for (int i=ind[v]; i>0; i-=val[v]) for (auto cur:arr[i]) relax(v, cur);
    }

    kill(-1);

    
    return 0;
}

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	23900 KB	Output is correct
2	Correct	10 ms	23900 KB	Output is correct
3	Correct	10 ms	23900 KB	Output is correct
4	Correct	11 ms	23900 KB	Output is correct
5	Correct	11 ms	23916 KB	Output is correct
6	Correct	11 ms	23968 KB	Output is correct
7	Correct	10 ms	23944 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	23896 KB	Output is correct
2	Correct	11 ms	23960 KB	Output is correct
3	Correct	10 ms	23900 KB	Output is correct
4	Correct	11 ms	23944 KB	Output is correct
5	Correct	11 ms	23912 KB	Output is correct
6	Correct	11 ms	23896 KB	Output is correct
7	Correct	11 ms	23900 KB	Output is correct
8	Correct	11 ms	23900 KB	Output is correct
9	Correct	11 ms	23960 KB	Output is correct
10	Correct	11 ms	23900 KB	Output is correct
11	Correct	11 ms	23900 KB	Output is correct
12	Correct	11 ms	24152 KB	Output is correct
13	Correct	11 ms	23900 KB	Output is correct
14	Correct	12 ms	24128 KB	Output is correct
15	Correct	13 ms	23900 KB	Output is correct

Subtask #3
0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	23900 KB	Output is correct
2	Correct	14 ms	24076 KB	Output is correct
3	Correct	11 ms	23896 KB	Output is correct
4	Correct	10 ms	23900 KB	Output is correct
5	Correct	10 ms	23900 KB	Output is correct
6	Correct	10 ms	23900 KB	Output is correct
7	Correct	10 ms	23896 KB	Output is correct
8	Correct	9 ms	23816 KB	Output is correct
9	Correct	11 ms	23900 KB	Output is correct
10	Correct	10 ms	23900 KB	Output is correct
11	Correct	10 ms	23900 KB	Output is correct
12	Correct	10 ms	23900 KB	Output is correct
13	Correct	11 ms	23808 KB	Output is correct
14	Correct	11 ms	23900 KB	Output is correct
15	Correct	11 ms	23956 KB	Output is correct
16	Correct	12 ms	23896 KB	Output is correct
17	Correct	11 ms	24040 KB	Output is correct
18	Correct	10 ms	23900 KB	Output is correct
19	Correct	10 ms	23896 KB	Output is correct
20	Correct	10 ms	23900 KB	Output is correct
21	Correct	10 ms	23900 KB	Output is correct
22	Correct	11 ms	23900 KB	Output is correct
23	Correct	11 ms	23992 KB	Output is correct
24	Correct	12 ms	24032 KB	Output is correct
25	Correct	12 ms	23960 KB	Output is correct
26	Correct	9 ms	23900 KB	Output is correct
27	Correct	11 ms	23900 KB	Output is correct
28	Incorrect	10 ms	23900 KB	Output isn't correct
29	Halted	0 ms	0 KB	-

Subtask #4
0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	23900 KB	Output is correct
2	Correct	10 ms	23964 KB	Output is correct
3	Correct	10 ms	23900 KB	Output is correct
4	Correct	11 ms	23900 KB	Output is correct
5	Correct	10 ms	23720 KB	Output is correct
6	Correct	10 ms	23956 KB	Output is correct
7	Correct	10 ms	23760 KB	Output is correct
8	Correct	10 ms	23900 KB	Output is correct
9	Correct	10 ms	23900 KB	Output is correct
10	Correct	10 ms	23900 KB	Output is correct
11	Correct	10 ms	24008 KB	Output is correct
12	Correct	11 ms	23824 KB	Output is correct
13	Correct	10 ms	23900 KB	Output is correct
14	Correct	11 ms	23900 KB	Output is correct
15	Correct	11 ms	23944 KB	Output is correct
16	Correct	10 ms	23900 KB	Output is correct
17	Correct	12 ms	23904 KB	Output is correct
18	Correct	12 ms	23900 KB	Output is correct
19	Correct	11 ms	23992 KB	Output is correct
20	Correct	10 ms	23900 KB	Output is correct
21	Correct	10 ms	23916 KB	Output is correct
22	Correct	11 ms	23900 KB	Output is correct
23	Correct	10 ms	23804 KB	Output is correct
24	Correct	11 ms	23824 KB	Output is correct
25	Correct	11 ms	23900 KB	Output is correct
26	Correct	11 ms	24016 KB	Output is correct
27	Correct	11 ms	23900 KB	Output is correct
28	Incorrect	10 ms	23904 KB	Output isn't correct
29	Halted	0 ms	0 KB	-

Subtask #5
0 / 43.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	23900 KB	Output is correct
2	Correct	10 ms	23900 KB	Output is correct
3	Correct	10 ms	23900 KB	Output is correct
4	Correct	10 ms	23960 KB	Output is correct
5	Correct	11 ms	24156 KB	Output is correct
6	Correct	10 ms	23900 KB	Output is correct
7	Correct	11 ms	23900 KB	Output is correct
8	Correct	10 ms	23900 KB	Output is correct
9	Correct	10 ms	23944 KB	Output is correct
10	Correct	10 ms	23900 KB	Output is correct
11	Correct	10 ms	23900 KB	Output is correct
12	Correct	10 ms	24044 KB	Output is correct
13	Correct	11 ms	23900 KB	Output is correct
14	Correct	11 ms	24056 KB	Output is correct
15	Correct	10 ms	23900 KB	Output is correct
16	Correct	11 ms	23896 KB	Output is correct
17	Correct	10 ms	23900 KB	Output is correct
18	Correct	10 ms	24008 KB	Output is correct
19	Correct	10 ms	23900 KB	Output is correct
20	Correct	12 ms	23896 KB	Output is correct
21	Correct	10 ms	23900 KB	Output is correct
22	Correct	10 ms	23900 KB	Output is correct
23	Correct	10 ms	23900 KB	Output is correct
24	Correct	10 ms	23900 KB	Output is correct
25	Correct	10 ms	23900 KB	Output is correct
26	Correct	10 ms	23900 KB	Output is correct
27	Correct	9 ms	23836 KB	Output is correct
28	Incorrect	10 ms	23900 KB	Output isn't correct
29	Halted	0 ms	0 KB	-

답안 #1094446

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