Submission #182430

#	Time	Username	Problem	Language	Result	Execution time	Memory
182430		nicolaalexandra	Toll (BOI17_toll)	C++14	100 / 100	414 ms	32236 KiB

toll

#include <bits/stdc++.h>
#define DIM 50010
#define INF 2000000000
using namespace std;
int k,n,m,q,i,j,x,y,el,cost,nr;
int aint[DIM*4][6][6],sol[6][6],aux[6][6],intv[DIM][6][6];
vector <pair<int,int> > L[DIM];
void init (int a[][6]){
    for (int i=0;i<k;i++)
        for (int j=0;j<k;j++)
            a[i][j] = INF;
}
void build (int nod, int st, int dr){
    if (st == dr){
        /// practic eu in nod tin minte costul sa ajung din st in st+1
        for (int i=st*k;i<min((st+1)*k,n);i++){
            for (auto it:L[i]){
                int j = it.first, cost = it.second;
                aint[nod][i%k][j%k] = min(aint[nod][i%k][j%k],cost);
            }
        }
        return;
    }
    int mid = (st+dr)>>1;
    build (nod<<1,st,mid);
    build ((nod<<1)|1,mid+1,dr);

    int fiu_st = nod<<1, fiu_dr = (nod<<1)|1;
    /// vr sa combin doua intervale, st mid si mid+1 dr
    /// costul de ajung din st in dr+1!!
    for (int i=0;i<k;i++)
        for (int j=0;j<k;j++)
            for (int t=0;t<k;t++)
                if (aint[fiu_st][i][t] != INF && aint[fiu_dr][t][j] != INF)
                    aint[nod][i][j] = min (aint[nod][i][j],aint[fiu_st][i][t] + aint[fiu_dr][t][j]);

}
void query (int nod, int st, int dr, int x, int y){
    if (x <= st && dr <= y){
        el++;
        for (int i=0;i<k;i++)
            for (int j=0;j<k;j++)
                intv[el][i][j] = aint[nod][i][j];
        return;
    }
    int mid = (st+dr)>>1;
    if (x <= mid)
        query (nod<<1,st,mid,x,y);
    if (y > mid)
        query ((nod<<1)|1,mid+1,dr,x,y);
}
int main (){
    //ifstream cin ("date.in");
    //ofstream cout ("date.out");
    cin>>k>>n>>m>>q;
    for (i=1;i<=m;i++){
        cin>>x>>y>>cost;
        L[x].push_back(make_pair(y,cost));
    }
    nr = (n-1)/k;
    for (i=1;i<=4*nr;i++)
        init (aint[i]);

    build (1,0,nr);

    for (;q--;){
        cin>>x>>y;
        if (x/k >= y/k){
            cout<<-1<<"\n";
            continue;
        }
        el = 0;
        query (1,0,nr,x/k,y/k-1);
        /// pt primul interval un rest il am deja stabilit
        init(sol);

        //for (i=0;i<k;i++)
          //  sol[x%k][i] = intv[1][x%k][i];
        for (int i=0;i<k;i++)
            for (int j=0;j<k;j++)
                sol[i][j] = intv[1][i][j];

        for (int idx=2;idx<=el;idx++){
            init (aux);
            for (int i=0;i<k;i++)
                for (int j=0;j<k;j++)
                    for (int t=0;t<k;t++)
                        if (sol[i][t] != INF && intv[idx][t][j] != INF)
                            aux[i][j] = min (aux[i][j],sol[i][t] + intv[idx][t][j]);

            for (int i=0;i<k;i++)
                for (int j=0;j<k;j++)
                    sol[i][j] = aux[i][j];
        }

        if (sol[x%k][y%k] == INF)
            cout<<-1<<"\n";
        else cout<<sol[x%k][y%k]<<"\n";
    }

    return 0;
}

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