Submission #1266398

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266398		abcdxyz123	Toll (BOI17_toll)	C++17	100 / 100	67 ms	10468 KiB

toll

#include<bits/stdc++.h>
#define inf 1000000000
#define pi pair<int,int>
#define fi first
#define se second
#define maxn 50005
#define maxk 10
using namespace std;
int k,n,m,q;
int dp[maxn][maxk];
vector<pi>in[maxn];
vector<pi>out[maxn];
int idb(int i)
{
    return i/k;
}
int lb(int i)
{
    return i*k;
}
int rb(int i)
{
    return min(n-1,(i+1)*k-1);
}
struct node
{
    int s,t,id;
    node(int s=0,int t=0,int id=0)
    {
        this->s=s;
        this->t=t;
        this->id=id;
    }
};
int ans[maxn];
void dnc(int l,int r,vector<node>&Query)
{
    if(l>r)return ;
    if(l==r)
    {
        for(auto[s,t,id]:Query)
        {
            ans[id]=inf;
        }
        return;
    }
    int mid=(l+r)/2;
    for(int i=l;i<=r;i++)
    {
        for(int u=lb(i);u<=rb(i);u++)
        {
            for(int v=0;v<k;v++)
            {
                dp[u][v]=inf;
            }
        }
    }
    for(int u=lb(mid);u<=rb(mid);u++)
    {
        dp[u][u%k]=0;
    }
    for(int i=mid-1;i>=l;i--)
    {
        for(int u=lb(i);u<=rb(i);u++)
        {
            for(int t=0;t<k;t++)
            {
                for(auto[v,w]:out[u])
                {
                    dp[u][t]=min(dp[u][t],dp[v][t]+w);
                }
            }
        }
    }
    for(int i=mid+1;i<=r;i++)
    {
        for(int u=lb(i);u<=rb(i);u++)
        {
            for(int t=0;t<k;t++)
            {
                for(auto[v,w]:in[u])
                {
                    dp[u][t]=min(dp[u][t],dp[v][t]+w);
                }
            }
        }
    }
    vector<node>QueryL;
    vector<node>QueryR;
    for(auto[s,t,id]:Query)
    {
        if(idb(t)<mid)QueryL.push_back(node(s,t,id));
        else if(idb(s)>mid)QueryR.push_back(node(s,t,id));
        else
        {
            if(idb(s)==idb(t))ans[id]=inf;
            else
            {
                ans[id]=inf;
                for(int x=0;x<k;x++)
                {
                    ans[id]=min(ans[id],dp[s][x]+dp[t][x]);
                }
            }
        }
    }
    dnc(l,mid-1,QueryL);
    dnc(mid+1,r,QueryR);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>k>>n>>m>>q;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        out[u].push_back({v,w});
        in[v].push_back({u,w});
    }
    vector<node>Query;
    for(int i=1;i<=q;i++)
    {
        int u,v;
        cin>>u>>v;
        if(idb(u)>=idb(v))ans[i]=inf;
        else
        {
            Query.push_back(node(u,v,i));
        }
    }
    dnc(0,idb(n),Query);
    for(int i=1;i<=q;i++)
    {
        if(ans[i]==inf)cout<<-1<<'\n';
        else cout<<ans[i]<<'\n';
    }
}

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