Submission #1101883

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101883		simona1230	Toll (BOI17_toll)	C++17	0 / 100	148 ms	524288 KiB

toll

// Online C++ compiler to run C++ program online
#include <bits/stdc++.h>
using namespace std;

int k,n,m,o;
vector<pair<int,int> > v[50001];
long long d[50001][32][8][8];

void read()
{
    cin>>k>>n>>m>>o;
    
    for(int b=0;b<=(n-1)/k;b++)
        for(int i1=0;i1<k;i1++)
            for(int i2=0;i2<k;i2++)
                d[b][0][i1][i2]=1e9;
                
    for(int i=1;i<=m;i++)
    {
        int a,b;
        long long t;
        cin>>a>>b>>t;
        v[a].push_back({b,t});
        int b1=a/k;
        int i1=a%k;
        int i2=b%k;
        d[b1][0][i1][i2]=min(d[b1][0][i1][i2],t);
    }
}

void prec()
{
    for(int lg=1;lg<16;lg++)
        for(int i1=0;i1<k;i1++)
            for(int i2=0;i2<k;i2++)
                for(int b=0;b<=(n-1)/k;b++)
                    {
                        d[b][lg][i1][i2]=1e9;
                        for(int i3=0;i3<k;i3++)
                             d[b][lg][i1][i2]=min(d[b][lg-1][i1][i3]
                                +d[b+(1<<(lg-1))][lg-1][i3][i2],
                                    d[b][lg][i1][i2]);
                    }
}


long long ans[8],ans2[8];
void compute(int a,int b)
{
    for(int i=0;i<k;i++)
        ans[i]=1e9;
    ans[a%k]=0;
    
    int jump=b/k-a/k;
    int block=a/k;
    for(int lg=0;lg<16;lg++)
    {
        if((1<<lg)&jump)
        {
            for(int i=0;i<k;i++)
                ans2[i]=ans[i];
            for(int i2=0;i2<k;i2++)
            {
                ans[i2]=1e9;
                for(int i1=0;i1<k;i1++)
                    ans[i2]=min(ans[i2],ans2[i1]+d[block][lg][i1][i2]);
            }
            block+=(1<<lg);
        }
    }
    
    int i=b%k;
    if(ans[i]>=1e9)cout<<-1<<endl;
    else cout<<ans[i]<<endl;
}

void solve()
{
    for(int i=1;i<=o;i++)
    {
        int a,b;
        cin>>a>>b;
        compute(a,b);
    }
}

int main() {
    read();
    prec();
    solve();
    return 0;
}

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