Submission #783743

#	Time	Username	Problem	Language	Result	Execution time	Memory
783743		1075508020060209tc	Toll (BOI17_toll)	C++14	0 / 100	3087 ms	359936 KiB

toll

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define X first
#define Y second
int K;int n;int m;int O;
vector<pair<int,int>>e[500005];
int jmp[18][60004][7][7];
int nwgr[10][10];
int tmpgr[10][10];
int agr[10][10];
int bgr[10][10];
int stp;
void mrg(int pl){
for(int i=0;i<=K-1;i++){
    for(int j=0;j<=K-1;j++){
        tmpgr[i][j]=1e18;
    }
}
for(int a=stp;a<=stp;a++){
    for(int aa=0;aa<=K-1;aa++){
        int apl=aa+K*(pl);
        for(int i=0;i<e[apl].size();i++){
            int v=e[apl][i].first;
            v%=K;
            int w=e[apl][i].second;
            for(int b=0;b<=K-1;b++){
                tmpgr[a][b]=min(tmpgr[a][b],agr[a][aa]+w+bgr[v][b]);
            }
        }
    }
}
}


signed main(){
cin.tie(0);
ios_base::sync_with_stdio(0);
cin>>K>>n>>m>>O;

for(int i=1;i<=m;i++){
    int a;int b;int t;
    cin>>a>>b>>t;
    e[a].push_back({b,t});
}
for(int lg=0;lg<=17;lg++){
    for(int a=0;a<=K-1;a++){
        for(int b=0;b<=K-1;b++){
            for(int i=0;i<=n;i++){
                if(a==b&&lg==0){continue;}
                jmp[lg][i][a][b]=1e18;
            }
        }
    }
}
for(int lg=1;lg<=17;lg++){
    for(int i=0;i+(1<<lg)-1<=n/K+1;i++){
        for(int a=0;a<=K-1;a++){
            for(int aa=0;aa<=K-1;aa++){
                int apl=K*(i+(1<<(lg-1))-1)+aa;
                for(int j=0;j<e[apl].size();j++){
                    int v=e[apl][j].first;
                    v%=K;
                    int w=e[apl][j].second;
                    for(int b=0;b<=K-1;b++){
                        jmp[lg][i][a][b]=min(jmp[lg][i][a][b],jmp[lg-1][i][a][aa]+w+jmp[lg-1][i+(1<<(lg-1))][v][b]);
                    }
                }

            }
        }
    }
}


while(O--){
    int a;int b;
    cin>>a>>b;
    if( (a/K)>=(b/K)){
        cout<<-1<<endl;
    }
    stp=a%K;
    for(int i=0;i<=K-1;i++){
        for(int j=0;j<=K-1;j++){
            if(i==j&&((a%K)==i)){
                nwgr[i][j]=0;
                continue;
            }
            nwgr[i][j]=1e18;
        }
    }
    int nwpl=a/K;
    for(int lg=0;lg>=0;lg--){

        while((nwpl+1<=(b/K))){
        //    cout<<lg<<endl;
            for(int i=0;i<=K-1;i++){
                for(int j=0;j<=K-1;j++){
                    agr[i][j]=nwgr[i][j];
                }
            }
            for(int i=0;i<=K-1;i++){
                for(int j=0;j<=K-1;j++){
                    bgr[i][j]=jmp[lg][nwpl+1][i][j];
                }
            }
            mrg(nwpl);
            nwpl+=(1<<lg);
            for(int i=0;i<=K-1;i++){
                for(int j=0;j<=K-1;j++){
                    nwgr[i][j]=tmpgr[i][j];
                }
            }
        }
    }
    int ans=nwgr[a%K][b%K];
    if(ans>=1e18){
        ans=-1;
    }
    cout<<ans<<endl;

}
return 0;
int lg;int i;int a;int b;
while(cin>>lg>>i>>a>>b){
    cout<<jmp[lg][i][a][b]<<endl;
}




}

Compilation message (stderr)

toll.cpp: In function 'void mrg(long long int)':
toll.cpp:23:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |         for(int i=0;i<e[apl].size();i++){
      |                     ~^~~~~~~~~~~~~~
toll.cpp: In function 'int main()':
toll.cpp:61:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |                 for(int j=0;j<e[apl].size();j++){
      |                             ~^~~~~~~~~~~~~~

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