oj.uz

Submission #1031316

# Submission time Handle Problem Language Result Execution time Memory
1031316 2024-07-22T17:17:14 Z _8_8_ Jakarta Skyscrapers (APIO15_skyscraper) C++17
0 / 100
 99 ms 262144 KB 
#include <bits/stdc++.h>
 
using namespace std;
    
typedef long long ll;
const int  N = 7211017, MOD = (int)1e9+7;

const int M = 3e4 + 21;
short n,m,b[M];
int ft[M];
vector<pair<int,int>> g[N * 2];
vector<pair<short,short>> x[M];
void add(int v,int u,int w) {
    g[v].push_back({u,w});
}
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 + n;
    for(int i = 1;i < n;i++){
        sort(x[i].begin(),x[i].end());
        for(int j = 0;j < (int)x[i].size();j++){
            vector<int> f;
            for(int k = j;k < (int)x[i].size() && x[i][k].first == x[i][j].first;k++){
                j = k;
                f.push_back(b[x[i][k].second]);
            }
            sort(f.begin(),f.end());
            for(int t = 0;t < (int)f.size();t++){
                int prev = (t ? f[t - 1] : 0);
                for(int k = f[t],_=0;k >= prev;k -= i){
                    g[f[t]].push_back({k,_});
                    _++;
                }
                int nx = (t < (int)f.size() - 1 ? f[t + 1] : n - 1);
                for(int k = f[t],_=0;k <= nx;k += i){
                    g[f[t]].push_back({k,_});
                    _++;
                }
            }
        }
        x[i].clear();
    }
    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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 93 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 94 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 94 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 97 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Runtime error 99 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -