Submission #1235124

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235124		chikien2009	Toll (BOI17_toll)	C++20	100 / 100	49 ms	16048 KiB

toll

#include <bits/stdc++.h>

using namespace std;

void setup()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int k, n, m, o, val[16][50000][5], a, b, t, cur[5], nxt[5];

int main()
{
    setup();

    cin >> k >> n >> m >> o;
    for (int i = 0; i < 5e4; ++i)
    {
        for (int j = 0; j < 16; ++j)
        {
            fill_n(val[j][i], 5, 2e9);
        }
    }
    while (m--)
    {
        cin >> a >> b >> t;
        val[0][a][b % k] = t;
    }
    for (int i = 1; i < 16; ++i)
    {
        for (int j = 0; j / k + (1 << i) <= n / k; ++j)
        {
            a = (j / k + (1 << (i - 1))) * k;
            for (int g = 0; g < k; ++g)
            {
                for (int h = 0; h < k; ++h)
                {
                    if (val[i - 1][j][g] != 2e9 && val[i - 1][a + g][h] != 2e9)
                    {
                        val[i][j][h] = min({val[i][j][h], val[i - 1][j][g] + val[i - 1][a + g][h]});
                    }
                }
            }
        }
    }
    while (o--)
    {
        cin >> a >> b;
        fill_n(cur, 5, 2e9);
        cur[a % k] = 0;
        a /= k;
        for (int i = 15; i >= 0; --i)
        {
            if (a + (1 << i) <= b / k)
            {
                fill_n(nxt, 5, 2e9);
                for (int j = 0; j < k; ++j)
                {
                    for (int g = 0; g < k; ++g)
                    {
                        if (cur[j] != 2e9 && val[i][a * k + j][g] != 2e9)
                        {
                            nxt[g] = min({nxt[g], cur[j] + val[i][a * k + j][g]});
                        }
                    }
                }
                for (int j = 0; j < 5; ++j)
                {
                    cur[j] = nxt[j];
                }
                a += (1 << i);
            }
        }
        cout << (cur[b % k] == 2e9 ? -1 : cur[b % k]) << "\n";
    }
    return 0;
}

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