제출 #51747

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
51747		hugo_pm	Evacuation plan (IZhO18_plan)	C++14	100 / 100	1718 ms	49628 KiB

plan

#include <bits/stdc++.h>
#define ford(i,n) for (int i = n-1; i >= 0; i--)
#pragma GCC diagnostic ignored "-Wunused-result"
using namespace std;

typedef pair<int, int> pii;
typedef pair<int, pii> Lien;
typedef priority_queue<pii, vector<pii>, greater<pii>> MinHeap;
const int INF = (INT_MAX - 3) / 2;
const int borneMax = (int)(1e5) + 5;

int nbNod, nbArc, nbCen, nbReq;
vector<pii> adj[borneMax];
vector<pii> mst[borneMax];
vector<int> cen;
vector<int> valeur(borneMax, INF);
bool exemple = false;
int pere[borneMax];
int depth[borneMax];
int ancetre[borneMax][18];
int minpoids[borneMax][18];

void lireEntree()
{
    scanf("%d%d", &nbNod, &nbArc);
    for (int ind = 0; ind < nbArc; ++ind)
    {
        int nod1, nod2, poids;
        scanf("%d%d%d", &nod1, &nod2, &poids);
        adj[nod1].push_back({nod2, poids});
        adj[nod2].push_back({nod1, poids});
    }

    scanf("%d", &nbCen);
    cen.resize(nbCen);
    for (int ind = 0; ind < nbCen; ++ind)
    {
        scanf("%d", &cen[ind]);
    }
}

void preparer()
{
    MinHeap dij;
    for (int nod : cen)
    {
        dij.push({nod, 0});
        valeur[nod] = 0;
    }
    while (! dij.empty())
    {
        auto e = dij.top();
        int nod = e.first, dis = e.second;
        dij.pop();
        if (dis > valeur[nod]) continue;
        for (pii obj : adj[nod])
        {
            int voisin = obj.first, poids = obj.second;
            if (dis + poids < valeur[voisin])
            {
                valeur[voisin] = dis + poids;
                dij.push({voisin, dis + poids});
            }
        }
    }
}

// Structure union-find optimisée en temps
// Complexité des opérations : O(log N)
class UnionFind
{
    public:
        UnionFind(int sz);
        int findRepr(int elem);
        bool unir(int a, int b);

    private:
        int taille;
        vector<int> repr, couverts;
};

UnionFind::UnionFind(int sz) : taille(sz), repr(sz+1), couverts(sz+1)
{
    for (int ind = 0; ind <= taille; ++ind)
    {
        repr[ind] = ind;
        couverts[ind] = 1;
    }
}

int UnionFind::findRepr(int elem)
{
    stack<int> vus; // (!) Consommation mémoire pour optimisation temporelle
    while (elem != repr[elem])
    {
        vus.push(elem);
        elem = repr[elem];
    }

    // Compression de chemin
    while (! vus.empty())
    {
        repr[vus.top()] = elem;
        vus.pop();
    }

    return elem;
}

// Retourne vrai si les deux élements ont été unis (n'étaient pas dans la même composante)
bool UnionFind::unir(int a, int b)
{
    a = findRepr(a);
    b = findRepr(b);
    if (a == b)
        return false;

    // Equilibrage : on insère le petit arbre dans le grand
    if (couverts[a] > couverts[b])
        swap(a, b);
    repr[a] = b;
    couverts[b] += couverts[a];

    return true;
}

void kruskal()
{
    vector<Lien> arcs;
    for (int ind = 1; ind <= nbNod; ++ind)
    {
        for (auto voiraw : adj[ind])
        {
            int voisin = voiraw.first;
            if (ind < voisin) arcs.push_back({-min(valeur[ind], valeur[voisin]), {ind, voisin}});
        }
    }
    sort(arcs.begin(), arcs.end());
    UnionFind uf(nbNod + 1);
    for (auto arc : arcs)
    {
        int poids = -arc.first, nod1 = arc.second.first, nod2 = arc.second.second;
        if (uf.unir(nod1, nod2))
        {
            mst[nod1].push_back({nod2, poids});
            mst[nod2].push_back({nod1, poids});
        }
    }
}

void genInfos()
{
    fill_n(&minpoids[0][0], borneMax * 18, INF);
    pere[1] = depth[1] = 0;
    stack<int> dfs;
    dfs.push(1);
    while (! dfs.empty())
    {
        int nod = dfs.top(); dfs.pop();
        for (pii vo : mst[nod]) if (vo.first != pere[nod])
        {
            pere[vo.first] = ancetre[vo.first][0] = nod;
            minpoids[vo.first][0] = vo.second;
            depth[vo.first] = depth[nod] + 1;
            dfs.push(vo.first);
        }
    }
    dfs.push(1);
    while (! dfs.empty())
    {
        int nod = dfs.top(); dfs.pop();
        for (int k = 1; (1 << k) <= depth[nod]; ++k)
        {
            ancetre[nod][k] = ancetre[ancetre[nod][k-1]][k-1];
            minpoids[nod][k] = min(minpoids[nod][k-1], minpoids[ancetre[nod][k-1]][k-1]);
        }
        for (pii vo : mst[nod]) if (vo.first != pere[nod])
        {
            dfs.push(vo.first);
        }
    }
}

int LCA(int u, int v)
{
    if (depth[u] > depth[v]) swap(u, v); // v plus bas que u
    ford(k, 18)
    {
        if (depth[v] - depth[u] >= (1 << k)) v = ancetre[v][k];
    }
    if (u == v) return u;
    ford(k, 18)
    {
        if (depth[u] < (1 << k)) continue;
        if (ancetre[u][k] != ancetre[v][k])
        {
            u = ancetre[u][k];
            v = ancetre[v][k];
        }
    }
    return pere[u];
}

int minTo(int nod, int par)
{
    int m = INF;
    ford(k, 18) if (depth[nod] - depth[par] >= (1 << k))
    {
        m = min(m, minpoids[nod][k]);
        nod = ancetre[nod][k];
    }
    return m;
}

int main()
{
    lireEntree();
    preparer();
    kruskal();
    genInfos();
    scanf("%d", &nbReq);
    for (int ind = 0; ind < nbReq; ++ind)
    {
        int nod1, nod2;
        scanf("%d%d", &nod1, &nod2);
        int lc = LCA(nod1, nod2);
        int m = min(minTo(nod1, lc), minTo(nod2, lc));
        printf("%d\n", m);
    }
}

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