Submission #924492

#	Time	Username	Problem	Language	Result	Execution time	Memory
924492		Faisal_Saqib	Toll (BOI17_toll)	C++17	0 / 100	3090 ms	10072 KiB

toll

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int N=5e4+2;
vector<pair<int,int>> ma[N],query[N];
vector<int> block[N];
int index[N];
bool vis[N];
int ans[N];
int Dist_next[6][N];
int Dist_this[6][N];
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int k,n,m,q;
    cin>>k>>n>>m>>q;
    for(int j=0;j<m;j++)
    {
        int a,b,t;
        cin>>a>>b>>t;
        ma[a].push_back({b,t});
    }
    for(int lp=0;lp<q;lp++)
    {
        int x,y;
        cin>>x>>y;
        query[x].push_back({y,lp});
    }
    for(int i=0;i<n;i++)
    {
        index[i]=block[i/k].size();
        block[(i/k)].push_back(i);
    }
    for(int ind=0;ind<k;ind++)
        for(int l=0;l<n;l++)
            Dist_next[ind][l]=Dist_this[ind][l]=1e9;
    for(int i=n-1;i>=0;i--)
    {
        if(!vis[(i/k)])
        {
            vis[(i/k)]=1;
	        // cout<<"Block: ";
            for(int& vertex:block[i/k])
            {
            	// cout<<vertex<<' ';
                Dist_this[index[vertex]][vertex]=0;
                for(auto& [adj,wei]:ma[vertex])
                {
                    Dist_this[index[vertex]][adj]=wei;
                    for(int to=i+1;to<n;to++)
                    {
                        Dist_this[index[vertex]][to]=min(Dist_this[index[vertex]][to],Dist_next[index[adj]][to]+wei);
                    }
                }
                for(auto& [y,inp]:query[vertex])
                {
                    if(y==vertex)
                    {
                        ans[inp]=0;
                    }
                    else if(y<(i+1))
                    {
                        ans[inp]=-1;
                    }
                    else
                    {
                        ans[inp]=((Dist_this[index[vertex]][y]==1e9)?-1:Dist_this[index[vertex]][y]);
                    }
                }
            }
            // cout<<endl;
            for(int ind=0;ind<k;ind++)
            {
                for(int l=i;l<n;l++)
                {
                    if(ind<block[(i/k)].size() and block[(i/k)][ind]==l)
                        Dist_this[ind][l]=0;
                    Dist_next[ind][l]=Dist_this[ind][l];
                    // cout<<Dist_next[ind][l]<<' ';
                    Dist_this[ind][l]=1e9;
                }
                // cout<<endl;
            }
            // cout<<"change block\n";
        }
    }
    for(int lp=0;lp<q;lp++)
        cout<<ans[lp]<<'\n';
    return 0;
}

Compilation message (stderr)

toll.cpp: In function 'int main()':
toll.cpp:79:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |                     if(ind<block[(i/k)].size() and block[(i/k)][ind]==l)
      |                        ~~~^~~~~~~~~~~~~~~~~~~~

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