oj.uz

답안 #683482

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
683482 2023-01-18T14:35:36 Z finn__ Toll (BOI17_toll) C++17
0 / 100
 124 ms 30592 KB 
#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; 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 / 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 (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
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 61 ms 29896 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 124 ms 30592 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 61 ms 29896 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -