oj.uz

Submission #695193

# Submission time Handle Problem Language Result Execution time Memory
695193 2023-02-04T19:18:46 Z Farhan_HY Jakarta Skyscrapers (APIO15_skyscraper) C++14
57 / 100
 164 ms 119936 KB 
    #include <bits/stdc++.h>
    #define int long long
    #define float double
    #define pb push_back
    #define F first
    #define S second
    #define T int t; cin >> t; while(t--)
    #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
     
    using namespace std;
    /// Benzema is the best player in the world
    const int N = 1e6 + 6;
    const int M = 2e3 + 3;
    const int mod = 1e9 + 7;
    const int inf = 1e18;
    const int dx[] = {-1, 1, 0, 0};
    const int dy[] = {0, 0, -1, 1};
    const int LOG = 28;
    int n, m;
    int p[N], dist[N];
    vector<pair<int, int>> adj[N];
    priority_queue<pair<int, int>> q;
    bool vis[N];
    int can[M][M];
    int b[N];
     
    void dij() {
        for(int i = 1; i <= n; i++) dist[i] = inf;
        q.push({0, b[1]});
        dist[b[1]] = 0;
        while(!q.empty()) {
            int u = q.top().S;
            q.pop();
            if (vis[u]) continue;
            vis[u] = 1;
            for(auto x: adj[u]) {
                if (dist[x.F] > dist[u] + x.S)
                    dist[x.F] = dist[u] + x.S, q.push({-dist[x.F], x.F});
            }
        }
    }
     
    main() {
        IOS
        cin >> n >> m;
        for(int i = 1; i <= m; i++) {
            cin >> b[i] >> p[i];
            b[i]++;
            int j = b[i] - p[i], cnt = 1;
            while(j >= 1) {
                if (can[b[i]][j] == 0) can[b[i]][j] = inf;
                can[b[i]][j] = min(can[b[i]][j], cnt);
                j -= p[i];
                cnt++;
            }
            cnt = 1, j = b[i] + p[i];
            while(j <= n) {
                if (can[b[i]][j] == 0) can[b[i]][j] = inf;
                can[b[i]][j] = min(can[b[i]][j], cnt);
                cnt++;
                j += p[i];
            }
        }
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                if (can[i][j])
                    adj[i].push_back({j, can[i][j]});
        dij();
        if (dist[b[2]] == inf) dist[b[2]] = -1;
        cout << dist[b[2]];
    }

Compilation message

skyscraper.cpp:43:5: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   43 |     main() {
      |     ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 13 ms 23708 KB Output is correct
3 Correct 12 ms 23836 KB Output is correct
4 Correct 12 ms 23760 KB Output is correct
5 Correct 15 ms 23764 KB Output is correct
6 Correct 11 ms 23820 KB Output is correct
7 Correct 12 ms 23828 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 12 ms 23764 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 11 ms 23732 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 11 ms 23764 KB Output is correct
7 Correct 12 ms 23772 KB Output is correct
8 Correct 12 ms 23860 KB Output is correct
9 Correct 12 ms 23940 KB Output is correct
10 Correct 12 ms 24276 KB Output is correct
11 Correct 14 ms 24404 KB Output is correct
12 Correct 13 ms 23872 KB Output is correct
13 Correct 13 ms 24532 KB Output is correct
14 Correct 12 ms 24148 KB Output is correct
15 Correct 12 ms 24148 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23804 KB Output is correct
2 Correct 14 ms 23892 KB Output is correct
3 Correct 12 ms 23732 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 14 ms 23764 KB Output is correct
6 Correct 14 ms 23808 KB Output is correct
7 Correct 12 ms 23764 KB Output is correct
8 Correct 12 ms 23768 KB Output is correct
9 Correct 12 ms 23840 KB Output is correct
10 Correct 12 ms 24276 KB Output is correct
11 Correct 13 ms 24372 KB Output is correct
12 Correct 13 ms 23916 KB Output is correct
13 Correct 13 ms 24532 KB Output is correct
14 Correct 13 ms 24080 KB Output is correct
15 Correct 14 ms 24132 KB Output is correct
16 Correct 13 ms 24880 KB Output is correct
17 Correct 19 ms 30036 KB Output is correct
18 Correct 21 ms 29192 KB Output is correct
19 Correct 19 ms 27532 KB Output is correct
20 Correct 100 ms 119392 KB Output is correct
21 Correct 13 ms 24584 KB Output is correct
22 Correct 19 ms 27992 KB Output is correct
23 Correct 19 ms 28500 KB Output is correct
24 Correct 25 ms 34004 KB Output is correct
25 Correct 23 ms 30428 KB Output is correct
26 Correct 23 ms 25520 KB Output is correct
27 Correct 22 ms 25020 KB Output is correct
28 Correct 26 ms 37204 KB Output is correct
29 Correct 21 ms 25428 KB Output is correct
30 Correct 20 ms 24788 KB Output is correct
31 Correct 20 ms 25220 KB Output is correct
32 Correct 20 ms 25172 KB Output is correct
33 Correct 20 ms 26072 KB Output is correct
34 Correct 20 ms 25984 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23764 KB Output is correct
2 Correct 12 ms 23812 KB Output is correct
3 Correct 11 ms 23764 KB Output is correct
4 Correct 11 ms 23764 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 12 ms 23764 KB Output is correct
7 Correct 11 ms 23792 KB Output is correct
8 Correct 12 ms 23808 KB Output is correct
9 Correct 12 ms 23892 KB Output is correct
10 Correct 12 ms 24276 KB Output is correct
11 Correct 12 ms 24404 KB Output is correct
12 Correct 14 ms 23880 KB Output is correct
13 Correct 13 ms 24480 KB Output is correct
14 Correct 12 ms 24148 KB Output is correct
15 Correct 14 ms 24148 KB Output is correct
16 Correct 13 ms 24920 KB Output is correct
17 Correct 16 ms 29916 KB Output is correct
18 Correct 20 ms 29148 KB Output is correct
19 Correct 19 ms 27488 KB Output is correct
20 Correct 103 ms 119388 KB Output is correct
21 Correct 14 ms 24532 KB Output is correct
22 Correct 19 ms 27940 KB Output is correct
23 Correct 20 ms 28500 KB Output is correct
24 Correct 22 ms 34004 KB Output is correct
25 Correct 21 ms 30436 KB Output is correct
26 Correct 23 ms 25580 KB Output is correct
27 Correct 22 ms 24916 KB Output is correct
28 Correct 24 ms 37132 KB Output is correct
29 Correct 19 ms 25336 KB Output is correct
30 Correct 19 ms 24684 KB Output is correct
31 Correct 19 ms 25224 KB Output is correct
32 Correct 19 ms 25260 KB Output is correct
33 Correct 19 ms 26100 KB Output is correct
34 Correct 21 ms 25972 KB Output is correct
35 Correct 32 ms 47788 KB Output is correct
36 Correct 20 ms 32468 KB Output is correct
37 Correct 43 ms 60148 KB Output is correct
38 Correct 43 ms 59784 KB Output is correct
39 Correct 44 ms 60252 KB Output is correct
40 Correct 42 ms 59896 KB Output is correct
41 Correct 44 ms 59596 KB Output is correct
42 Correct 80 ms 25928 KB Output is correct
43 Correct 85 ms 25376 KB Output is correct
44 Correct 164 ms 119840 KB Output is correct
45 Correct 28 ms 32384 KB Output is correct
46 Correct 27 ms 32452 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23764 KB Output is correct
2 Correct 13 ms 23816 KB Output is correct
3 Correct 13 ms 23764 KB Output is correct
4 Correct 13 ms 23784 KB Output is correct
5 Correct 12 ms 23796 KB Output is correct
6 Correct 12 ms 23764 KB Output is correct
7 Correct 13 ms 23764 KB Output is correct
8 Correct 12 ms 23764 KB Output is correct
9 Correct 13 ms 23892 KB Output is correct
10 Correct 13 ms 24224 KB Output is correct
11 Correct 13 ms 24404 KB Output is correct
12 Correct 13 ms 23892 KB Output is correct
13 Correct 13 ms 24440 KB Output is correct
14 Correct 13 ms 24148 KB Output is correct
15 Correct 12 ms 24148 KB Output is correct
16 Correct 13 ms 24916 KB Output is correct
17 Correct 17 ms 29864 KB Output is correct
18 Correct 20 ms 29188 KB Output is correct
19 Correct 19 ms 27536 KB Output is correct
20 Correct 105 ms 119380 KB Output is correct
21 Correct 14 ms 24532 KB Output is correct
22 Correct 20 ms 27988 KB Output is correct
23 Correct 18 ms 28552 KB Output is correct
24 Correct 21 ms 34012 KB Output is correct
25 Correct 24 ms 30432 KB Output is correct
26 Correct 22 ms 25556 KB Output is correct
27 Correct 21 ms 25032 KB Output is correct
28 Correct 24 ms 37248 KB Output is correct
29 Correct 19 ms 25348 KB Output is correct
30 Correct 18 ms 24720 KB Output is correct
31 Correct 19 ms 25172 KB Output is correct
32 Correct 20 ms 25228 KB Output is correct
33 Correct 20 ms 26020 KB Output is correct
34 Correct 19 ms 26020 KB Output is correct
35 Correct 32 ms 47860 KB Output is correct
36 Correct 19 ms 32524 KB Output is correct
37 Correct 45 ms 60144 KB Output is correct
38 Correct 43 ms 59884 KB Output is correct
39 Correct 48 ms 60108 KB Output is correct
40 Correct 46 ms 59852 KB Output is correct
41 Correct 42 ms 59628 KB Output is correct
42 Correct 80 ms 25972 KB Output is correct
43 Correct 82 ms 25388 KB Output is correct
44 Correct 161 ms 119936 KB Output is correct
45 Correct 28 ms 32408 KB Output is correct
46 Correct 28 ms 32404 KB Output is correct
47 Runtime error 31 ms 48048 KB Execution killed with signal 11
48 Halted 0 ms 0 KB -