oj.uz

Submission #783743

# Submission time Handle Problem Language Result Execution time Memory
783743 2023-07-15T09:36:44 Z 1075508020060209tc Toll (BOI17_toll) C++14
0 / 100
 3000 ms 359936 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3073 ms 339844 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3087 ms 359936 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12244 KB Output is correct
2 Incorrect 7 ms 12244 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12244 KB Output is correct
2 Incorrect 7 ms 12244 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3073 ms 339844 KB Time limit exceeded
2 Halted 0 ms 0 KB -