Submission #1143936

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143936		zawos	Toll (BOI17_toll)	C++20	100 / 100	69 ms	25756 KiB

toll

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define FOR(i,a,b) for (int i = (a); i < (b); i++)
using namespace std;
using namespace __gnu_pbds;
using ll=long long;
using ld=long double;
using vi=vector<int>;
template<class T> using oset =tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update> ;
//上
const int N = 50010;
const int inf = 1000000000;
int dst[N][20][5],msk[N];
ll k,n,m,o; 
void divi(int l,int r,int lvl,vector<vector<int>> &AL,vector<vector<int>> &nAL){
    if(l == r) return;
    int mid = (l+r)/2;
    int medio = k*(mid+1)-1;
    for(int i = 0; i <k;i++) dst[medio-i][lvl][k-1-i] =0;
    for(int i = medio-k; i >= l*k;i--){
        for(int j = 0; j <k;j++){
            if(AL[i][j]){
                for(int rr = 0; rr < k;rr++){
                    dst[i][lvl][rr] = min(dst[i][lvl][rr],dst[(i/k+1)*k+j][lvl][rr]+AL[i][j]);
                    if(dst[i][lvl][rr] > inf) dst[i][lvl][rr] = inf;
                }
                
            }
        }
    }
    medio++;
    for(int i = 0; i <k;i++) for(int j =0; j<k;j++){
        if(medio + i < n){
            if(nAL[medio+i][j]) dst[medio+i][lvl][j] = nAL[medio+i][j];
        }
    }
    for(int i = medio+k; i <r*k+k &&i < n;i++){
        for(int j = 0; j <k;j++){
            if(nAL[i][j]){
                for(int rr = 0; rr < k;rr++){
                    dst[i][lvl][rr] = min(dst[i][lvl][rr],dst[(i/k-1)*k+j][lvl][rr]+nAL[i][j]);
                    if(dst[i][lvl][rr] > inf) dst[i][lvl][rr] = inf;
                }
            }
        }
    }
    for(int i = mid+1; i<=r;i++) msk[i]^=(1<<lvl);
    divi(l,mid,lvl+1,AL,nAL);
    divi(mid+1,r,lvl+1,AL,nAL);
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> k >> n >> m >> o;
    FOR(i,0,n) FOR(j,0,20) FOR(xx,0,5) dst[i][j][xx] = inf;
    memset(msk,0,sizeof(msk));
    vector<vector<int>> AL(n,vector<int>(k));
    vector<vector<int>> nAL(n,vector<int>(k));
    for(int i = 0; i< m;i++){
        int a,b,toll; cin >> a >> b >> toll;
        AL[a][b%k] = toll;
        nAL[b][a%k] = toll;
    }
    divi(0,(n+k-1)/k-1,0,AL,nAL);

    for(int i = 0; i < o; i++){
        int a,b; cin >> a >> b;
        if(a/k == b/k) cout <<"-1\n";
        else{
            int bits = __builtin_ctz(msk[a/k]^msk[b/k]);
            int ans = 1e9;
            for(int rr = 0; rr < k;rr++){
                ans = min(ans,dst[a][bits][rr]+dst[b][bits][rr]);
            }
            if(ans == 1e9){
                cout <<-1<<'\n';
            }else cout << ans<<'\n';
        }
    }
}

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