oj.uz

Submission #683485

# Submission time Handle Problem Language Result Execution time Memory
683485 2023-01-18T14:44:32 Z finn__ Toll (BOI17_toll) C++17
7 / 100
 140 ms 58444 KB 
#include <bits/stdc++.h>
using namespace std;

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

    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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 58444 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 2 ms 980 KB Output is correct
6 Correct 2 ms 980 KB Output is correct
7 Correct 2 ms 980 KB Output is correct
8 Correct 127 ms 58352 KB Output is correct
9 Correct 123 ms 58352 KB Output is correct
10 Correct 101 ms 56832 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 132 ms 47676 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 0 ms 212 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 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 58444 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 2 ms 980 KB Output is correct
6 Correct 2 ms 980 KB Output is correct
7 Correct 2 ms 980 KB Output is correct
8 Correct 127 ms 58352 KB Output is correct
9 Correct 123 ms 58352 KB Output is correct
10 Correct 101 ms 56832 KB Output is correct
11 Incorrect 132 ms 47676 KB Output isn't correct
12 Halted 0 ms 0 KB -