oj.uz

Submission #378308

# Submission time Handle Problem Language Result Execution time Memory
378308 2021-03-16T12:50:10 Z couplefire Toll (BOI17_toll) C++17
0 / 100
 3000 ms 15836 KB 
#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[mxlvl+1][p][p];
    for(int i = 0; i<=mxlvl; i++){
        for(int a = 0; a<p; a++) for(int b = 0; b<p; b++) dp[i][a][b] = INF;
    }
    for(int a = 0; a<p; a++) for(int b = 0; b<p; b++) dp[mid][a][b] = (a == b)?0:INF;
    for(int i = mid+1; i<=mxlvl; 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][a][x.first.second], dp[i-1][a][b]+x.second);
            }
        }
    }
    for(int i = mid-1; i>=0; i--){
        for(int a = 0; a<=p; a++){
            for(int b = 0; b<p; b++){
                for(auto x : adj[i][a]) ckmin(dp[i][a][b], dp[i+1][x.first.second][b]+x.second);
            }
        }
    }
    vector<pair<pair<int, int>, int>> lqueries, rqueries;
    for(auto x : queries){
        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][x.first.first%p][y]+dp[x.first.second/p][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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3066 ms 14504 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3075 ms 15836 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6252 KB Output is correct
2 Correct 4 ms 6252 KB Output is correct
3 Correct 4 ms 6268 KB Output is correct
4 Correct 4 ms 6252 KB Output is correct
5 Correct 4 ms 6252 KB Output is correct
6 Correct 16 ms 6380 KB Output is correct
7 Correct 17 ms 6380 KB Output is correct
8 Incorrect 33 ms 6636 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6252 KB Output is correct
2 Correct 4 ms 6252 KB Output is correct
3 Correct 4 ms 6268 KB Output is correct
4 Correct 4 ms 6252 KB Output is correct
5 Correct 4 ms 6252 KB Output is correct
6 Correct 16 ms 6380 KB Output is correct
7 Correct 17 ms 6380 KB Output is correct
8 Incorrect 33 ms 6636 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3066 ms 14504 KB Time limit exceeded
2 Halted 0 ms 0 KB -