Submission #1107140

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107140		hihihihaw	Toll (BOI17_toll)	C++17	100 / 100	146 ms	179984 KiB

toll

#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;
            continue;
        }
        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)){
                //cout<<"    "<<j<<endl;
                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==0)cout<<"   "<<z<<" "<<bj[pos][z][k2][j]<<endl;
                        }
                        //if (k1==0 && k2==2) cout<<ans[k1][k2]<<endl;
                    }
                }
                //cout<<ans[0][0]<<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 (stderr)

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:116:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |         freopen("optmilk.in", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:117:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |         freopen("optmilk.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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