oj.uz

Submission #1107135

# Submission time Handle Problem Language Result Execution time Memory
1107135 2024-10-31T17:37:10 Z hihihihaw Toll (BOI17_toll) C++17
0 / 100
 90 ms 176712 KB 
#pragma GCC optimize("O3,unroll-loops")    
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define pb push_back
#define pii pair<int,int>
#define sz(v) (int)v.size()
#define fi first
#define se second
#define INF 1223372036854775807
#define MOD  998244353
#define cint(x) int x;cin>>x;
#define cinarr(a,n) int a[n];for (int i=0;i<n;i++) cin>>a[i];
#define coutarr(a) for (auto d:a)cout<<d<<" "; cout<<endl;
#define coutarrD(a) for (auto d:a) cout<<d.fi<<","<<d.se<<" "; cout<<endl;
#define BERKAY_TUP ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define endl '\n'
#define ld long double
#define mid (start+end)/2
#define vvi vector<vector<int>>
int t=1;
int interactive=0;
int usaco=0;
int testCase=0;
int bj[50023][5][5][18];
void solve(){
    int k,n,m,q;
    cin>>k>>n>>m>>q;
    for (int i=0;i<50023;i++){
        for (int j=0;j<18;j++){
            for (int k1=0;k1<5;k1++){
                for (int k2=0;k2<5;k2++){
                    bj[i][k1][k2][j]=99999999999;
                }
            }
        }
    }
    while (m--){
        int x,y,c;
        cin>>x>>y>>c;
        int g1=x/k,g2=g1+1;
        bj[g1][x%k][y%k][0]=c;
    }
    for (int j=1;j<18;j++){
        for (int i=0;i<n/k;i++){
            if (i+(1<<j)>n/k) continue;
            for (int k1=0;k1<k;k1++){
                for (int k2=0;k2<k;k2++){
                    for (int z=0;z<k;z++){
                        bj[i][k1][k2][j]=min(bj[i][k1][k2][j],bj[i][k1][z][j-1]+bj[i+(1<<(j-1))][z][k2][j-1]);
                    }
                }
            }
        }
    }
    while (q--){
        int a,b;
        cin>>a>>b;
        if (a/k>=b/k){
            cout<<"-1"<<endl;
            return;
        }
        int z=b/k-a/k;
        int ansPrev[k][k];
        for (int k1=0;k1<k;k1++){
            for (int k2=0;k2<k;k2++){
                if (k1!=k2) ansPrev[k1][k2]=99999999999;
                else ansPrev[k1][k2]=0;
            }
        }
        int ans[k][k];
        int pos=a/k;
        for (int j=0;j<18;j++){
            if (z&(1<<j)){
                for (int k1=0;k1<k;k1++){
                    for (int k2=0;k2<k;k2++){
                        ans[k1][k2]=99999999999;
                        for (int z=0;z<k;z++){
                            ans[k1][k2]=min(ans[k1][k2],ansPrev[k1][z]+bj[pos][z][k2][j]);
                            //if (k1==0 && k2==2)cout<<"   "<<z<<" "<<ansPrev[k1][z]+bj[pos][z][k2][j]<<endl;
                        }
                        //if (k1==0 && k2==2) cout<<ans[k1][k2]<<endl;
                    }
                }
                pos+=(1<<j);
            }
        }
        for (int k1=0;k1<k;k1++){
            for (int k2=0;k2<k;k2++){
                ansPrev[k1][k2]=ans[k1][k2];
            }
        }
        if (ans[a%k][b%k]>=99999999999) cout<<-1<<endl;
        else cout<<ans[a%k][b%k]<<endl;
    }

    

}
 
 
 
 
 
 
 
 
int32_t main(){
    
    BERKAY_TUP;
    if (usaco){
        freopen("optmilk.in", "r", stdin);
        freopen("optmilk.out", "w", stdout);
    }
    if (!interactive){
    #ifdef Local
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
        //freopen("wormsort.out", "w", stdout);
    #endif
    }
    if (t==1) solve();
    else{
        cin>>t;
        while (t--){testCase++;solve();}
    }
    
        
    return 0;
}

Compilation message

toll.cpp: In function 'void solve()':
toll.cpp:42:20: warning: unused variable 'g2' [-Wunused-variable]
   42 |         int g1=x/k,g2=g1+1;
      |                    ^~
toll.cpp: In function 'int32_t main()':
toll.cpp:113:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |         freopen("optmilk.in", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:114:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |         freopen("optmilk.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 8.0

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

Subtask #4
0 / 31.0

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

Subtask #5
0 / 44.0

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