Submission #914854

#	Time	Username	Problem	Language	Result	Execution time	Memory
914854		sverma22	Toll (BOI17_toll)	C++17	0 / 100	34 ms	16648 KiB

toll

#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); 
    // assert(0 <= start_node - st && start_node - st < dist.size()); 
    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 < st || b > en) {
                continue; 
            }
            // if(b > a) continue; // avoid exploring too much ya know
            assert(0 <= a - st && a - st < dist.size());
            assert(0 <= b - st && b - st < dist.size());  
            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); 
    // assert(0 <= start_node - st && start_node - st < dist.size()); 
    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 < st || b > en) {
                continue; 
            }
            assert(0 <= a - st && a - st < dist.size());
            assert(0 <= b - st && b - st < dist.size()); 
            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';

        // assert(0 <= start_node - m * k  && start_node - m * k < lef.size()); 
        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++) {

        // assert(0 <= start_node - m * k - k && start_node - m * k - k < rig.size()); 
        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) {

    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(); 
    }
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from toll.cpp:1:
toll.cpp: In function 'void djikstra_left(int64_t, int64_t, int64_t, std::vector<long int>&)':
toll.cpp:38:42: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |             assert(0 <= a - st && a - st < dist.size());
      |                                   ~~~~~~~^~~~~~~~~~~~~
toll.cpp:39:42: warning: comparison of integer expressions of different signedness: 'std::tuple_element<0, std::pair<long int, long int> >::type' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |             assert(0 <= b - st && b - st < dist.size());
      |                                   ~~~~~~~^~~~~~~~~~~~~
toll.cpp: In function 'void djikstra_right(int64_t, int64_t, int64_t, std::vector<long int>&)':
toll.cpp:64:42: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |             assert(0 <= a - st && a - st < dist.size());
      |                                   ~~~~~~~^~~~~~~~~~~~~
toll.cpp:65:42: warning: comparison of integer expressions of different signedness: 'std::tuple_element<0, std::pair<long int, long int> >::type' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |             assert(0 <= b - st && b - st < dist.size());
      |                                   ~~~~~~~^~~~~~~~~~~~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 10
• Subtask 3: 0 / 8
• Subtask 4: 0 / 31
• Subtask 5: 0 / 44