제출 #182423

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
182423		nicolaalexandra	Toll (BOI17_toll)	C++14	7 / 100	214 ms	32308 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] = 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][j] != INF && aint[fiu_dr][j][t] != INF)
                    aint[nod][i][t] = min (aint[nod][i][t],aint[fiu_st][i][j] + aint[fiu_dr][j][t]);

}
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 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][j] != INF && intv[idx][j][t] != INF)
                            aux[i][t] = sol[i][j] + intv[idx][j][t];

            for (int i=0;i<k;i++)
                for (int j=0;j<k;j++)
                    sol[i][j] = aux[i][j];
        }
        /// acum pt ultimul
        int mini = INF;
        if (el > 1){
            for (int i=0;i<k;i++)
                for (int j=0;j<k;j++)
                    if (sol[i][j] != INF && intv[el][j][y%k] != INF)
                        mini = min (mini,sol[i][j] + intv[el][j][y%k]);
        } else mini = sol[x%k][y%k];

        if (mini == INF)
            cout<<-1<<"\n";
        else cout<<mini<<"\n";
    }

    return 0;
}

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