oj.uz

Submission #491587

# Submission time Handle Problem Language Result Execution time Memory
491587 2021-12-03T12:14:37 Z stefantaga Toll (BOI17_toll) C++14
7 / 100
 124 ms 39496 KB 
#include <bits/stdc++.h>
#define INF 1000000000000000
using namespace std;
long long k,n,m,o;
long long rmq[50005][20][5],lg,i,j,t,x,y,cost,locx,locy,p,nivelsf,start,sfarsit;
long long din[10][5];
int main()
{
    #ifdef HOME
    ifstream cin("date.in");
    ofstream cout("date.out");
    #endif // HOME
    cin>>k>>n>>m>>o;
    lg=log2(n);
    for (i=0;i<=n;i++)
    {
        for (j=0;j<=lg;j++)
        {
            for (t=0;t<k;t++)
            {
                rmq[i][j][t]=INF;
            }
        }
    }
    for (i=1;i<=m;i++)
    {
        cin>>x>>y>>cost;
        locx=x%k;
        locy=y%k;
        rmq[x][0][locy]=cost;
    }
    p=1;
    for (i=1;i<=lg;i++)
    {
        for (j=0;j<=n;j++)
        {
            nivelsf=j/k+p;
            if (nivelsf+p>n/k)
            {
                continue;
            }
            for (start=0;start<k;start++)
            {
                for (sfarsit=0;sfarsit<k;sfarsit++)
                {
                    rmq[j][i][sfarsit]=min(rmq[j][i-1][start]+rmq[nivelsf*k+start][i-1][sfarsit],rmq[j][i][sfarsit]);
                }
            }
        }
        p=p*2;
    }
    for (;o--;)
    {
        int a,b;
        cin>>a>>b;
        if (a==b)
        {
            cout<<"0"<<'\n';
            continue;
        }
        int niva,nivb,dif;
        niva=a/k;
        nivb=b/k;
        if (niva>=nivb)
        {
            cout<<"0"<<'\n';
            continue;
        }
        dif=nivb-niva;
        int p=1;
        for (i=0;i<k;i++)
        {
            if (a%k==i)
            {
                din[i][0]=0;
            }
            else
            {
                din[i][0]=INF;
            }
            din[i][1]=INF;
        }
        int nivel,pas,acum,inainte;
        nivel=a/k;
        pas=0;
        for (i=0;i<=lg;i++)
        {
            if (dif&p)
            {
                pas++;
                acum=pas%2;
                inainte=1-acum;
                for (j=0;j<k;j++)
                {
                    for (t=0;t<k;t++)
                    {
                        din[t][acum]=min(din[t][acum],din[j][inainte]+rmq[nivel*k+j][i][t]);
                    }
                }
                for (t=0;t<k;t++)
                {
                    din[t][inainte]=INF;
                }
                nivel=nivel+p;
            }
            p=p*2;
        }
        if (din[b%k][acum]==INF)
        {
            cout<<"-1"<<'\n';
        }
        else
        {
            cout<<din[b%k][acum]<<'\n';
        }
    }
    return 0;
}

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:108:26: warning: 'acum' may be used uninitialized in this function [-Wmaybe-uninitialized]
  108 |         if (din[b%k][acum]==INF)
      |             ~~~~~~~~~~~~~^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 39496 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 3 ms 1044 KB Output is correct
6 Correct 3 ms 972 KB Output is correct
7 Correct 4 ms 972 KB Output is correct
8 Correct 85 ms 39428 KB Output is correct
9 Correct 88 ms 39424 KB Output is correct
10 Correct 52 ms 39428 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 8.0

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

Subtask #4
0 / 31.0

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

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 39496 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 3 ms 1044 KB Output is correct
6 Correct 3 ms 972 KB Output is correct
7 Correct 4 ms 972 KB Output is correct
8 Correct 85 ms 39428 KB Output is correct
9 Correct 88 ms 39424 KB Output is correct
10 Correct 52 ms 39428 KB Output is correct
11 Correct 124 ms 39428 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Incorrect 0 ms 204 KB Output isn't correct
14 Halted 0 ms 0 KB -