Submission #1239303

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239303		lambd47	Toll (BOI17_toll)	C++20	0 / 100	119 ms	176704 KiB

toll

#include <bits/stdc++.h>

#define int long long
using namespace std;

#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)

std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());

const int T=180;
const int INF=1e15;

typedef array<array<int,5>,5> mat;
void solve() {
    int k,n,m,q;cin>>k>>n>>m>>q;
    n/=T;n*=T;n+=T;
    const array<int,5> BigChungus={INF,INF,INF,INF,INF};
    const mat HugeChungus={BigChungus,BigChungus,BigChungus,BigChungus,BigChungus};
    vector<mat> adj(n/k,HugeChungus);
    L(i,0,m-1){
        int a,b,w;cin>>a>>b>>w;
        adj[a/k][a%k][b%k]=w;
    }
    auto merge=[&](mat a,mat& b)->mat{
        mat aux=HugeChungus;
        L(i,0,k-1){
            L(j,0,k-1){
                L(f,0,k-1){
                    aux[i][j]=min(aux[i][j],a[i][f]+b[f][j]);
                }
            }
        }
        return aux;
    };
/*
    for(int i=t-1;i<n;i+=t){
        for(int j=0;j<t;j+=k){
            int at=i-k+1-j*k;
            if(j==0){
                l(f,0,k-1)dp[at/k][f][f]=0;
            }
            else{
                l(f,0,k-1)dp[at/k]=merge(adj[at/k],dp[at/k+1]);
            }
        }
    }
    */

    
    const int lg=16;
    vector<vector<mat>> dp(lg,vector<mat>(n/k));
    int lim=n/k;
    L(i,0,lg-1){
        L(j,0,lim-1){
            if(i==0){
                dp[i][j]=adj[j];
            }
            else{
                if((1<<(i-1))+j<lim){
                    dp[i][j]=merge(dp[i-1][j],dp[i-1][j+(1<<(i-1))]);
                }
            }
        }
    }
    while(q--){
        int a,b;cin>>a>>b;
        if(a>b)swap(a,b);
        int na=a/k;
        int nb=b/k;
        int d=nb-na;
        if(nb==na){
            cout<<-1<<"\n";continue;
        }
        bool ok=0;
        mat aux;
        L(i,0,lg-1){
            if(d&(1<<i)){
                if(!ok){
                    aux=dp[i][na];
                    na+=(1<<i);
                }
                else{
                    ok=1;
                    aux=merge(aux,dp[i][na]);
                    na+=(1<<i);
                }
            }
        }
        cout<<(aux[a%k][b%k]<INF?aux[a%k][b%k]:-1)<<"\n";
    }

}
 
int32_t main() {
    std::cin.tie(0)->sync_with_stdio(0); 
    std::cin.exceptions(std::cin.failbit);

    int T = 1;
//    std::cin >> T;
    while(T--) {
        solve();
    }

	return 0;
}

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