oj.uz

Submission #1092007

# Submission time Handle Problem Language Result Execution time Memory
1092007 2024-09-22T20:21:34 Z raphaelp Toll (BOI17_toll) C++14
7 / 100
 108 ms 12628 KB 
#include <bits/stdc++.h>
using namespace std;
long long l(long long x) { return (x << 1); }
long long r(long long x) { return (x << 1) + 1; }
void setup(long long L, long long R, vector<vector<vector<long long>>> &dp, long long x, long long K)
{
    if (L == R)
        return;
    long long m = (L + R) / 2;
    setup(L, m, dp, l(x), K);
    setup(m + 1, R, dp, r(x), K);
    for (long long i = 0; i < K; i++)
    {
        for (long long j = 0; j < K; j++)
        {
            for (long long k = 0; k < K; k++)
            {
                dp[x][i][j] = min(dp[x][i][j], dp[l(x)][i][k] + dp[r(x)][k][j]);
            }
        }
    }
}
vector<vector<long long>> query(long long L, long long R, long long a, long long b, long long x, long long K, vector<vector<vector<long long>>> &dp)
{
    vector<vector<long long>> ans;
    if (L > b || R < a)
        return ans;
    ans.assign(K, vector<long long>(K, 1000000000000));
    if (L >= a && R <= b)
        return dp[x];
    long long m = (L + R) / 2;
    vector<vector<long long>> lef = query(L, m, a, b, l(x), K, dp);
    vector<vector<long long>> right = query(m + 1, R, a, b, r(x), K, dp);
    if (lef.size() == 0)
        ans = right;
    else if (right.size() == 0)
        ans = lef;
    else
        for (long long i = 0; i < K; i++)
        {
            for (long long j = 0; j < K; j++)
            {
                for (long long k = 0; k < K; k++)
                {
                    ans[i][j] = min(ans[i][j], lef[i][k] + right[k][j]);
                }
            }
        }
    return ans;
}
int main()
{
    long long N, M, K, O;
    cin >> K >> N >> M >> O;
    long long N2 = (1 << (long long)ceil(log2(ceil((double)N / K))));
    vector<vector<vector<long long>>> dp(2 * N2, vector<vector<long long>>(K, vector<long long>(K, 1000000000000)));
    for (long long i = 0; i < M; i++)
    {
        long long a, b, t;
        cin >> a >> b >> t;
        dp[N2 + a / K][a % K][b % K] = t;
    }
    setup(0, N2 - 1, dp, 1, K);
    for (long long i = 0; i < O; i++)
    {
        long long a, b;
        cin >> a >> b;
        vector<vector<long long>> temp = query(0, N2 - 1, a / K, b / K - 1, 1, K, dp);
        cout << ((temp[a % K][b % K] == 1000000000000) ? -1 : temp[a % K][b % K]) << '\n';
    }
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 12628 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 432 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 4 ms 604 KB Output is correct
6 Correct 4 ms 604 KB Output is correct
7 Correct 4 ms 604 KB Output is correct
8 Correct 87 ms 12480 KB Output is correct
9 Correct 108 ms 12604 KB Output is correct
10 Correct 57 ms 11868 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 11820 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Runtime error 0 ms 348 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 12628 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 432 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 4 ms 604 KB Output is correct
6 Correct 4 ms 604 KB Output is correct
7 Correct 4 ms 604 KB Output is correct
8 Correct 87 ms 12480 KB Output is correct
9 Correct 108 ms 12604 KB Output is correct
10 Correct 57 ms 11868 KB Output is correct
11 Correct 100 ms 11820 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Runtime error 0 ms 348 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -