Submission #213629

#	Time	Username	Problem	Language	Result	Execution time	Memory
213629		MKopchev	Toll (BOI17_toll)	C++14	100 / 100	160 ms	101624 KiB

toll

#include<bits/stdc++.h>
using namespace std;
const int nmax=5e4+42;

int k,n,m,q;

int dist[20][nmax][5][5];

int dist_1[5][5],dist_2[5][5],dist_3[5][5];

void my_merge()
{
    memset(dist_3,-1,sizeof(dist_3));
    for(int i=0;i<k;i++)
        for(int j=0;j<k;j++)
            for(int p=0;p<k;p++)
                if(dist_1[i][j]!=-1&&dist_2[j][p]!=-1)
                {
                    int is=dist_1[i][j]+dist_2[j][p];
                    if(dist_3[i][p]==-1)dist_3[i][p]=is;
                    else dist_3[i][p]=min(dist_3[i][p],is);
                }

}

int current_dists[5],help[5];

int query()
{
    int u,v;
    scanf("%i%i",&u,&v);

    memset(current_dists,-1,sizeof(current_dists));
    current_dists[u%k]=0;

    int beg=u/k,en=v/k;
    for(int step=19;step>=0;step--)
        if(beg+(1<<step)<=en)
        {
            memset(help,-1,sizeof(help));

            for(int j=0;j<k;j++)
                for(int p=0;p<k;p++)
                    if(current_dists[j]!=-1&&dist[step][beg][j][p]!=-1)
                    {
                        int is=current_dists[j]+dist[step][beg][j][p];
                        if(help[p]==-1)help[p]=is;
                        else help[p]=min(help[p],is);
                    }
            for(int j=0;j<k;j++)
                current_dists[j]=help[j];

            beg=beg+(1<<step);
        }
    return current_dists[v%k];
}
int main()
{
    memset(dist,-1,sizeof(dist));
    scanf("%i%i%i%i",&k,&n,&m,&q);

    int a,b,t;
    for(int i=1;i<=m;i++)
    {
        scanf("%i%i%i",&a,&b,&t);
        dist[0][a/k][a%k][b%k]=t;
    }

    for(int step=1;step<20;step++)
    {
        for(int i=0;i+(1<<step)-1<=n/k;i++)
        {
            for(int j=0;j<k;j++)
                for(int p=0;p<k;p++)
                {
                    dist_1[j][p]=dist[step-1][i][j][p];
                    dist_2[j][p]=dist[step-1][i+(1<<(step-1))][j][p];
                }

            my_merge();

            for(int j=0;j<k;j++)
                for(int p=0;p<k;p++)
                    dist[step][i][j][p]=dist_3[j][p];
        }
    }

    for(int i=1;i<=q;i++)
        printf("%i\n",query());
    return 0;
}

Compilation message (stderr)

toll.cpp: In function 'int query()':
toll.cpp:31:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i%i",&u,&v);
     ~~~~~^~~~~~~~~~~~~~
toll.cpp: In function 'int main()':
toll.cpp:60:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i%i%i%i",&k,&n,&m,&q);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:65:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i%i%i",&a,&b,&t);
         ~~~~~^~~~~~~~~~~~~~~~~~~

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