Submission #683484

#	Time	Username	Problem	Language	Result	Execution time	Memory
683484		finn__	Toll (BOI17_toll)	C++17	7 / 100	210 ms	58584 KiB

toll

#include <bits/stdc++.h>
using namespace std;

int main()
{
    size_t n, m, o, k;
    cin >> k >> n >> m >> o;

    vector<vector<pair<unsigned, unsigned>>> g(n);
    for (size_t i = 0; i < m; i++)
    {
        unsigned u, v, t;
        cin >> u >> v >> t;
        g[u].emplace_back(v, t);
    }

    vector<vector<vector<unsigned>>> dp(n, vector<vector<unsigned>>(1, vector<unsigned>(k, UINT_MAX)));
    for (size_t u = 0; u < n; u++)
        for (auto const &[v, w] : g[u])
            dp[u][0][v % k] = w;

    for (size_t j = 1; j < n / k; j <<= 1)
        for (size_t u = 0; u < n; u++)
        {
            if ((u / k + j + 1) * k >= n)
                continue;
            dp[u].emplace_back(k, UINT_MAX);
            for (size_t h = 0; h < k; h++)
                for (size_t i = 0; i < k; i++)
                {
                    if (dp[u][dp[u].size() - 2][i] != UINT_MAX &&
                        dp[u].size() - 2 < dp[(u / k + j) * k + i].size() &&
                        dp[(u / k + j) * k + i][dp[u].size() - 2][h] != UINT_MAX)
                        dp[u].back()[h] =
                            min(dp[u].back()[h],
                                dp[u][dp[u].size() - 2][i] + dp[(u / k + j) * k + i][dp[u].size() - 2][h]);
                }
        }

    for (size_t i = 0; i < o; i++)
    {
        unsigned u, v;
        cin >> u >> v;

        if (u / k >= v / k)
        {
            cout << -1 << '\n';
            continue;
        }

        size_t z = 0, h = v / k - u / k;
        vector<unsigned> d(k, UINT_MAX);
        d[u % k] = 0;
        while (h)
        {
            if (h & 1)
            {
                vector<unsigned> e(k, UINT_MAX);
                for (size_t j = 0; j < k; j++)
                    if (d[j] != UINT_MAX)
                        for (size_t l = 0; l < k; l++)
                            if (z < dp[(u / k) * k + j].size() &&
                                dp[(u / k) * k + j][z][l] != UINT_MAX)
                                e[l] = min(e[l], d[j] + dp[(u / k) * k + j][z][l]);
                u += 1 << z;
                swap(d, e);
            }
            z++;
            h >>= 1;
        }

        if (d[v % k] == UINT_MAX)
            cout << -1 << '\n';
        else
            cout << d[v % k] << '\n';
    }
}

• Subtask 1: 7 / 7
• Subtask 2: 0 / 10
• Subtask 3: 0 / 8
• Subtask 4: 0 / 31
• Subtask 5: 0 / 44