Submission #957636

#	Time	Username	Problem	Language	Result	Execution time	Memory
957636		12345678	Toll (BOI17_toll)	C++17	7 / 100	46 ms	31824 KiB

toll

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=5e4+5, kx=16;

ll dp[nx][kx][5], sz, n, m, q, a, b, t;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>sz>>n>>m>>q;
    for (int i=0; i<nx; i++) for (int j=0; j<kx; j++) for (int k=0; k<sz; k++) dp[i][j][k]=1e18;
    for (int i=0; i<m; i++) cin>>a>>b>>t, dp[a][0][b%sz]=t;
    for (int i=1; i<kx; i++) for (int j=0; j<n; j++) for (int k=0; k<sz; k++) for (int l=0; l<sz; l++) dp[j][i][k]=min(dp[j][i][k], dp[j][i-1][l]+dp[min(l+((j/sz)+(1<<(i-1)))*sz, (ll)nx-1)][i-1][k]);
    //for (int i=0; i<n; i++) for (int j=0; j<3; j++) for (int k=0; k<sz; k++) cout<<i<<' '<<j<<' '<<k<<' '<<dp[i][j][k]<<'\n';
    while (q--)
    {
        cin>>a>>b;
        int c=a/sz, tg=b/sz;
        vector<pair<ll, ll>> v;
        v.push_back({0, a});
        if (c==t) 
        {
            cout<<-1<<'\n';
            continue;
        }
        for (int i=kx-1; i>=0; i--)
        {
            if (c+(1<<i)>tg) continue;
            if (v.empty())
            {
                cout<<-1<<'\n';
                break;
            }
            if (c+(1<<i)==tg)
            {
                ll res=1e18;
                for (auto x:v) res=min(res, x.first+dp[x.second][i][b%sz]);
                if (res==1e18) cout<<-1<<'\n';
                else cout<<res<<'\n';
                break;
            }
            vector<ll> tmp(sz, 1e18);
            for (int j=0; j<sz; j++) for (auto x:v) tmp[j]=min(tmp[j], x.first+dp[x.second][i][j]);
            v.clear();
            for (int j=0; j<sz; j++) if (tmp[j]!=1e18) v.push_back({tmp[j], (c+(1<<i))*sz+j});
            c+=(1<<i);
        }
    }
}

/*
5 14 5 0
0 5 9
5 12 10
0 7 7
7 12 8
4 7 10
0 12


*/

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