Submission #447404

#	Time	Username	Problem	Language	Result	Execution time	Memory
447404		zaneyu	Toll (BOI17_toll)	C++14	100 / 100	158 ms	42768 KiB

toll

/*input
5 14 5 5
0 5 9
5 12 10
0 7 7
7 12 8
4 7 10
0 12
0 5
0 7
7 12
0 13
*/
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
#define REP(i,n) for(int i=0;i<n;i++)
#define MNTO(x,y) x=min(x,(__typeof__(x))y)
#define MXTO(x,y) x=max(x,(__typeof__(x))y)
#define pii pair<int,int>
#define pb push_back
#define f first
#define ll long long
#define s second
const int INF=0x3f3f3f3f;
const ll INF64=4e18;
struct node{
    ll dist[5][5];
}seg[4*maxn];
inline node merge(node a,node b){
    node c;
    REP(i,5) REP(j,5) c.dist[i][j]=INF64;
    REP(k,5){
        REP(i,5){
            REP(j,5){
                MNTO(c.dist[i][j],a.dist[i][k]+b.dist[k][j]);
            }
        }
    }
    return c;
}
inline void upd(int idx,int l,int r,int p,int i,int j,int x){
    if(r<p or l>p) return;
    if(l==r){
        seg[idx].dist[i][j]=x;
        return;
    }
    int mid=(l+r)/2;
    upd(idx*2,l,mid,p,i,j,x);
    upd(idx*2+1,mid+1,r,p,i,j,x);
    //seg[idx]=merge(seg[idx*2],seg[idx*2+1]);
}
inline void mrg(int idx,int l,int r){
    if(l==r) return;
    int mid=(l+r)/2;
    mrg(idx*2,l,mid);
    mrg(idx*2+1,mid+1,r);
    seg[idx]=merge(seg[idx*2],seg[idx*2+1]);
}
inline node query(int idx,int l,int r,int ql,int qr){
    //node c;
    //REP(i,5) REP(j,5) c.dist[i][j]=0;
    //if(r<ql or l>qr) return c;
    if(ql<=l and r<=qr) return seg[idx];
    int mid=(l+r)/2;
    if(mid<ql) return query(idx*2+1,mid+1,r,ql,qr);
    if(mid>=qr) return query(idx*2,l,mid,ql,qr); 
    return merge(query(idx*2,l,mid,ql,qr),query(idx*2+1,mid+1,r,ql,qr));
}
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int k,n,m,q;
    cin>>k>>n>>m>>q;
    REP(i,4*n) REP(j,5) REP(k,5) seg[i].dist[j][k]=INF64;
    REP(i,m){
        int a,b,c;
        cin>>a>>b>>c;
        upd(1,0,(n/k),a/k,a%k,b%k,c);
    }
    mrg(1,0,(n/k));
    REP(i,q){
        int a,b;
        cin>>a>>b;
        if((a/k)>=(b/k)){
            cout<<"-1\n";
            continue;
        }
        node z=query(1,0,(n/k),a/k,b/k-1);
        ll x=z.dist[a%k][b%k];
        if(x==INF64) x=-1;
        cout<<x<<'\n';
    }
}

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