oj.uz

Submission #914841

# Submission time Handle Problem Language Result Execution time Memory
914841 2024-01-22T18:17:34 Z sverma22 Toll (BOI17_toll) C++17
0 / 100
 31 ms 9296 KB 
#include <bits/stdc++.h>
using namespace std; 

#define int int64_t

int n, k; 

struct Info {
    int L_idx, R_idx, M_idx; 
    vector<vector<int> > lef; 
    int lef_st; 
    vector<vector<int> > rig; 
    int rig_st; 
}; 

map<int, Info> info_map; 

vector<vector<pair<int, int> > > adj; 
vector<vector<pair<int, int> > > rev_adj; 

void djikstra_left(int start_node, int st, int en, vector<int>& dist) {
    priority_queue<pair<int, int> > pq; 
    vector<bool> processed(dist.size(), false); 
    dist[start_node - st] = 0; 
    pq.push({0, start_node}); 

    while(!pq.empty()) {
        int a = pq.top().second; pq.pop(); 
        if(processed[a]) continue; 
        processed[a] = true; 

        for(auto [b, w] : rev_adj[a]) {
            // if(b > a) continue; // avoid exploring too much ya know
            if(dist[a - st] + w < dist[b - st]) {
                dist[b - st] = dist[a - st] + w; 
                pq.push({-dist[b - st], b}); 
            }
        }
    }
}

void djikstra_right(int start_node, int st, int en, vector<int>& dist) {
     priority_queue<pair<int, int> > pq; 
    vector<bool> processed(dist.size(), false); 
    dist[start_node - st] = 0; 
    pq.push({0, start_node}); 

    while(!pq.empty()) {
        int a = pq.top().second; pq.pop(); 
        if(processed[a]) continue; 
        processed[a] = true; 

        for(auto [b, w] : adj[a]) {
            // if(b < a) continue; // avoid extra exploration
            if(dist[a - st] + w < dist[b - st]) {
                dist[b - st] = dist[a - st] + w; 
                pq.push({-dist[b - st], b}); 
            }
        }
    }
}



void dvc(int l, int r, int lvl) { // may have to add more params later 
    if(l == r) return; 
    int m = (l + r) / 2;  

    // cout << l << ',' << r << '\n';

    info_map[lvl].L_idx = l; 
    info_map[lvl].R_idx = r; 
    info_map[lvl].M_idx = m; 

    vector<vector<int> > &lef = info_map[lvl].lef; 
    lef.resize(k); 

    // need to populate our fuckers and do a graph search 

    // START: l * k -> END: m * k + k - 1 
    int st = l * k; 
    int en = (m + 1) * k - 1;

    info_map[lvl].lef_st = st; 

    // cout << st << "->" << en << '\n';

    int len = en - st + 1; 

    for(int start_node = m * k; start_node < m * k + k; start_node++) {
        // cout << "START NODE: " << start_node << '\n';
        lef[start_node - m * k].resize(len, INT_MAX); 
        djikstra_left(start_node, st, en, lef[start_node - m * k]);
        // for(int node = st; node <= en; node++) {
        //     int dist = lef[start_node - m * k][node - st];
        //     if(dist == INT_MAX) {
        //         cout << -1 << ' ';
        //     } else cout << dist << ' ';
        // }
        // cout << '\n';
    }

    vector<vector<int> > &rig = info_map[lvl].rig; 
    rig.resize(k); 
    st = (m + 1) * k; 
    en = (r + 1) * k - 1;
    len = en - st + 1; 

    info_map[lvl].rig_st = st; 

    // cout << st << "->" << en << '\n';

    for(int start_node = m * k + k; start_node < m * k + 2 * k; start_node++) {
        rig[start_node - m * k - k].resize(len, INT_MAX); 
        djikstra_right(start_node, st, en, rig[start_node - m * k - k]); 
        // for(int node = st; node <= en; node++) {
        //     int dist = rig[start_node - m * k - k][node - st];
        //     if(dist == INT_MAX) {
        //         cout << -1 << ' ';
        //     } else cout << dist << ' ';
        // }
        // cout << '\n';
    }

    dvc(l, m, 2 * lvl); 
    dvc(m + 1, r, 2 * lvl + 1); 
}

int query(int a, int b) {
    return 5;

    int ai = a / k, bi = b/ k; 

    int lvl = 1; 
    while(true) {
        int m = info_map[lvl].M_idx; 
        if(ai <= m && m < bi) {
            
            int best = INT_MAX; 

            for(int i = m * k; i < m * k + k; i++) {
                int lef_cheese = info_map[lvl].lef[i - m * k][a - info_map[lvl].lef_st];
                if(lef_cheese == INT_MAX) continue; 
                for(auto [j, w] : adj[i]) {
                    int rig_cheese = info_map[lvl].rig[j - m * k - k][b - info_map[lvl].rig_st]; 
                    if(rig_cheese == INT_MAX) continue; 
                    best = min(best, lef_cheese + w + rig_cheese); 
                }
            }

            if(best == INT_MAX) best = -1; 
            return best; 
        } else if(ai > m) { // go to right side 
            lvl = 2 * lvl + 1; 
        } else { // go to left side 
            lvl = 2 * lvl; 
        }
    }

    return -1; 
}


void solve() {
    int m, o; 
    cin >> k >> n >> m >> o; 

    adj.resize(n + 1); 
    rev_adj.resize(n + 1); 

    for(int i = 0; i < m; i++) {
        int a, b, t; cin >> a >> b >> t; 
        adj[a].push_back({b, t}); 
        rev_adj[b].push_back({a, t}); 
    }

    // run the divide and conquer 
    // dvc(0, n / k, 1); 

    for(int i = 0; i < o; i++) { // process queries 
        int a, b; cin >> a >> b; 
        cout << query(a, b) << '\n';
    }

}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // #ifndef ONLINE_JUDGE
    // freopen("file.txt", "r", stdin);
    // #endif
    int t = 1; // cin >> t; 
    while(t--) {
        solve(); 
    }
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 6744 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 9296 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 6744 KB Output isn't correct
2 Halted 0 ms 0 KB -