Submission #1262163

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262163		quangykqh	Toll (BOI17_toll)	C++20	0 / 100	55 ms	41540 KiB

toll

#include<bits/stdc++.h>
using namespace std;
const int MN=1e6+1209;
long long n,m,k,ans,a[MN],q,nxt[50020][21][5],pfsum[MN],val[5],val1[5],MIN;
string skibidi,sex;
int take(int i,int j,int x)
{
    return ((i/k)+(1<<j))*k+x;
}
int main()
{
    if(fopen("GAME.INP","r"))
    {
        freopen("GAME.INP","r",stdin);
        freopen("GAME.OUT","w",stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>k>>n>>m>>q;
    for(int i=0;i<n;i++)
    {
        for(int x=0;x<k;x++)
        {
            nxt[i][0][x]=9e15;
        }
    }
    for(int i=1;i<=m;i++)
    {
        long long x,y,l;
        cin>>x>>y>>l;
        nxt[x][0][y%k]=min(nxt[x][0][y%k],l);
    }
    for(int i=0;i<n;i++)
    {
        for(int j=1;j<=20;j++)
        {
            for(int x=0;x<k;x++)
            {
                if(take(i,j,x)>=n)continue;
                nxt[i][j][x]=9e15;
                for(int p=0;p<k;p++)
                {
                    nxt[i][j][x]=min(nxt[i][j][x],nxt[i][j-1][p]+nxt[take(i,j-1,p)][j-1][x]);
                }
            }
        }
    }
    while(q--)
    {
        int x,y;
        cin>>x>>y;
        int cnt=y/k-x/k;
        int flo=x/k;
        for(int i=0;i<k;i++)val[i]=9e15;
        val[x%k]=0;
        for(int i=20;i>=0;i--)
        {
            if((1<<i)>cnt)continue;
            cnt-=(1<<i);
            for(int j=0;j<k;j++)
            {
                val1[j]=9e15;
                for(int p=0;p<k;p++)
                {
                    val1[j]=min(val1[j],val[x]+nxt[flo*k+p][i][j]);
                }
            }
            flo+=(1<<i);
            for(int j=0;j<k;j++)
            {
                val[j]=val1[j];
            }
        }
        cout<<(val[y%k]>=8999999999999999?-1:val[y%k])<<'\n';
    }

}

Compilation message (stderr)

toll.cpp: In function 'int main()':
toll.cpp:14:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |         freopen("GAME.INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
toll.cpp:15:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |         freopen("GAME.OUT","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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