oj.uz

Submission #182423

# Submission time Handle Problem Language Result Execution time Memory
182423 2020-01-09T18:59:26 Z nicolaalexandra Toll (BOI17_toll) C++14
7 / 100
 214 ms 32308 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 32308 KB Output is correct
2 Correct 3 ms 1528 KB Output is correct
3 Correct 3 ms 1528 KB Output is correct
4 Correct 3 ms 1532 KB Output is correct
5 Correct 8 ms 2168 KB Output is correct
6 Correct 9 ms 2168 KB Output is correct
7 Correct 9 ms 2168 KB Output is correct
8 Correct 156 ms 32220 KB Output is correct
9 Correct 169 ms 32124 KB Output is correct
10 Correct 73 ms 29820 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 214 ms 18800 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Incorrect 3 ms 1528 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Incorrect 3 ms 1528 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 32308 KB Output is correct
2 Correct 3 ms 1528 KB Output is correct
3 Correct 3 ms 1528 KB Output is correct
4 Correct 3 ms 1532 KB Output is correct
5 Correct 8 ms 2168 KB Output is correct
6 Correct 9 ms 2168 KB Output is correct
7 Correct 9 ms 2168 KB Output is correct
8 Correct 156 ms 32220 KB Output is correct
9 Correct 169 ms 32124 KB Output is correct
10 Correct 73 ms 29820 KB Output is correct
11 Incorrect 214 ms 18800 KB Output isn't correct
12 Halted 0 ms 0 KB -