Submission #727956

#	Time	Username	Problem	Language	Result	Execution time	Memory
727956		Denkata	Toll (BOI17_toll)	C++14	0 / 100	44 ms	7116 KiB

toll

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int maxn = 50006;
const int maxq = 10006;
int i,j,p,q,n,m,k,raz[50006],K,Q,ans[maxq];

struct Put
{
    int v,d;
};
vector <Put> v[50006],obr[50006];
bool operator<(Put a,Put b)
{
    return a.d>b.d;
}
priority_queue <Put> pq;
pair <int,int> quer[maxq];
void dijkstra(int u,int l,int r)
{
   // cout<<"dijkstra ot "<<u<<endl;
    pq.push({u,0});
    while(!pq.empty())
    {
        auto t = pq.top();
        pq.pop();
        if(raz[t.v]==-1)
        {
            raz[t.v] = t.d;
          //  cout<<t.v<<" "<<t.d<<endl;
            for(auto i:v[u])
            {
                if(raz[i.v]==-1 && i.v/K<=r)
                    pq.push({i.v,i.d+t.d});
            }

        }
    }
    pq.push({u,0});
    raz[u]=-1;
    while(!pq.empty())
    {
        auto t = pq.top();
        pq.pop();
        if(raz[t.v]==-1)
        {
            raz[t.v] = t.d;
           //s cout<<t.v<<" "<<t.d<<endl;
            for(auto i:obr[u])
            {
                if(raz[i.v]==-1 && i.v/K>=l)
                    pq.push({i.v,i.d+t.d});
            }
        }
    }
}
void solve(int l,int r,vector <int> zaqvki)
{
    if(l>=r)return ;
    int mid = (l+r)/2;
    vector <int> todo[2];
    for(int j=mid*K;j<(mid+1)*K;j++)
    {
        fill(raz,raz+n+1,-1);
        dijkstra(j,l,r);
        for(auto t:zaqvki)
        {
            p = quer[t].first;
            q = quer[t].second;
            if(p/K<=mid && q/K>=mid)
            {
                //cout<<p<<" zaqvka "<<q<<" "<<raz[p]<<" "<<raz[q]<<endl;
                if(raz[p]!=-1 && raz[q]!=-1)
                    ans[t] = min(ans[t],raz[p]+raz[q]);
                continue;
            }
            todo[p/K>mid].push_back(t);
        }
    }
    if(!todo[0].empty())solve(l,mid-1,todo[0]);
    if(!todo[1].empty())solve(mid+1,r,todo[1]);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>K>>n>>m>>Q;
    for(i=1;i<=m;i++)
    {
        cin>>p>>q>>k;
        v[p].push_back({q,k});
        obr[q].push_back({p,k});
    }
    for(i=1;i<=Q;i++)
    {
        cin>>quer[i].first>>quer[i].second;
        ans[i] = INT_MAX;
    }
    vector <int> tt;
    for(i=1;i<=Q;i++)
        tt.push_back(i);
    solve(0,n/K,tt);
    for(i=1;i<=Q;i++)
        if(ans[i]==INT_MAX)cout<<-1<<endl;
        else cout<<ans[i]<<endl;
    return 0;
}
/**
5 14 5 5
0 5 9
5 12 10
0 7 7
7 12 8
4 7 10
0 12
0 5
0 7
7 12
0 13


3 14 5 5
0 5 9
5 12 10
0 7 7
7 12 8
4 7 10
0 3 4
3  2
0 12
0 5
0 7
7 12
0 13
*/

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