oj.uz

Submission #783748

# Submission time Handle Problem Language Result Execution time Memory
783748 2023-07-15T09:45:04 Z 1075508020060209tc Toll (BOI17_toll) C++14
39 / 100
 3000 ms 364204 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;
        continue;
    }
    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++){
      |                     ~^~~~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3085 ms 339880 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 3068 ms 359940 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12244 KB Output is correct
2 Correct 6 ms 12244 KB Output is correct
3 Correct 6 ms 12200 KB Output is correct
4 Correct 6 ms 12244 KB Output is correct
5 Correct 6 ms 12244 KB Output is correct
6 Correct 11 ms 18680 KB Output is correct
7 Correct 13 ms 19156 KB Output is correct
8 Correct 15 ms 19316 KB Output is correct
9 Correct 12 ms 19252 KB Output is correct
10 Correct 153 ms 340552 KB Output is correct
11 Correct 193 ms 361344 KB Output is correct
12 Correct 263 ms 363432 KB Output is correct
13 Correct 226 ms 364124 KB Output is correct
14 Correct 212 ms 362272 KB Output is correct
15 Correct 160 ms 222420 KB Output is correct
16 Correct 149 ms 222412 KB Output is correct

Subtask #4
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12244 KB Output is correct
2 Correct 6 ms 12244 KB Output is correct
3 Correct 6 ms 12200 KB Output is correct
4 Correct 6 ms 12244 KB Output is correct
5 Correct 6 ms 12244 KB Output is correct
6 Correct 11 ms 18680 KB Output is correct
7 Correct 13 ms 19156 KB Output is correct
8 Correct 15 ms 19316 KB Output is correct
9 Correct 12 ms 19252 KB Output is correct
10 Correct 153 ms 340552 KB Output is correct
11 Correct 193 ms 361344 KB Output is correct
12 Correct 263 ms 363432 KB Output is correct
13 Correct 226 ms 364124 KB Output is correct
14 Correct 212 ms 362272 KB Output is correct
15 Correct 160 ms 222420 KB Output is correct
16 Correct 149 ms 222412 KB Output is correct
17 Correct 1613 ms 361576 KB Output is correct
18 Correct 6 ms 12244 KB Output is correct
19 Correct 8 ms 12192 KB Output is correct
20 Correct 7 ms 12164 KB Output is correct
21 Correct 7 ms 12264 KB Output is correct
22 Correct 6 ms 12244 KB Output is correct
23 Correct 29 ms 18736 KB Output is correct
24 Correct 35 ms 19216 KB Output is correct
25 Correct 53 ms 19284 KB Output is correct
26 Correct 45 ms 19284 KB Output is correct
27 Correct 1217 ms 340768 KB Output is correct
28 Correct 1956 ms 363672 KB Output is correct
29 Correct 2133 ms 364204 KB Output is correct
30 Correct 1959 ms 362428 KB Output is correct

Subtask #5
0 / 44.0

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