Submission #378312

#	Time	Username	Problem	Language	Result	Execution time	Memory
378312		couplefire	Toll (BOI17_toll)	C++17	100 / 100	181 ms	14808 KiB

toll

#include <bits/stdc++.h>
using namespace std;
#define MAXN 50005
#define INF 1000000009

int ckmin(int &a, int b){return (b<a)?a=b:a;}
int ckmax(int &a, int b){return (b>a)?a=b:b;}

vector<pair<pair<int, int>, int>> adj[MAXN][5];
int p, n, m, q;
vector<pair<pair<int, int>, int>> queries;
int ans[MAXN];
int mxlvl;

void cdq(int l, int r, vector<pair<pair<int, int>, int>> &bruh){
    if(r < l) return;

    int mid = (l+r)/2;

    int dp[r-l+1][p][p];
    for(int i = l; i<=r; i++){
        for(int a = 0; a<p; a++) for(int b = 0; b<p; b++) dp[i-l][a][b] = INF;
    }
    for(int a = 0; a<p; a++) for(int b = 0; b<p; b++) dp[mid-l][a][b] = (a == b)?0:INF;
    for(int i = mid+1; i<=r; i++){
        for(int a = 0; a<p; a++){
            for(int b = 0; b<p; b++){
                for(auto x : adj[i-1][b]) ckmin(dp[i-l][a][x.first.second], dp[i-1-l][a][b]+x.second);
            }
        }
    }
    for(int i = mid-1; i>=l; i--){
        for(int a = 0; a<p; a++){
            for(int b = 0; b<p; b++){
                for(auto x : adj[i][a]) ckmin(dp[i-l][a][b], dp[i+1-l][x.first.second][b]+x.second);
            }
        }
    }
    vector<pair<pair<int, int>, int>> lqueries, rqueries;
    for(auto x : bruh){
        if(x.first.second/p < mid){
            lqueries.push_back(x);
            continue;
        }
        if(x.first.first/p > mid){
            rqueries.push_back(x);
            continue;
        }

        for(int y = 0; y<p; y++){
            ckmin(ans[x.second], dp[x.first.first/p-l][x.first.first%p][y]+dp[x.first.second/p-l][y][x.first.second%p]);
        }
    }
    cdq(l, mid-1, lqueries);
    cdq(mid+1, r, rqueries);
}

int main(){
    // freopen("a.in", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> p >> n >> m >> q; mxlvl = n/p;
    for(int i = 0; i<m; i++){
        int a, b, w; cin >> a >> b >> w;
        adj[a/p][a%p].push_back({{b/p, b%p}, w});
    }
    for(int i = 0; i<q; i++){
        int a, b; cin >> a >> b;
        queries.push_back({{a, b}, i});
    }
    fill(ans, ans+q, INF);
    cdq(0, mxlvl, queries);
    for(int i = 0; i<q; i++) cout << ((ans[i] == INF)?-1:ans[i]) << endl;
}

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