oj.uz

Submission #1031211

# Submission time Handle Problem Language Result Execution time Memory
1031211 2024-07-22T16:04:19 Z _8_8_ Jakarta Skyscrapers (APIO15_skyscraper) C++17
22 / 100
 133 ms 253012 KB 
#include <bits/stdc++.h>
 
using namespace std;
    
typedef long long ll;
const int  N = 5226152+12, MOD = (int)1e9+7;

const int M = 3e4 + 21;
short n,m,b[M],ft[M];
vector<int> g[N];
vector<pair<short,short>> x[M];
void add(int v,int u) {
    g[v].push_back(u);
    g[u].push_back(v);
}
bool sgn(int x) {
    return (x < n);
}
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;
    int num = 0;
    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){
                num += (n - x[i][j].first) / i;
            }
        }
    }
    if(num > (int)3e4 * (int)180){
        cout << -2;
        return;
    }
    for(int i = 1;i < n;i++){
        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);
                }
            }
            int v = b[x[i][j].second];
            g[v].push_back(ft[v]);
        }
        // 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(int to:g[v]){
            int w = (sgn(to) == sgn(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 49 ms 123752 KB Output is correct
2 Correct 49 ms 123656 KB Output is correct
3 Correct 51 ms 123856 KB Output is correct
4 Correct 48 ms 123808 KB Output is correct
5 Correct 50 ms 123732 KB Output is correct
6 Correct 48 ms 123728 KB Output is correct
7 Correct 48 ms 123796 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 123748 KB Output is correct
2 Correct 45 ms 123732 KB Output is correct
3 Correct 43 ms 123728 KB Output is correct
4 Correct 45 ms 123732 KB Output is correct
5 Correct 46 ms 123672 KB Output is correct
6 Correct 44 ms 123732 KB Output is correct
7 Correct 46 ms 123728 KB Output is correct
8 Correct 46 ms 123732 KB Output is correct
9 Correct 44 ms 123732 KB Output is correct
10 Correct 44 ms 123740 KB Output is correct
11 Correct 46 ms 123988 KB Output is correct
12 Correct 44 ms 123688 KB Output is correct
13 Correct 47 ms 123724 KB Output is correct
14 Correct 52 ms 123988 KB Output is correct
15 Correct 52 ms 123992 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 123728 KB Output is correct
2 Correct 45 ms 123732 KB Output is correct
3 Correct 46 ms 123732 KB Output is correct
4 Correct 45 ms 123732 KB Output is correct
5 Correct 44 ms 123728 KB Output is correct
6 Correct 47 ms 123732 KB Output is correct
7 Correct 46 ms 123728 KB Output is correct
8 Correct 46 ms 123868 KB Output is correct
9 Correct 44 ms 123736 KB Output is correct
10 Correct 45 ms 123740 KB Output is correct
11 Correct 46 ms 124048 KB Output is correct
12 Correct 43 ms 123800 KB Output is correct
13 Correct 46 ms 123732 KB Output is correct
14 Correct 49 ms 124184 KB Output is correct
15 Correct 46 ms 123988 KB Output is correct
16 Correct 46 ms 123984 KB Output is correct
17 Correct 49 ms 124508 KB Output is correct
18 Correct 48 ms 123992 KB Output is correct
19 Correct 48 ms 123996 KB Output is correct
20 Correct 48 ms 123984 KB Output is correct
21 Correct 46 ms 123728 KB Output is correct
22 Correct 46 ms 123996 KB Output is correct
23 Correct 45 ms 123988 KB Output is correct
24 Correct 50 ms 124244 KB Output is correct
25 Correct 50 ms 123988 KB Output is correct
26 Correct 51 ms 124020 KB Output is correct
27 Correct 45 ms 123988 KB Output is correct
28 Correct 48 ms 124764 KB Output is correct
29 Runtime error 122 ms 253012 KB Execution killed with signal 11
30 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 123728 KB Output is correct
2 Correct 46 ms 123736 KB Output is correct
3 Correct 49 ms 123700 KB Output is correct
4 Correct 44 ms 123736 KB Output is correct
5 Correct 45 ms 123764 KB Output is correct
6 Correct 47 ms 123732 KB Output is correct
7 Correct 45 ms 123732 KB Output is correct
8 Correct 44 ms 123732 KB Output is correct
9 Correct 46 ms 123732 KB Output is correct
10 Correct 46 ms 123732 KB Output is correct
11 Correct 47 ms 123984 KB Output is correct
12 Correct 55 ms 123732 KB Output is correct
13 Correct 45 ms 123828 KB Output is correct
14 Correct 54 ms 123988 KB Output is correct
15 Correct 47 ms 123988 KB Output is correct
16 Correct 47 ms 123896 KB Output is correct
17 Correct 48 ms 124504 KB Output is correct
18 Correct 53 ms 123988 KB Output is correct
19 Correct 55 ms 123996 KB Output is correct
20 Correct 54 ms 123984 KB Output is correct
21 Correct 47 ms 123728 KB Output is correct
22 Correct 45 ms 124128 KB Output is correct
23 Correct 46 ms 123988 KB Output is correct
24 Correct 48 ms 124240 KB Output is correct
25 Correct 47 ms 124240 KB Output is correct
26 Correct 46 ms 123992 KB Output is correct
27 Correct 49 ms 124160 KB Output is correct
28 Correct 58 ms 124752 KB Output is correct
29 Runtime error 126 ms 253008 KB Execution killed with signal 11
30 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 123740 KB Output is correct
2 Correct 45 ms 123728 KB Output is correct
3 Correct 47 ms 123860 KB Output is correct
4 Correct 45 ms 123732 KB Output is correct
5 Correct 48 ms 123732 KB Output is correct
6 Correct 49 ms 123732 KB Output is correct
7 Correct 47 ms 123740 KB Output is correct
8 Correct 46 ms 123784 KB Output is correct
9 Correct 49 ms 123728 KB Output is correct
10 Correct 47 ms 123736 KB Output is correct
11 Correct 49 ms 123972 KB Output is correct
12 Correct 49 ms 123724 KB Output is correct
13 Correct 55 ms 123732 KB Output is correct
14 Correct 50 ms 123988 KB Output is correct
15 Correct 55 ms 124212 KB Output is correct
16 Correct 47 ms 123804 KB Output is correct
17 Correct 50 ms 124304 KB Output is correct
18 Correct 48 ms 123988 KB Output is correct
19 Correct 47 ms 123956 KB Output is correct
20 Correct 51 ms 123836 KB Output is correct
21 Correct 57 ms 123772 KB Output is correct
22 Correct 49 ms 123988 KB Output is correct
23 Correct 50 ms 124032 KB Output is correct
24 Correct 51 ms 124236 KB Output is correct
25 Correct 50 ms 124252 KB Output is correct
26 Correct 50 ms 123988 KB Output is correct
27 Correct 52 ms 123988 KB Output is correct
28 Correct 52 ms 124752 KB Output is correct
29 Runtime error 133 ms 252956 KB Execution killed with signal 11
30 Halted 0 ms 0 KB -