Submission #876902

#	Time	Username	Problem	Language	Result	Execution time	Memory
876902		andrei_iorgulescu	Toll (BOI17_toll)	C++14	100 / 100	439 ms	12216 KiB

toll

#include <bits/stdc++.h>

using namespace std;

int inf = 1e9;

int k,n,m,q,t;
vector<pair<int,int>>g[50005],gr[50005];
int ans[10005];
int dist[50005];

struct ura
{
    int x,y,idx;
};

void dijkstral(int start,int leftbound)
{
    priority_queue<pair<int,int>>pq;
    pq.push({0,start});
    while (!pq.empty())
    {
        int timp = -pq.top().first,nod = pq.top().second;
        pq.pop();
        if (dist[nod] == inf)
        {
            dist[nod] = timp;
            for (auto vecin : gr[nod])
            {
                if (vecin.first >= leftbound)
                    pq.push({-(vecin.second + timp),vecin.first});
            }
        }
    }
}

void dijkstrar(int start,int rightbound)
{
    priority_queue<pair<int,int>>pq;
    pq.push({0,start});
    while (!pq.empty())
    {
        int timp = -pq.top().first,nod = pq.top().second;
        pq.pop();
        if (dist[nod] == inf)
        {
            dist[nod] = timp;
            for (auto vecin : g[nod])
            {
                if (vecin.first <= rightbound)
                    pq.push({-(vecin.second + timp),vecin.first});
            }
        }
    }
}

void solve(int l,int r,vector<ura>&v)
{
    if (l == r)
        return;
    int mij = (l + r) / 2;
    ///pentru query-uri cu st <= mij si dr > mij, sigur trec prin ceva din mij
    ///incerc fiecare din cele k valori ale mij ca fiind "punctul de trecere"
    ///valorile de mijloc sunt mij * k, mij * k + 1,...mij * k + k - 1
    vector<ura>v1,v2,s;
    for (auto it : v)
    {
        if (it.y / k <= mij)
            v1.push_back(it);
        else if (it.x / k > mij)
            v2.push_back(it);
        else
            s.push_back(it);
    }
    if (v1.size() != 0)
        solve(l,mij,v1);
    if (v2.size() != 0)
        solve(mij + 1,r,v2);
    for (int i = mij * k; i < min((mij + 1) * k,n + 1); i++)
    {
        ///i este nodul de trecere
        ///fac un dijkstra in stanga si unul in dreapta din nodul i, bounded by [l * k, r * (k + 1) - 1] si incerc sa rezolv fiecare query din s
        for (int j = l * k; j < min(n + 1,(r + 1) * k); j++)
            dist[j] = inf;
        dijkstral(i,l * k);
        dist[i] = inf;
        dijkstrar(i,(r + 1) * k - 1);
        for (auto it : s)
        {
            ans[it.idx] = min(ans[it.idx],dist[it.x] + dist[it.y]);
            //cout << "Q " << dist[it.x] << ' ' << dist[it.y] << '\n';
        }
        for (int j = l * k; j < min(n + 1,(r + 1) * k); j++)
            dist[j] = inf;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> k >> n >> m >> q;
    t = (n - 1) / k;
    for (int i = 1; i <= m; i++)
    {
        int x,y,z;
        cin >> x >> y >> z;
        g[x].push_back({y,z});
        gr[y].push_back({x,z});
    }
    vector<ura>v;
    for (int i = 1; i <= q; i++)
    {
        ura aux;
        cin >> aux.x >> aux.y;
        aux.idx = i;
        v.push_back(aux);
    }
    for (int i = 1; i <= q; i++)
        ans[i] = inf;
    solve(0,t,v);
    for (int i = 1; i <= q; i++)
    {
        if (ans[i] == inf)
            cout << -1 << '\n';
        else
            cout << ans[i] << '\n';
    }
    return 0;
}

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