Submission #683125

#	Time	Username	Problem	Language	Result	Execution time	Memory
683125		opPO	Evacuation plan (IZhO18_plan)	C++17	100 / 100	503 ms	55824 KiB

plan

#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>

using namespace std;

#define int long long
#define f first
#define s second
#define pb push_back
#define ld long double
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define vec vector

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
const ld eps = 1e-6;
const int mod = 998244353;
const int oo = 2e9;
const ll OO = 2e18;
const int N = 1e5 + 10;
int n, m, k, q, p[N];
vec<pii> g[N], changes[N];
vec<int> sets[N];
bool used[N];

void init_dsu()
{
    for (int i = 0; i < N; i++)
    {
        p[i] = i;
        sets[i].pb(i);
    }
}

int get(int v)
{
    if (p[v] == v) return v;
    return p[v] = get(p[v]);
}

void merge(int u, int v, int time)
{
    int x = get(u), y = get(v);
    if (x == y) return;
    if (sz(sets[x]) > sz(sets[y])) swap(x, y);
    for (int &V : sets[x])
    {
        changes[V].pb({time, y});
        sets[y].pb(V);
    }
    p[x] = y;
    sets[x].clear();
}

void solve()
{
    init_dsu();
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].pb({v, w});
        g[v].pb({u, w});
    }
    cin >> k;
    vec<int> dist(n + 1, OO);
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    for (int i = 0; i < k; i++)
    {
        int v;
        cin >> v;
        dist[v] = 0;
        pq.push({0, v});
    }
    while (!pq.empty())
    {
        pii cur = pq.top(); pq.pop();
        int dst = cur.f, v = cur.s;
        if (dst > dist[v]) continue;
        for (auto &to : g[v])
        {
            if (dst + to.s < dist[to.f])
            {
                dist[to.f] = dst + to.s;
                pq.push({dist[to.f], to.f});
            }
        }
    }
    vec<pii> events;
    for (int i = 1; i <= n; i++) events.pb({dist[i], i});
    sort(rall(events));
    for (int i = 1; i <= n; i++) changes[i].pb({OO, i});
    for (int i = 0; i < n; i++)
    {
        int v = events[i].s;
        int t = events[i].f;
        used[v] = true;
        for (auto &to : g[v])
        {
            int u = to.f;
            if (!used[u]) continue;
            merge(u, v, t);
        }
    }
    cin >> q;
    while (q--)
    {
        int s, t;
        cin >> s >> t;
        int ans = 0;
        for (auto &ch_s : changes[s])
        {
            for (auto &ch_t : changes[t])
            {
                if (ch_s.s == ch_t.s) ans = max(ans, min(ch_s.f, ch_t.f));
            }
        }
        cout << ans << "\n";
    }
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    solve();
    return 0;
}

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