oj.uz

Submission #1031138

# Submission time Handle Problem Language Result Execution time Memory
1031138 2024-07-22T15:24:51 Z _8_8_ Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 642 ms 262144 KB 
#include <bits/stdc++.h>
 
using namespace std;
    
typedef long long ll;
const int  N = 174 *(int)3e4 + 1, MOD = (int)1e9+7;

const int M = 3e4 + 21;
int n,m,b[M],ft[M];
vector<pair<int,int>> x[M],g[N];
void add(int v,int u) {
    g[v].push_back({u,1});
    g[u].push_back({v,1});
}
int d[N];
void test() {
    cin >> n >> m;
    for(int i = 0;i < m;i++) {
        int p;
        cin >> b[i] >> p;
        int d = b[i] % p;
        x[p].emplace_back(d,i);
    }
    int it = n - 1;
    for(int i = 1;i < n;i++){
        sort(x[i].begin(),x[i].end());
        for(int j = 0;j < (int)x[i].size();j++){
            if(!j || x[i][j].first != x[i][j - 1].first){
                // cout << i << ' ';
                for(int k = x[i][j].first;k < n;k += i){
                    ft[k] = ++it;
                    if(k - i >= 0){
                        add(ft[k - i],ft[k]);
                    }
                    g[ft[k]].push_back({k,0});
                }
            }
            int v = b[x[i][j].second];
            g[v].push_back({ft[v],0});
        }
        // cout << '\n';
    }
    set<pair<int,int>> st;
    for(int i = 0;i <= it;i++){
        d[i] = 1e9;
    }
    st.insert({0,b[0]});
    d[b[0]] = 0;
    while(!st.empty()){
        auto [c,v] = (*st.begin());
        st.erase(st.begin());
        for(auto [to,w]:g[v]){
            if(d[to] > d[v] + w){
                st.erase({d[to],to});
                d[to] = d[v] + w;
                st.insert({d[to],to});
            }
        }
    }
    if(d[b[1]] == 1e9){
        d[b[1]] = -1;
    }
    cout << d[b[1]];
}
int main() {
    ios_base::sync_with_stdio(false);cin.tie(0);
    int t = 1; 
    // cin >> t;
    while(t--) {
        test();
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 125524 KB Output is correct
2 Correct 49 ms 123636 KB Output is correct
3 Correct 50 ms 123724 KB Output is correct
4 Correct 49 ms 123728 KB Output is correct
5 Correct 49 ms 123736 KB Output is correct
6 Correct 49 ms 123732 KB Output is correct
7 Correct 49 ms 123740 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 123732 KB Output is correct
2 Correct 52 ms 123728 KB Output is correct
3 Correct 53 ms 123712 KB Output is correct
4 Correct 49 ms 125448 KB Output is correct
5 Correct 51 ms 123728 KB Output is correct
6 Correct 51 ms 123728 KB Output is correct
7 Correct 50 ms 123732 KB Output is correct
8 Correct 50 ms 123604 KB Output is correct
9 Correct 50 ms 123588 KB Output is correct
10 Correct 48 ms 123728 KB Output is correct
11 Correct 52 ms 123952 KB Output is correct
12 Correct 53 ms 125648 KB Output is correct
13 Correct 55 ms 123728 KB Output is correct
14 Correct 58 ms 123984 KB Output is correct
15 Correct 52 ms 123984 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 123732 KB Output is correct
2 Correct 48 ms 123732 KB Output is correct
3 Correct 56 ms 123728 KB Output is correct
4 Correct 51 ms 123732 KB Output is correct
5 Correct 49 ms 123732 KB Output is correct
6 Correct 52 ms 123732 KB Output is correct
7 Correct 48 ms 123828 KB Output is correct
8 Correct 48 ms 123732 KB Output is correct
9 Correct 53 ms 123728 KB Output is correct
10 Correct 51 ms 123732 KB Output is correct
11 Correct 52 ms 125776 KB Output is correct
12 Correct 49 ms 123716 KB Output is correct
13 Correct 50 ms 123732 KB Output is correct
14 Correct 51 ms 125780 KB Output is correct
15 Correct 54 ms 123984 KB Output is correct
16 Correct 49 ms 123988 KB Output is correct
17 Correct 57 ms 124656 KB Output is correct
18 Correct 50 ms 125776 KB Output is correct
19 Correct 50 ms 123908 KB Output is correct
20 Correct 50 ms 123988 KB Output is correct
21 Correct 57 ms 123820 KB Output is correct
22 Correct 54 ms 123996 KB Output is correct
23 Correct 54 ms 123988 KB Output is correct
24 Correct 59 ms 124496 KB Output is correct
25 Correct 54 ms 124004 KB Output is correct
26 Correct 53 ms 126032 KB Output is correct
27 Correct 56 ms 123988 KB Output is correct
28 Correct 54 ms 125012 KB Output is correct
29 Correct 62 ms 126800 KB Output is correct
30 Correct 53 ms 124496 KB Output is correct
31 Correct 55 ms 125380 KB Output is correct
32 Correct 54 ms 125008 KB Output is correct
33 Correct 73 ms 129872 KB Output is correct
34 Correct 71 ms 129872 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 123624 KB Output is correct
2 Correct 50 ms 123732 KB Output is correct
3 Correct 55 ms 123728 KB Output is correct
4 Correct 49 ms 123728 KB Output is correct
5 Correct 50 ms 123728 KB Output is correct
6 Correct 50 ms 123740 KB Output is correct
7 Correct 49 ms 123728 KB Output is correct
8 Correct 54 ms 123824 KB Output is correct
9 Correct 52 ms 123740 KB Output is correct
10 Correct 49 ms 125508 KB Output is correct
11 Correct 50 ms 123988 KB Output is correct
12 Correct 51 ms 123840 KB Output is correct
13 Correct 49 ms 123728 KB Output is correct
14 Correct 52 ms 124016 KB Output is correct
15 Correct 52 ms 123988 KB Output is correct
16 Correct 51 ms 125780 KB Output is correct
17 Correct 52 ms 124540 KB Output is correct
18 Correct 49 ms 123988 KB Output is correct
19 Correct 51 ms 125872 KB Output is correct
20 Correct 52 ms 123984 KB Output is correct
21 Correct 51 ms 123732 KB Output is correct
22 Correct 51 ms 123984 KB Output is correct
23 Correct 51 ms 123988 KB Output is correct
24 Correct 57 ms 124524 KB Output is correct
25 Correct 58 ms 124248 KB Output is correct
26 Correct 52 ms 124244 KB Output is correct
27 Correct 51 ms 126016 KB Output is correct
28 Correct 56 ms 125012 KB Output is correct
29 Correct 59 ms 126800 KB Output is correct
30 Correct 52 ms 124500 KB Output is correct
31 Correct 58 ms 125524 KB Output is correct
32 Correct 53 ms 124896 KB Output is correct
33 Correct 80 ms 129876 KB Output is correct
34 Correct 71 ms 129948 KB Output is correct
35 Correct 84 ms 129616 KB Output is correct
36 Correct 55 ms 124752 KB Output is correct
37 Correct 94 ms 133712 KB Output is correct
38 Correct 96 ms 133452 KB Output is correct
39 Correct 104 ms 133384 KB Output is correct
40 Correct 92 ms 133208 KB Output is correct
41 Correct 103 ms 134992 KB Output is correct
42 Correct 54 ms 124792 KB Output is correct
43 Correct 54 ms 124752 KB Output is correct
44 Correct 54 ms 124628 KB Output is correct
45 Correct 162 ms 149292 KB Output is correct
46 Correct 179 ms 149540 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 123732 KB Output is correct
2 Correct 50 ms 123716 KB Output is correct
3 Correct 51 ms 123728 KB Output is correct
4 Correct 49 ms 123732 KB Output is correct
5 Correct 53 ms 123668 KB Output is correct
6 Correct 58 ms 123732 KB Output is correct
7 Correct 49 ms 123732 KB Output is correct
8 Correct 49 ms 123740 KB Output is correct
9 Correct 49 ms 123732 KB Output is correct
10 Correct 49 ms 123868 KB Output is correct
11 Correct 50 ms 123920 KB Output is correct
12 Correct 50 ms 123724 KB Output is correct
13 Correct 50 ms 123724 KB Output is correct
14 Correct 51 ms 123984 KB Output is correct
15 Correct 53 ms 124228 KB Output is correct
16 Correct 51 ms 123996 KB Output is correct
17 Correct 55 ms 124504 KB Output is correct
18 Correct 51 ms 124040 KB Output is correct
19 Correct 50 ms 123836 KB Output is correct
20 Correct 52 ms 123984 KB Output is correct
21 Correct 50 ms 123728 KB Output is correct
22 Correct 50 ms 123992 KB Output is correct
23 Correct 52 ms 123984 KB Output is correct
24 Correct 55 ms 124500 KB Output is correct
25 Correct 51 ms 124164 KB Output is correct
26 Correct 48 ms 124240 KB Output is correct
27 Correct 52 ms 125776 KB Output is correct
28 Correct 57 ms 125020 KB Output is correct
29 Correct 62 ms 126800 KB Output is correct
30 Correct 52 ms 124552 KB Output is correct
31 Correct 55 ms 125448 KB Output is correct
32 Correct 54 ms 125020 KB Output is correct
33 Correct 72 ms 129876 KB Output is correct
34 Correct 74 ms 129876 KB Output is correct
35 Correct 81 ms 129620 KB Output is correct
36 Correct 52 ms 126540 KB Output is correct
37 Correct 97 ms 133712 KB Output is correct
38 Correct 95 ms 133460 KB Output is correct
39 Correct 96 ms 133200 KB Output is correct
40 Correct 103 ms 133204 KB Output is correct
41 Correct 103 ms 133368 KB Output is correct
42 Correct 56 ms 124756 KB Output is correct
43 Correct 57 ms 124756 KB Output is correct
44 Correct 53 ms 124560 KB Output is correct
45 Correct 173 ms 149524 KB Output is correct
46 Correct 176 ms 149400 KB Output is correct
47 Correct 295 ms 163156 KB Output is correct
48 Correct 76 ms 136080 KB Output is correct
49 Correct 69 ms 133184 KB Output is correct
50 Correct 66 ms 131412 KB Output is correct
51 Correct 129 ms 140960 KB Output is correct
52 Correct 138 ms 142316 KB Output is correct
53 Correct 71 ms 130900 KB Output is correct
54 Correct 53 ms 125268 KB Output is correct
55 Correct 57 ms 126532 KB Output is correct
56 Correct 61 ms 126572 KB Output is correct
57 Correct 170 ms 146016 KB Output is correct
58 Correct 61 ms 127828 KB Output is correct
59 Correct 68 ms 129336 KB Output is correct
60 Correct 73 ms 130636 KB Output is correct
61 Correct 73 ms 131916 KB Output is correct
62 Correct 117 ms 149584 KB Output is correct
63 Correct 642 ms 242260 KB Output is correct
64 Runtime error 249 ms 262144 KB Execution killed with signal 9
65 Halted 0 ms 0 KB -