Submission #491592

#	Time	Username	Problem	Language	Result	Execution time	Memory
491592		stefantaga	Toll (BOI17_toll)	C++14	100 / 100	239 ms	42704 KiB

toll

#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<<"-1"<<'\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 (stderr)

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 / 7
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 31 / 31
• Subtask 5: 44 / 44