oj.uz

Submission #549657

# Submission time Handle Problem Language Result Execution time Memory
549657 2022-04-16T08:34:12 Z Jarif_Rahman Toll (BOI17_toll) C++17
8 / 100
 3000 ms 5964 KB 
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

const ll inf = 1e17;
int k;

struct node{
    vector<vector<ll>> A, B;
    node(){
        A.assign(k, vector<ll>(k, 0));
        B = vector<vector<ll>>(k, vector<ll>(k, inf));
        for(int i = 0; i < k; i++) B[i][i] = 0;
    }
    node(vector<vector<ll>> _A){
        A = _A;
        B.assign(k, vector<ll>(k, inf));
        for(int i = 0; i < k; i++) B[i][i] = 0;
    }
};
node operator+(node a, node b){
    node rt;
    rt.A = a.A, rt.B = vector<vector<ll>>(k, vector<ll>(k, inf));

    for(int i = 0; i < k; i++) for(int j = 0; j < k; j++)
        for(int l = 0; l < k; l++) for(int m = 0; m < k; m++)
            rt.B[i][j] = min(rt.B[i][j], a.B[i][l]+b.B[m][j]+b.A[l][m]);
    return rt;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, m, o; cin >> k >> n >> m >> o;

    vector<vector<vector<ll>>> div((n+k-1)/k, vector<vector<ll>>(k, vector<ll>(k, inf)));

    for(int i = 0; i < m; i++){
        int a, b; ll w; cin >> a >> b >> w;
        div[b/k][a%k][b%k] = w;
    }

    while(o--){
        int a, b; cin >> a >> b;
        auto nd = node(div[a/k]);
        for(int i = a/k+1; i <= b/k; i++) nd = nd+node(div[i]);

        ll ans = nd.B[a%k][b%k];
        if(ans >= inf) ans = -1;
        cout << ans << "\n";
    }

}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3067 ms 5532 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 3065 ms 5552 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 20 ms 404 KB Output is correct
7 Correct 14 ms 420 KB Output is correct
8 Correct 18 ms 340 KB Output is correct
9 Correct 15 ms 340 KB Output is correct
10 Correct 1050 ms 5384 KB Output is correct
11 Correct 742 ms 5440 KB Output is correct
12 Correct 682 ms 5744 KB Output is correct
13 Correct 701 ms 5964 KB Output is correct
14 Correct 749 ms 5324 KB Output is correct
15 Correct 537 ms 3796 KB Output is correct
16 Correct 434 ms 3788 KB Output is correct

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 20 ms 404 KB Output is correct
7 Correct 14 ms 420 KB Output is correct
8 Correct 18 ms 340 KB Output is correct
9 Correct 15 ms 340 KB Output is correct
10 Correct 1050 ms 5384 KB Output is correct
11 Correct 742 ms 5440 KB Output is correct
12 Correct 682 ms 5744 KB Output is correct
13 Correct 701 ms 5964 KB Output is correct
14 Correct 749 ms 5324 KB Output is correct
15 Correct 537 ms 3796 KB Output is correct
16 Correct 434 ms 3788 KB Output is correct
17 Execution timed out 3080 ms 5692 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

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