Submission #363316

#	Time	Username	Problem	Language	Result	Execution time	Memory
363316		ngpin04	Toll (BOI17_toll)	C++14	100 / 100	117 ms	35072 KiB

toll

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
const int N = 5e4 + 5;
const int oo = 1e9;

int dis[16][N][5];
int lca[16][N][5];
int n,k,m,q;

void build()
{
    for (int j = 1; j < 16; j++)
    for (int i = 0; i < n; i++)
    {
        for (int cur = 0; cur < k; cur++)
        {
            int p = lca[j - 1][i][cur];
            if (p < 0)
                continue;
            for (int nxt = 0; nxt < k; nxt++)
            {
                int pp = lca[j - 1][p][nxt];
                if (pp < 0)
                    continue;
                lca[j][i][nxt] = pp;
                dis[j][i][nxt] = min(dis[j][i][nxt], dis[j - 1][i][cur] + dis[j - 1][p][nxt]);
            }
        }
    }
}

void jump(vector <pair <int, int>> &f, int step)
{
    for (int i = 0; i < 16; i++) if ((step >> i) & 1)
    {
        vector <pair <int, int>> g(k, mp(oo, oo));
        for (auto pir : f)
        {
            int u = pir.fi;
            int cur = pir.se;
            if (u == oo)
                continue;
            for (int nxt = 0; nxt < k; nxt++)
            {
                int v = lca[i][u][nxt];
                if (v < 0)
                    continue;
                g[nxt] = min(g[nxt], mp(v, cur + dis[i][u][nxt]));
            }
        }
        f = g;
    }
}

int solve(int s, int t)
{
    int step = (t / k) - (s / k);

    if (step < 0)
        return -1;
    vector <pair <int, int>> res(k, mp(oo, oo));

    res[s % k] = mp(s, 0);
    jump(res, step);
    for (auto pir : res)
        if (pir.fi == t)
            return pir.se;
    return -1;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("file.inp","r",stdin);
    cin >> k >> n >> m >> q;

    memset(lca, -1, sizeof(lca));

    for (int j = 0; j < 16; j++)
    for (int i = 0; i < n; i++)
    for (int cur = 0; cur < k; cur++)
        dis[j][i][cur] = oo;

    for (int i = 1; i <= m; i++)
    {
        int u,v,w;
        cin >> u >> v >> w;
        lca[0][u][v % k] = v;
        dis[0][u][v % k] = w;
    }

    build();

    while (q--)
    {
        int u,v;
        cin >> u >> v;
        cout << solve(u, v) << "\n";
    }
    return 0;
}

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