Submission #1092009

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092009		raphaelp	Toll (BOI17_toll)	C++14	100 / 100	191 ms	15704 KiB

toll

#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;
        if (a / K == b / K)
        {
            cout << -1 << '\n';
            continue;
        }
        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 / 7
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 31 / 31
• Subtask 5: 44 / 44