Submission #628594

#	Time	Username	Problem	Language	Result	Execution time	Memory
628594		kakayoshi	Toll (BOI17_toll)	C++14	100 / 100	116 ms	40488 KiB

toll

#include <bits/stdc++.h>
using namespace std;
#define forw(i,a,b) for(ll i=a;i<=b;i++)
#define forb(i,a,b) for(ll i=a;i>=b;i--)
#define fi first
#define se second
#define pb push_back
#define all(a) a.begin(),a.end()
#define getbit(mask,i) ((mask>>i)&1)
#define getnum(i) (1<<(i))
#define minimize(a,b) ()
typedef long long int ll;
const ll maxN=1e6+5;
const ll mod=1e9+7;
const ll oo=1e18;
ll k,n,m,q,d[maxN][17][6],tmp[6],ans[6];
void solve()
{
    cin>>k>>n>>m>>q;
    // init
    // d[u][i][v] : position u ; go through 2^i blocks ; destination k*(u/k+2^i) + v
    forw(u,0,n-1)
        forw(i,0,16)
            forw(v,0,k-1)
                d[u][i][v]=oo;
    // read
    forw(i,1,m)
    {
        int u,v,val;cin>>u>>v>>val;
        d[u][0][v%k]=val;
    }
    // sparse
    forb(u,n-1,0)
    {
        forw(i,1,16)
        {
            if (u+getnum(i)>=n) break;
            forw(pos,0,k-1)
                forw(v,0,k-1)
                    d[u][i][v]=min(d[u][i][v],d[u][i-1][pos]+d[pos+k*(u/k+getnum(i-1))][i-1][v]);
        }
    }
    // query
    while (q--)
    {
        int l,r; cin>>l>>r;
        int blocks=r/k - l/k; blocks--;
        forw(i,0,k-1) ans[i]=d[l][0][i];
        int cnt=l/k+1;
        forw(i,0,16)
        if (blocks & getnum(i))
        {
            forw(u,0,k-1) tmp[u]=oo;

            forw(u,0,k-1)
                forw(v,0,k-1)
                    tmp[v]=min(tmp[v],ans[u]+d[u+cnt*k][i][v]);
            forw(u,0,k-1) ans[u]=tmp[u];
            cnt+=getnum(i);
        }
        if (ans[r%k]==oo) cout<<-1<<"\n";
        else cout<<ans[r%k]<<"\n";
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    //freopen("bruh.inp","r",stdin);
    //freopen("bruh.out","w",stdout);
    solve();
    return 0;
}

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