Submission #588739

#	Time	Username	Problem	Language	Result	Execution time	Memory
588739		krit3379	Toll (BOI17_toll)	C++17	100 / 100	96 ms	42736 KiB

toll

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define N 50005

int mod;
long long dp[20][5][N];
vector<long long> v(5);

int t(int i,int j,int st){
    return i/mod*mod+mod*(1<<st)+j;
}

int main(){
    int n,m,q,st,ss,i,j,k,a,b,w,now;
    scanf("%d %d %d %d",&mod,&n,&m,&q);
    for(i=0;i<20;i++)for(j=0;j<5;j++)for(k=0;k<N;k++)dp[i][j][k]=1e15;
    for(i=1;i<=m;i++){
        scanf("%d %d %d",&a,&b,&w);
        dp[0][b%mod][a]=w;
    }
    for(st=1;st<19;st++){
        ss=1<<st;
        for(i=0;i<n;i++){
            if(i+mod*ss>=N)break;
            for(j=0;j<mod;j++){
                for(k=0;k<mod;k++){
                    dp[st][k][i]=min(dp[st][k][i],dp[st-1][j][i]+dp[st-1][k][t(i,j,st-1)]);
                }
            }
        }
    }
    while(q--){
        scanf("%d %d",&a,&b);
        now=a/mod;
        for(i=0;i<mod;i++)v[i]=1e15;
        v[a%mod]=0;
        for(st=19;st>=0;st--){
            if(now*mod+mod*(1<<st)<=b/mod*mod){
                vector<long long> temp(mod,1e15);
                for(i=0;i<mod;i++)for(j=0;j<mod;j++){
                    temp[j]=min(temp[j],dp[st][j][now*mod+i]+v[i]);
                }
                for(i=0;i<mod;i++)v[i]=temp[i];
                now+=1<<st;
            }
        }
        if(v[b%mod]<1e15)printf("%lld\n",v[b%mod]);
        else printf("-1\n");
    }
    return 0;
}

Compilation message (stderr)

toll.cpp: In function 'int main()':
toll.cpp:17:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |     scanf("%d %d %d %d",&mod,&n,&m,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:20:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |         scanf("%d %d %d",&a,&b,&w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~
toll.cpp:35:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |         scanf("%d %d",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~~

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