oj.uz

Submission #933419

# Submission time Handle Problem Language Result Execution time Memory
933419 2024-02-25T16:01:25 Z LucaIlie Toll (BOI17_toll) C++17
8 / 100
 3000 ms 7132 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAX_K = 5;
const int MAX_N = 5e4;
const int INF = 1e9;
int k;

struct matrix {
    int n;
    vector<vector<int>> mat;

    void init( int _n ) {
        n = _n;
        mat.resize( n );
        for ( int i = 0; i < n; i++ ) {
            mat[i].resize( n );
            for ( int j = 0; j < n; j++ )
                mat[i][j] = INF;
        }
    }

    matrix operator + ( matrix b ) {
        matrix a = *this;
        matrix c;
        c.init( n );

        for ( int i = 0; i < n; i++ ) {
            for ( int j = 0; j < n; j++ ) {
                for ( int k = 0; k < n; k++ )
                    c.mat[i][j] = min( c.mat[i][j], a.mat[i][k] + b.mat[k][j] );
            }
        }

        return c;
    }
};


matrix buckets[MAX_N];

matrix query( int l, int r ) {
    matrix ans = buckets[l];
    for ( int i = l + 1; i <= r; i++ )
        ans = ans + buckets[i];
    return ans;
}

int main() {
    int k, n, m, o;

    cin >> k >> n >> m >> o;


    int b = 0;
    for ( int i = 0; i < n; i += k ) {
        buckets[i / k].init( k );
        b++;
    }
    for ( int i = 0; i < m; i++ ) {
        int a, b, c;
        cin >> a >> b >> c;
        buckets[a / k].mat[a % k][b % k] = c;
    }

    while ( o-- ) {
        int l, r;

        cin >> l >> r;
        int ans = query( l / k, r / k - 1 ).mat[l % k][r % k];
        if ( ans == INF || l / k >= r / k )
            cout << "-1\n";
        else
            cout << ans << "\n";
    }

    return 0;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3062 ms 6024 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 3039 ms 6704 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 1884 KB Output is correct
2 Correct 1 ms 1884 KB Output is correct
3 Correct 1 ms 1884 KB Output is correct
4 Correct 1 ms 1880 KB Output is correct
5 Correct 1 ms 1880 KB Output is correct
6 Correct 5 ms 1884 KB Output is correct
7 Correct 5 ms 1884 KB Output is correct
8 Correct 6 ms 2136 KB Output is correct
9 Correct 5 ms 1884 KB Output is correct
10 Correct 222 ms 5724 KB Output is correct
11 Correct 197 ms 6636 KB Output is correct
12 Correct 209 ms 7056 KB Output is correct
13 Correct 227 ms 7132 KB Output is correct
14 Correct 208 ms 6748 KB Output is correct
15 Correct 143 ms 4688 KB Output is correct
16 Correct 126 ms 4692 KB Output is correct

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1884 KB Output is correct
2 Correct 1 ms 1884 KB Output is correct
3 Correct 1 ms 1884 KB Output is correct
4 Correct 1 ms 1880 KB Output is correct
5 Correct 1 ms 1880 KB Output is correct
6 Correct 5 ms 1884 KB Output is correct
7 Correct 5 ms 1884 KB Output is correct
8 Correct 6 ms 2136 KB Output is correct
9 Correct 5 ms 1884 KB Output is correct
10 Correct 222 ms 5724 KB Output is correct
11 Correct 197 ms 6636 KB Output is correct
12 Correct 209 ms 7056 KB Output is correct
13 Correct 227 ms 7132 KB Output is correct
14 Correct 208 ms 6748 KB Output is correct
15 Correct 143 ms 4688 KB Output is correct
16 Correct 126 ms 4692 KB Output is correct
17 Execution timed out 3037 ms 6936 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 3062 ms 6024 KB Time limit exceeded
2 Halted 0 ms 0 KB -