Submission #924503

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

toll

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
// #define int long long
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];
signed 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: ";
            int st=block[i/k].back()+1;
            for(int& vertex:block[i/k])
            {
                // cout<<vertex<<' ';
                for(auto& [adj,wei]:ma[vertex]) // O(k)
                {
                    Dist_this[index[vertex]][adj]=wei;
                    for(int to=st;to<n;to++)
                    {
                        if(to>block[adj/k].back())
                            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]);
                    }
                }
            }
            for(int ind=0;ind<k;ind++)
            {
                for(int l=st;l<n;l++)
                {
                    Dist_next[ind][l]=Dist_this[ind][l];
                    Dist_this[ind][l]=1e9;
                }
            }
        }
    }
    for(int lp=0;lp<q;lp++)
        cout<<ans[lp]<<'\n';
    return 0;
}

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