Submission #881967

#	Time	Username	Problem	Language	Result	Execution time	Memory
881967		tset	Evacuation plan (IZhO18_plan)	C++17	100 / 100	690 ms	121476 KiB

plan

#include<bits/stdc++.h>

using namespace std;

#define int long long
const int INF = LLONG_MAX/6;

vector<int> parentUF;
vector<vector<int>> voisinDeArbre;
vector<int> pereDe;
vector<vector<int>> filsDe;
vector<int > profNde;

int getLeader(int nde)
{
    if(parentUF[nde] == nde)
        return nde;
    parentUF[nde] = getLeader(parentUF[nde]);
    return parentUF[nde];
}

void mergeUF(int u, int v)
{
    int leaderU = getLeader(u);
    int leaderV = getLeader(v);
    if(leaderU != leaderV)
        parentUF[leaderU] = leaderV;
}

void dfsRoot(int nde, int ancestor, int prof)
{
    pereDe[nde] = ancestor;
    profNde[nde] = prof;
    for(int iV : voisinDeArbre[nde])
    {
        if(iV != ancestor)
        {
            filsDe[nde].push_back(iV);
            dfsRoot(iV, nde, prof+1);
        }
    }
}

signed main()
{
    int nbNdes, nbArcs;
    scanf("%lld%lld", &nbNdes, &nbArcs);
    vector<vector<pair<int, int>>> voisinDe(nbNdes);
    vector<pair<int, int>> arcs;
    vector<tuple<int, int, int>> arcsSorted;
    for(int iA  = 0; iA< nbArcs; iA++)
    {
        int u, v, pond;
        scanf("%lld%lld%lld", &u, &v, &pond);
        u--;v--;
        voisinDe[u].push_back({pond, v});
        voisinDe[v].push_back({pond, u});
        arcs.push_back({u, v});
    }
    int nbSpe;
    scanf("%lld", &nbSpe);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    for(int iSpe = 0; iSpe < nbSpe; iSpe++)
    {
        int u;
        scanf("%lld", &u);
        u--;
        pq.push({0, u});
    }
    vector<int> pondNde(nbNdes, INF);
    while (!pq.empty())
    {
        pair<int, int> pqTop = pq.top();
        pq.pop();
        int pondAct = pqTop.first;
        int ndeAct = pqTop.second;
        if(pondNde[ndeAct] == INF)
        {
            pondNde[ndeAct] = pondAct;
            for(pair<int, int> iV : voisinDe[ndeAct])
            {
                pq.push({pondAct + iV.first, iV.second});
            }
        }
    }
    for(int iArc = 0; iArc< nbArcs; iArc++)
    {
        int u = arcs[iArc].first, v = arcs[iArc].second;
        int pondArc = min(pondNde[u], pondNde[v]);
        arcsSorted.push_back({-pondArc, u, v});
    }
    sort(arcsSorted.begin(), arcsSorted.end());
    parentUF.resize(nbNdes);
    for(int iNde = 0; iNde< nbNdes; iNde++)
    {
        parentUF[iNde] = iNde;
    }
    voisinDeArbre.resize(nbNdes);

    for(tuple<int, int, int> arcAct: arcsSorted)
    {
        int u = get<1>(arcAct);
        int v = get<2>(arcAct);
        if(getLeader(u) != getLeader(v))
        {
            mergeUF(u, v);
            voisinDeArbre[u].push_back(v);
            voisinDeArbre[v].push_back(u);
        }
    }
    pereDe.resize(nbNdes);
    filsDe.resize(nbNdes);
    profNde.resize(nbNdes);
    int root = 0;
    dfsRoot(root, root, 0);

    vector<vector<int>> goUpValue(nbNdes, vector<int>(20));
    vector<vector<int>> goUpCrtq(nbNdes, vector<int>(20));

    for(int iNde = 0; iNde< nbNdes; iNde++)
    {
        goUpValue[iNde][0] = pereDe[iNde];
        goUpCrtq[iNde][0] = min(pondNde[iNde], pondNde[pereDe[iNde]]);
    }
    for(int powerTwo = 1; powerTwo< 20; powerTwo++)
    {
        for(int iNde = 0; iNde < nbNdes; iNde++)
        {
            goUpValue[iNde][powerTwo] = goUpValue[goUpValue[iNde][powerTwo-1]][powerTwo-1];
            goUpCrtq[iNde][powerTwo] = min(goUpCrtq[iNde][powerTwo-1], goUpCrtq[goUpValue[iNde][powerTwo-1]][powerTwo-1]);
        }
    }

    int nbQueries;
    scanf("%lld", &nbQueries);

    for(int iQ =0; iQ< nbQueries; iQ++)
    {
        int u, v;
        scanf("%lld%lld", &u, &v);
        u--;
        v--;
        int minCtrqWh = min(pondNde[u], pondNde[v]);
        if(profNde[u]>profNde[v])
        {
            int tmp = u;
            u = v;
            v = tmp;
        }
        for(int powerTwo = 19; powerTwo>=0; powerTwo--)
        {
            if(profNde[v] - (1 << powerTwo) >= profNde[u])
            {
                minCtrqWh = min(minCtrqWh, goUpCrtq[v][powerTwo]);
                v = goUpValue[v][powerTwo];
            }
        }
        for(int powerTwo = 19; powerTwo>=0; powerTwo--)
        {
            if(goUpValue[u][powerTwo] != goUpValue[v][powerTwo])
            {
                minCtrqWh = min(minCtrqWh, goUpCrtq[u][powerTwo]);
                u = goUpValue[u][powerTwo];

                minCtrqWh = min(minCtrqWh, goUpCrtq[v][powerTwo]);
                v = goUpValue[v][powerTwo];
            }
        }
        if(u != v)
        {
            minCtrqWh = min(minCtrqWh, goUpCrtq[u][0]);
        }
        printf("%lld\n", minCtrqWh);
    }

}

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:47:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |     scanf("%lld%lld", &nbNdes, &nbArcs);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:54:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         scanf("%lld%lld%lld", &u, &v, &pond);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |     scanf("%lld", &nbSpe);
      |     ~~~~~^~~~~~~~~~~~~~~~
plan.cpp:67:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |         scanf("%lld", &u);
      |         ~~~~~^~~~~~~~~~~~
plan.cpp:136:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  136 |     scanf("%lld", &nbQueries);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~
plan.cpp:141:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  141 |         scanf("%lld%lld", &u, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 12 / 12
• Subtask 4: 19 / 19
• Subtask 5: 46 / 46