Submission #867681

#	Time	Username	Problem	Language	Result	Execution time	Memory
867681		sleepntsheep	Evacuation plan (IZhO18_plan)	C++17	100 / 100	363 ms	36572 KiB

plan

#include <iostream>
#include <cassert>
#include <queue>
#include <cstring>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#include <utility>
#include <array>

using namespace std;
#define ALL(x) x.begin(), x.end()
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false);
using ll = long long;
#define N 100005

int c, n, m, k, Q, d[N], P[N], J[N], L[N], p[N], M[N], Y[N];
vector<tuple<int, int, int>> el;
vector<pair<int, int>> g[N];
priority_queue<pair<int, int>> q;
int fnd(int u) { return p[u] < 0 ? u : fnd(p[u]); }
int unn(int x, int y) { x=fnd(x),y=fnd(y); if(x==y)return 0;if(-p[x]>-p[y]) swap(x,y); p[y]+=p[x];p[x]=y;return 1;}

void dfs(int u)
{
    for (auto [w, v] : g[u])
    {
        if (v == P[u]) continue;
        P[v] = u, L[v] = L[u] + 1, Y[v] = w;
        if (L[u] - L[J[u]] == L[J[u]] - L[J[J[u]]]) J[v] = J[J[u]], M[v] = min({w, M[u], M[J[u]]});
        else J[v] = u, M[v] = w;
        dfs(v);
    }
}

int evacuate(int u, int v)
{
    if (L[u] < L[v]) return evacuate(v, u);
    int z = 2e9;
    for (; L[u] > L[v]; )
    {
        if (L[J[u]] >= L[v]) z = min(z, M[u]), u = J[u];
        else z = min(z, Y[u]), u = P[u];
    }
    assert(L[u] == L[v]);
    for (; u != v; )
    {
        if (J[u] != J[v]) z = min(z, min(M[u], M[v])), u = J[u], v = J[v];
        else z = min(z, min(Y[u], Y[v])), u = P[u], v = P[v];
    }
    return z;
}

int main()
{
    memset(d, 63, sizeof d); memset(p, -1, sizeof p);
    ShinLena;
    cin >> n >> m;
    el.resize(m);
    for (auto &[w, u, v]: el) cin >> u >> v >> w, g[v].emplace_back(w, u), g[u].emplace_back(w, v);
    for (int x = (cin >> k, 0); k--;) cin >> x, q.emplace(d[x] = 0, x);
    for (; q.size(); )
    {
        auto [c, u] = q.top(); q.pop();
        for (auto [w, v] : g[u]) if (w - c < d[v]) q.emplace(-(d[v] = w-c), v);
    }
    for (auto &[w, u, v] : el) w = -min(d[u], d[v]);
    for (int i = 1; i <= n; ++i) g[i].clear();
    sort(ALL(el));
    for (auto &[w, u, v] : el)
    {
        if (unn(u, v))
        {
            g[u].emplace_back(-w, v), g[v].emplace_back(-w, u);
            if (++c == n - 1) break;
        }
    }
    J[1] = P[1] = 1; M[1] = 1e9; dfs(1);
    cin >> Q;
    for (int u, v; Q--;) cin >> u >> v, cout << evacuate(u, v) << '\n';
    return 0;
}

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