oj.uz

Submission #828265

# Submission time Handle Problem Language Result Execution time Memory
828265 2023-08-17T07:29:29 Z Darren0724 Toll (BOI17_toll) C++17
7 / 100
 401 ms 310772 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N=50005;
const int INF=1e9;
const int K=__lg(N)+1;
vector jump(N, vector (K,vector(5,vector(5,INF))));
void f(vector<vector<int>> &a,vector<vector<int>> &b,vector<vector<int>> &c,int k){
    //i -> p -> j
    for(int i=0;i<k;i++){
        for(int p=0;p<k;p++){
            for(int j=0;j<k;j++){
                c[i][j]=min(c[i][j],a[i][p]+b[p][j]);
            }
        }
    }
}
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int k,n,m,q;cin>>k>>n>>m>>q;
    for(int i=0;i<m;i++){
        int a,b,c;cin>>a>>b>>c;
        int t=a/k;
        jump[t][0][a%k][b%k]=c;
    }
    for(int j=1;j<K;j++){
        for(int i=0;i+(1<<j-1)<N;i++){
            f(jump[i][j-1],jump[i+(1<<j-1)][j-1],jump[i][j],k);
        }
    }
    for(int i=0;i<q;i++){
        vector ans(5,vector(5,0ll));
        int a,b;cin>>a>>b;
        int t=(b/k)-(a/k);
        if(t==0){
            cout<<-1<<endl;
            continue;
        }
        int now=a/k;
        for(int j=0;j<K;j++){
            if(t&(1<<j)){
                vector<vector<int>> y(5);
                for(int j1=0;j1<5;j1++){
                    y[j1]=ans[j1];
                    ans[j1].assign(5,INF);
                }
                f(y,jump[now][j],ans,k);
                now+=(1<<j);
            }
        }
        int ans1=ans[a%k][b%k];
        cout<<(ans1>=INF?-1:ans1)<<endl;
    }
    return 0;
}

Compilation message

toll.cpp: In function 'int32_t main()':
toll.cpp:29:28: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   29 |         for(int i=0;i+(1<<j-1)<N;i++){
      |                           ~^~
toll.cpp:30:40: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   30 |             f(jump[i][j-1],jump[i+(1<<j-1)][j-1],jump[i][j],k);
      |                                       ~^~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 401 ms 310124 KB Output is correct
2 Correct 303 ms 309096 KB Output is correct
3 Correct 286 ms 309064 KB Output is correct
4 Correct 297 ms 309236 KB Output is correct
5 Correct 284 ms 309176 KB Output is correct
6 Correct 329 ms 309176 KB Output is correct
7 Correct 284 ms 309096 KB Output is correct
8 Correct 354 ms 310028 KB Output is correct
9 Correct 381 ms 310036 KB Output is correct
10 Correct 358 ms 309184 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 401 ms 310772 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 290 ms 309048 KB Output is correct
2 Incorrect 337 ms 309144 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 290 ms 309048 KB Output is correct
2 Incorrect 337 ms 309144 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 401 ms 310124 KB Output is correct
2 Correct 303 ms 309096 KB Output is correct
3 Correct 286 ms 309064 KB Output is correct
4 Correct 297 ms 309236 KB Output is correct
5 Correct 284 ms 309176 KB Output is correct
6 Correct 329 ms 309176 KB Output is correct
7 Correct 284 ms 309096 KB Output is correct
8 Correct 354 ms 310028 KB Output is correct
9 Correct 381 ms 310036 KB Output is correct
10 Correct 358 ms 309184 KB Output is correct
11 Incorrect 401 ms 310772 KB Output isn't correct
12 Halted 0 ms 0 KB -