Submission #1093542

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093542		DucNguyen2007	Toll (BOI17_toll)	C++14	100 / 100	174 ms	14616 KiB

toll

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
const int maxN=5e4+5,INF=1e9;
const ll inf=2e18;
int n,k,m,q,ans[maxN+1],d[maxN+1][7][2];
vector<pii> adj[maxN+1],adj_rv[maxN+1];
struct query
{
    int l,r,id;
};
vector<query> p;
struct duongdi
{
    int u,w;
    bool operator < (const duongdi &o)const
    {
        return w>o.w;
    }
};
priority_queue<duongdi> pq;
void clr(int l,int r,int id)
{
    for(int i=l;i<=r;i++)
    {
        d[i][id][0]=d[i][id][1]=INF;
    }
}
void dijkstra(int s,int t,int type,int l,int r,vector<pii> adj[])
{
    d[s][t][type]=0;
    pq.push({s,0});
    while(!pq.empty())
    {
        duongdi tmp=pq.top();
        int u=tmp.u,w=tmp.w;
        //cout<<u<<" "<<w<<'\n';
        pq.pop();
        if(d[u][t][type]<w)
        {
            continue;
        }
        for(auto [v,nw]:adj[u])
        {

            if(v/k>r||v/k<l)
            {
                continue;
            }
            //cout<<v<<" "<<nw<<" "<<d[v][t][type]<<'\n';
            if(d[v][t][type]>d[u][t][type]+nw)
            {
                d[v][t][type]=d[u][t][type]+nw;
                pq.push({v,d[v][t][type]});
            }
        }
    }
}
void Dnc(int l,int r,vector<query> v)
{
    if(v.empty())
    {
        return;
    }
    if(l==r)
    {
        for(int i=0;i<k;i++)
        {
            clr(l*k,(r+1)*k-1,i);
            dijkstra(l*k+i,i,1,l,r,adj);
        }
        for(auto j:v)
        {
            if(d[j.r][j.l%k][1]==INF)
            {
                ans[j.id]=-1;
            }
            else ans[j.id]=d[j.r][j.l%k][1];
        }
        return;
    }
    int mid=(l+r)/2;
    for(int i=mid*k;i<(mid+1)*k;i++)
    {
        clr(l*k,(r+1)*k-1,i%k);
        dijkstra(i,i%k,0,l,mid,adj_rv);
        dijkstra(i,i%k,1,mid+1,r,adj);
    }
    vector<query> vec[2];
    for(auto j:v)
    {
        if(j.l/k<=mid&&mid<j.r/k)
        {
            int tmp=INF;
            //cout<<l<<" "<<r<<" "<<j.l<<" "<<j.r<<'\n';
            for(int i=0;i<k;i++)
            {
                tmp=min(tmp,d[j.l][i][0]+d[j.r][i][1]);
                //cout<<d[j.l][i][0]<<" "<<d[j.r][i][1]<<'\n';
            }
            if(tmp==INF)
            {
                ans[j.id]=-1;
            }
            else ans[j.id]=tmp;
        }
        if(l<=j.l/k&&j.r/k<=mid)
        {
            vec[0].push_back(j);
        }
        if(mid<j.l/k&&j.r/k<=r)
        {
            vec[1].push_back(j);
        }
    }
    Dnc(l,mid,vec[0]);
    Dnc(mid+1,r,vec[1]);
}
int main()
{
    //freopen("","r",stdin);
    //freopen("","w",stdout);
    ios_base::sync_with_stdio(0);
    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;
        adj[u].push_back({v,w});
        adj_rv[v].push_back({u,w});
    }
    for(int i=1;i<=q;i++)
    {
        int l,r;
        cin>>l>>r;
        p.push_back({l,r,i});
    }
    Dnc(0,n/k,p);
    for(int i=1;i<=q;i++)
    {
        cout<<ans[i]<<'\n';
    }
}
/*2 10 14 1
3 4 5032
0 2 6758
6 9 3324
0 3 2553
1 2 6681
2 4 2802
7 8 7419
2 5 680
7 9 2800
4 6 8953
4 7 409
3 5 2008
5 6 4066
5 7 7370
2 3
*/

Compilation message (stderr)

toll.cpp: In function 'void dijkstra(int, int, int, int, int, std::vector<std::pair<int, int> >*)':
toll.cpp:48:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   48 |         for(auto [v,nw]:adj[u])
      |                  ^

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