제출 #1286400

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1286400		iamhereforfun	Toll (BOI17_toll)	C++20	100 / 100	200 ms	288276 KiB

toll

// Starcraft 2 enjoyer //

#include <bits/stdc++.h>

using namespace std;

#define LSOne(X) ((X) & -(X))

const int N = 5e4 + 5;
const int M = 1e6 + 5;
const int LG = 20;
const int C = 26;
const long long INF = 1e18;
const int B = 320;
const int P = 31;
const int MOD = 1e9 + 7;

int k, n, m, q, mask[N], mid[LG][N];
long long val[LG][N][6][6];
vector<pair<int, int>> adj[N];

void build(int l, int r, int lvl)
{
    if (l == r)
    {
        return;
    }
    int m = (l + r) / 2;
    // cout << l << " " << r << " " << lvl << "\n";
    for (int x = 0; x < k; x++)
    {
        val[lvl][m][x][x] = 0;
    }
    for (int x = m - 1; x >= l; x--)
    {
        for (int y = 0; y < k; y++)
        {
            for (int z = 0; z < k; z++)
            {
                for (auto &[i, w] : adj[x * k + y])
                {
                    val[lvl][x][y][z] = min(val[lvl][x][y][z], val[lvl][x + 1][i % k][z] + w);
                }
                // cout << val[lvl][x][y][z] << " " << lvl << " " << x << " " << x * k + y << " " << (x + 1) * k + z << "\n";
            }
        }
    }
    for (int x = 0; x < k; x++)
    {
        val[lvl][m + 1][x][x] = 0;
    }
    for (int x = m + 1; x < r; x++)
    {
        for (int y = 0; y < k; y++)
        {
            for (int z = 0; z < k; z++)
            {
                for (auto &[i, w] : adj[x * k + y])
                {
                    val[lvl][x + 1][i % k][z] = min(val[lvl][x + 1][i % k][z], val[lvl][x][y][z] + w);
                }
            }
        }
    }
    for (int x = m + 1; x <= r; x++)
    {
        mask[x] |= 1 << lvl;
    }
    for (int x = l; x <= r; x++)
    {
        mid[lvl][x] = m;
    }
    build(l, m, lvl + 1);
    build(m + 1, r, lvl + 1);
}

void solve()
{
    cin >> k >> n >> m >> q;
    for (int x = 0; x <= n; x++)
    {
        for (int y = 0; y < LG; y++)
        {
            for (int z = 0; z < k; z++)
            {
                for (int t = 0; t < k; t++)
                {
                    val[y][x][z][t] = INF;
                }
            }
        }
    }
    for (int x = 0; x < m; x++)
    {
        int a, b, w;
        cin >> a >> b >> w;
        adj[a].push_back({b, w});
    }
    build(0, n / k, 0);
    for (int x = 0; x < q; x++)
    {
        int a, b;
        cin >> a >> b;
        if (a / k == b / k)
        {
            if (a == b)
                cout << 0 << "\n";
            else
                cout << -1 << "\n";
            continue;
        }
        int i = __builtin_ctz(mask[a / k] ^ mask[b / k]);
        // cout << i << " ";
        long long ans = INF;
        int m = mid[i][a / k];
        // cout << m << " " << a << " " << b << "\n";
        for (int y = 0; y < k; y++)
        {
            for (auto &[j, w] : adj[m * k + y])
            {
                // cout << m * k + y << " " << j << " " << a / k << " " << a % k << " " << y << " " << b % k << " " << j % k << "\n";
                // cout << val[i][a / k][a % k][y] << " " << val[i][b / k][b % k][j % k] << " " << w << "\n";
                ans = min(ans, val[i][a / k][a % k][y] + val[i][b / k][b % k][j % k] + w);
            }
        }
        if (ans == INF)
            cout << -1 << "\n";
        else
            cout << ans << "\n";
    }
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    for (int x = 1; x <= t; x++)
    {
        solve();
    }
    return 0;
}

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