Submission #924692

#	Time	Username	Problem	Language	Result	Execution time	Memory
924692		Faisal_Saqib	Toll (BOI17_toll)	C++17	100 / 100	237 ms	50628 KiB

toll

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
// #define int long long
const int N=5e4+1000;
vector<pair<int,int>> ma[N];
// int ans[6][6];
// int ans_[6][6];
int n,k;
struct Data
{
    int mat[6][6];
    int block=0;
    Data()
    {
        for(int i=0;i<6;i++)
        {
            for(int j=0;j<6;j++)
            {
                mat[i][j]=1e9;
            }
        }
    }
    Data(int x)
    {
        for(int i=0;i<6;i++)
        {
            for(int j=0;j<6;j++)
            {
                mat[i][j]=x*(i!=j);
            }
        }
    }
    void print()
    {
    	cout<<"Start\n";
    	for(int i=0;i<6;i++)
    	{
    		for(int l=0;l<6;l++)
    		{
    			cout<<mat[i][l]<<' ';
    		}
    		cout<<endl;
    	}
    	cout<<"Finish\n";
    	cout<<"Block "<<block<<endl;
    }
};
Data* seg[N*8];

Data* merge(Data* a,Data* b)
{
    Data* ans=new Data();
    // cout<<"Merge "<<a->block<<' '<<b->block<<endl;
    for(int l=0;l<6;l++)
    {
	    for(int i=0;i<6;i++)
	    {
	    	// for(int j=0;j<6;j++)
	    	// {
	    		// for(auto& [l,w]:ma[(a->block*k)+j])
	    		// {
		    		// ans->mat[j][l%k]=min(ans->mat[j][l%k],a->mat[i][j]+b->mat[j][l%k]+w);
	    		// }
	    	// }
			// cout<<"From  "<<l<<" to "<<i<<' '<<a->mat[l][i]<<endl;
	        for(auto& [j,w]:ma[(a->block*k)+i])
	        {
	        	for(int p=0;p<6;p++)
	        	{
	        		// cout<<"For "<<
		        	ans->mat[l][p]=min(ans->mat[l][p],a->mat[l][i]+w+b->mat[j%k][p]);
	        	}
            }
        }
    }
    ans->block=b->block;
    // cout<<"APDS\n";
    return ans;
    
}
void build(int v=1,int s=0,int e=(n-1)/k)
{
	// cout<<s<<' '<<e<<' '<<v<<endl;
    if(s==e)
    {
        seg[v]=new Data(1e9);
        seg[v]->block=s;
        // cout<<"Leaf "<<s<<endl;
        // seg[v]->print();
        return;
    }
    int lc=(2*v);
    int rc=lc+1;
    int mid=(s+e)/2;
    build(lc,s,mid);
    build(rc,mid+1,e);
    seg[v]=new Data();
    seg[v]=merge(seg[lc],seg[rc]);
	// cout<<"For range "<<s<<' '<<e<<endl;
	// seg[v]->print();
}
Data* get(int l,int r,int v=1,int s=0,int e=(n-1)/k)
{
	// if(r<s or e<l)
	// {
		// Data* ap=new Data(0);
		// return ap;
	// }
    Data* ap;
	if(l<=s and e<=r)
	{
		ap=seg[v];		
	}
	else
	{
	    int lc=(2*v);
	    int rc=lc+1;
	    int mid=(s+e)/2;
	    if(s<=r and mid>=l)
	    {
	    	ap=get(l,r,lc,s,mid);
	    	if((mid+1)<=r and e>=l)
	    	{
	    		ap=merge(ap,get(l,r,rc,mid+1,e));
	    	}
	    }
	    else
	    {
	    	if((mid+1)<=r and e>=l)
	    	{
	    		ap=get(l,r,rc,mid+1,e);
	    	}
	    }
	}
	if(ap==NULL)
		exit(-1);
    return ap;
}
signed main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int 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 l=0;l<n;l++)
    //     for(int ind=0;ind<k;ind++)
    //         for(int p=0;p<k;p++)
    //             Dist[l][ind][p]=1e9;
    // for(int i=0;i<n;i++)
    //     Dist[(i/k)][i%k][i%k]=we;
    build();
    for(int lp=0;lp<q;lp++)
    {
        int x,y;
        cin>>x>>y;
        int cur_block=x/k;
        int block_to=y/k;
        Data* apl=get(cur_block,block_to);
        int ansp=apl->mat[x%k][y%k];
        if(ansp==1e9)
        {
            cout<<-1<<'\n';
        }
        else
        {
            cout<<ansp<<'\n';
        }
    }
    return 0;
}

Compilation message (stderr)

toll.cpp: In function 'Data* get(int, int, int, int, int)':
toll.cpp:139:12: warning: 'ap' may be used uninitialized in this function [-Wmaybe-uninitialized]
  139 |     return ap;
      |            ^~

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