Submission #1087328

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087328		LeonidCuk	Toll (BOI17_toll)	C++17	100 / 100	142 ms	8532 KiB

toll

#include <bits/stdc++.h>
using namespace std;
int n,k,q;
vector<pair<int,int>>g[50000],que;
vector<int>ans,pom[5];
void daq(int l,int r,vector<int>v)
{
    if(l/k==r/k||l>r)
    {
        return;
    }
    int m=((l+r)/2)/k;
    for(int i=m*k+1;i<=r;i++)
    {
        for(int j=0;j<k;j++)
        {
            pom[j][i]=INT_MAX;
        }
    }
    for(int i=min(m*k,l);i<=r;i++)
    {
        if(i/k==m)
        {
        for(int j=0;j<k;j++)
        {
            if(j==i-m*k)
            {
                pom[j][i]=0;
            }
            else
            {
                pom[j][i]=INT_MAX;
            }
        }
        }
        for(auto p:g[i])
        {
            if(p.first>r)continue;
            for(int j=0;j<k;j++)
            {
                if(pom[j][i]!=INT_MAX)
                {
                    pom[j][p.first]=min(pom[j][i]+p.second,pom[j][p.first]);
                }
            }
        }
    }
    for(int i=m*k-1;i>=l;i--)
    {
        for(int j=0;j<k;j++)
        {
            pom[j][i]=INT_MAX;
        }
        for(auto p:g[i])
        {
            for(int j=0;j<k;j++)
            {
                if(pom[j][p.first]!=INT_MAX)
                {
                    pom[j][i]=min(pom[j][i],pom[j][p.first]+p.second);
                }
            }
        }
    }
    vector<int>todo1,todo2;
    for(auto i:v)
    {
        auto p=que[i];
        if(p.first<m*k&&p.second>=(m+1)*k)
        {
            int res=INT_MAX;
            for(int j=0;j<k;j++)
            {
                if(pom[j][p.first]!=INT_MAX&&pom[j][p.second]!=INT_MAX)
                {
                    res=min(res,pom[j][p.first]+pom[j][p.second]);
                }
            }
            if(res!=INT_MAX)ans[i]=res;
        }
        else if(p.first/k==m&&p.second>=(m+1)*k)
        {
            if(pom[p.first%k][p.second]!=INT_MAX)
            {
                ans[i]=pom[p.first%k][p.second];
            }
        }
        else if(p.second/k==m&&p.first<m*k)
        {
            if(pom[p.second%k][p.first]!=INT_MAX)
            {
                ans[i]=pom[p.second%k][p.first];
            }
        }
        else if(p.second/k<m)
        {
            todo1.push_back(i);
        }
        else if(p.first/k>m)
        {
            todo2.push_back(i);
        }
    }
    m=(l+r)/2;
    daq(l,m,todo1);
    daq(m+1,r,todo2);
}
int main()
{
    int m,a,b,c;
    cin>>k>>n>>m>>q;
    vector<int>todo;
    for(int i=0;i<k;i++)
    {
        pom[i].resize(n);
    }
    for(int i=0;i<m;i++)
    {
        cin>>a>>b>>c;
        g[a].push_back({b,c});
    }
    for(int i=0;i<q;i++)
    {
        ans.push_back(-1);
        cin>>a>>b;
        que.push_back({a,b});
        if(a/k!=b/k)
        {
            todo.push_back(i);
        }
    }
    daq(0,n-1,todo);
    for(int i=0;i<q;i++)
    {
        cout<<ans[i]<<endl;
    }
}

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