Submission #129906

#	Time	Username	Problem	Language	Result	Execution time	Memory
129906		Abelyan	Toll (BOI17_toll)	C++17	100 / 100	204 ms	47932 KiB

toll

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
 
#define FOR(i,a) for (int i=0;i<(a);++i)
#define FORD(i,a) for (int i=(a)-1;i>=0;i--)
#define FORT(i,a,b) for (int i=(a);i<=(b);++i)
#define FORTD(i,b,a) for (int i=(b);i>=(a);--i)
#define trav(i,v) for (auto i : v)
#define all(v) v.begin(),v.end()
#define ad push_back
#define fr first
#define sc second
#define mpr(a,b) make_pair(a,b)
#define pir pair<int,int>
#define all(v) v.begin(),v.end()
#define make_unique(v) v.erase(unique(all(v)),v.end())
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define srng mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define y1 EsiHancagorcRepa
 
const int N=1e5+10;
const ll MOD=1e9+7;
 
int k,n,m,o;
 
struct node{
    int a[5][5];
    node(){
        FOR(i,5)FOR(j,5)a[i][j]=INT_MAX;
    }
    void operator=(node t){
        FOR(i,5)FOR(j,5)a[i][j]=t.a[i][j];
    }
}sg[4*N],zro;
 
node mrg(node a,node b){
    if (b.a[0][0]==-1)return a;
    if (a.a[0][0]==-1)return b;
    node c;
    FOR(i,k){
        FOR(j,k){
            c.a[i][j]=INT_MAX;
        }
    }
    FOR(i,k){
        FOR(j,k){
            FOR(mj,5){
                if (a.a[i][mj]==INT_MAX)continue;
                if (b.a[mj][j]==INT_MAX)continue;
                c.a[i][j]=min(c.a[i][j],a.a[i][mj]+b.a[mj][j]);
            }
        }
    }
    return c;
}
 
vector<pir> g[N];
 
void build(int v,int tl,int tr){
    //sg[v]=new node();
    if (tl==tr){
        FOR(i,k){
            trav(to,g[tl*k+i]){
                //cout<<"heey "<<sg[v].a[i][to.fr%k]<<endl;
                sg[v].a[i][to.fr%k]=to.sc;
            }
        }
        /*
        cout<<v<<" "<<tl<<" "<<tr<<endl;
        FOR(i,k){
            FOR(j,k){
                cout<<sg[v].a[i][j]<<" ";
            }
            cout<<endl;
        }
        cout<<"************"<<endl;*/
        return;
    }
    int tm=(tl+tr)/2;
    build(v+v,tl,tm);
    build(v+v+1,tm+1,tr);
    sg[v]=mrg(sg[v+v],sg[v+v+1]);
    /*
    cout<<v<<" "<<tl<<" "<<tr<<endl;;
    FOR(i,k){
        FOR(j,k){
            cout<<sg[v].a[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<"************"<<endl;*/
}
 
node query(int v,int tl,int tr,int l,int r){
    //cout<<v<<" "<<tl<<" "<<tr<<" "<<l<<" "<<r<<endl;
    if (l>r) return zro;
    if (tl==l && tr==r)return sg[v];
    int tm=(tl+tr)/2;
    return mrg(query(v+v,tl,tm,l,min(tm,r)),query(v+v+1,tm+1,tr,max(tm+1,l),r));
}
 
int main(){
    fastio;
    srng;
    //cout<<zro.a[1][1]<<endl;
    //zro=new node();
    cin>>k>>n>>m>>o;
    FOR(i,m){
        int a,b,c;
        cin>>a>>b>>c;
        g[a].ad({b,c});
        //g[b].ad({a,c});
    }
    zro.a[0][0]=-1;
    while(n%k)n++;
    int qan=n/k;
    build(1,0,qan);
    FOR(i,o){
        int l,r;
        cin>>l>>r;
        if (l/k>=r/k){
            cout<<-1<<endl;
            continue;
        }
        node tv=query(1,0,qan,l/k,r/k-1);
        if (tv.a[l%k][r%k]==INT_MAX)cout<<-1<<endl;
        else cout<<tv.a[l%k][r%k]<<endl;
    }
 
    return 0;
}

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