Submission #198048

#	Time	Username	Problem	Language	Result	Execution time	Memory
198048		Andrei_Cotor	Toll (BOI17_toll)	C++14	100 / 100	259 ms	24840 KiB

toll

//alternativ cu rmq, aceasi complexitate
#include<iostream>
#include<vector>

using namespace std;

vector<pair<int,int> > A[50005],Qu[50005];
int k,DpSt[50005][7][7],DpDr[50005][7][7],Rez[10005];
pair<int,int> Q[10005];

void solve(int st, int dr)
{
    if(st==dr)
    {
        for(auto qu:Qu[st])
        {
            if(qu.first!=st)
                continue;

            if(Q[qu.second].first==Q[qu.second].second)
                Rez[qu.second]=0;
        }
        return;
    }

    int mij=(st+dr)/2;

    for(int i=st; i<=mij; i++)
        for(int j=0; j<k; j++)
            for(int ind=0; ind<k; ind++)
                DpSt[i][j][ind]=1000000000;

    for(int i=mij; i<=dr; i++)
        for(int j=0; j<k; j++)
            for(int ind=0; ind<k; ind++)
                DpDr[i][j][ind]=1000000000;

    for(int i=0; i<k; i++)
        DpSt[mij][i][i]=DpDr[mij][i][i]=0;

    for(int i=mij; i<dr; i++)
    {
        for(int j=0; j<k; j++)   //la mij am fost in j
        {
            for(int ind=0; ind<k; ind++)   //la i am fost in ind
            {
                for(auto other:A[i*k+ind])
                    DpDr[i+1][j][other.first%k]=min(DpDr[i+1][j][other.first%k],DpDr[i][j][ind]+other.second);
            }
        }
    }

    for(int i=mij-1; i>=st; i--)
    {
        for(int j=0; j<k; j++)
        {
            for(int ind=0; ind<k; ind++)
            {
                for(auto other:A[i*k+ind])
                    DpSt[i][j][ind]=min(DpSt[i][j][ind],DpSt[i+1][j][other.first%k]+other.second);
            }
        }
    }

    for(int i=st; i<=mij; i++)
    {
        for(auto qu:Qu[i])
        {
            if(qu.first<=mij || qu.first>dr)
                continue;

            for(int j=0; j<k; j++)
                Rez[qu.second]=min(Rez[qu.second],DpSt[i][j][Q[qu.second].first%k]+DpDr[qu.first][j][Q[qu.second].second%k]);
        }
    }

    solve(st,mij);
    solve(mij+1,dr);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n,q,m;
    cin>>k>>n>>m>>q;

    for(int i=1; i<=m; i++)
    {
        int x,y,t;
        cin>>x>>y>>t;
        A[x].push_back({y,t});
    }

    for(int i=1; i<=q; i++)
    {
        int x,y;
        cin>>x>>y;

        Q[i]={x,y};
        Qu[x/k].push_back({y/k,i});

        Rez[i]=1000000000;
    }

    solve(0,n/k);

    for(int i=1; i<=q; i++)
    {
        if(Rez[i]==1000000000)
            cout<<"-1\n";
        else
            cout<<Rez[i]<<"\n";
    }
    return 0;
}

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