Submission #924454

#	Time	Username	Problem	Language	Result	Execution time	Memory
924454		Sir_Ahmed_Imran	Toll (BOI17_toll)	C++17	100 / 100	134 ms	17232 KiB

toll

                              ///~~~LOTA~~~///
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define append push_back
#define add insert
#define nl "\n"
#define ff first
#define ss second
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define L0TA ios_base::sync_with_stdio(false);cin.tie(NULL)
#define N 50000
int k,M;
int a[N][5][5];
vector<vector<int>> g;
vector<vector<int>> seg[4*N];
void build(int v=1,int s=0,int e=M){
    seg[v]=g;
    for(int i=0;i<k;i++)
        for(int j=0;j<k;j++)
            seg[v][i][j]=5e8;
    if(e-s==1){
        for(int i=0;i<k;i++)
            seg[v][i][i]=0;
        return;
    }
    int mid,rc,lc;
    mid=(s+e)/2;
    rc=2*v+1;
    lc=2*v;
    build(lc,s,mid);
    build(rc,mid,e);
    for(int i=0;i<k;i++)
        for(int j=0;j<k;j++)
            for(int l=0;l<k;l++)
                for(int r=0;r<k;r++)
                    seg[v][i][j]=min(seg[v][i][j],
                    seg[lc][i][l]+a[mid-1][l][r]+seg[rc][r][j]);
}
vector<vector<int>> get(int l,int r,int v=1,int s=0,int e=M){
    if(r<=s || e<=l) return g;
    if(l<=s && e<=r) return seg[v];
    vector<vector<int>> o,p,q;
    int mid,rc,lc;
    mid=(s+e)/2;
    rc=2*v+1;
    lc=2*v;
    p=get(l,r,lc,s,mid);
    q=get(l,r,rc,mid,e);
    o=g;
    if(mid>=r) return p;
    if(mid<=l) return q;
    for(int i=0;i<k;i++)
        for(int j=0;j<k;j++)
            o[i][j]=5e8;
    for(int i=0;i<k;i++)
        for(int j=0;j<k;j++)
            for(int l=0;l<k;l++)
                for(int r=0;r<k;r++)
                    o[i][j]=min(o[i][j],
                    p[i][l]+a[mid-1][l][r]+q[r][j]);
    return o;
}
void solve(){
    int n,m,o,p,q,r;
    cin>>k>>n>>m>>o;
    M=(n+k-1)/k;
    for(int i=0;i<k;i++){
        vector<int> u;
        for(int j=0;j<k;j++)
            u.append(0);
        g.append(u);
    }
    for(int i=0;i<m;i++){
        cin>>p>>q>>r;
        a[p/k][p%k][q%k]=r;
    }
    for(int i=0;i<M;i++)
        for(int j=0;j<k;j++)
            for(int l=0;l<k;l++)
                if(a[i][j][l]==0)
                    a[i][j][l]=5e8;
    build();
    while(o--){
        cin>>p>>q;
        r=get(p/k,q/k+1)[p%k][q%k];
        if(r==5e8) r=-1;
        cout<<r<<nl;
    }
}
int main(){
    L0TA;
    solve();
    return 0;
}

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