Submission #844054

#	Time	Username	Problem	Language	Result	Execution time	Memory
844054		GrandTiger1729	Evacuation plan (IZhO18_plan)	C++17	100 / 100	598 ms	36032 KiB

plan

#include <bits/stdc++.h>
using namespace std;

struct DSU
{
    vector<int> rt, sz;
    vector<int> stk;
    DSU(int n)
    {
        rt.resize(n);
        sz.resize(n, 1);
        iota(rt.begin(), rt.end(), 0);
    }
    int find(int u)
    {
        if (u == rt[u]) return u;
        return find(rt[u]);
    }
    bool same(int u, int v)
    {
        return find(u) == find(v);
    }
    void unite(int u, int v)
    {
        u = find(u), v = find(v);
        if (u == v)
        {
            stk.push_back(-1);
            return;
        }
        if (sz[u] < sz[v])
            swap(u, v);
        stk.push_back(v);
        rt[v] = u;
        sz[u] += sz[v];
    }
    void rollback()
    {
        int v = stk.back();
        stk.pop_back();
        if (v == -1) return;
        int u = rt[v];
        sz[u] -= sz[v];
        rt[v] = v;
    }
};

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n, m; cin >> n >> m;
    vector<vector<pair<int, int>>> g(n);
    for (int i = 0; i < m; i++)
    {
        int u, v, w; cin >> u >> v >> w;
        u--, v--;
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }
    vector<int> a(n);
    {
        int k; cin >> k;
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
        for (int i = 0; i < k; i++)
        {
            int x; cin >> x;
            x--;
            pq.emplace(0, x);
        }
        vector<bool> vis(n);
        while (pq.size())
        {
            auto [x, u] = pq.top();
            pq.pop();
            if (vis[u]) continue;
            vis[u] = 1;
            a[u] = x;
            for (auto &[v, w] : g[u])
            {
                pq.emplace(x + w, v);
            }
        }
    }
    int q; cin >> q;
    vector<pair<int, int>> qry(q);
    for (int i = 0; i < q; i++)
    {
        int u, v; cin >> u >> v;
        u--, v--;
        qry[i] = make_pair(u, v);
    }
    vector<int> ord(n);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int i, int j)
    {
        return a[i] < a[j];
    });
    DSU dsu(n);
    vector<int> vis(n);
    vector<int> ans(q, -1);
    function<void(vector<int> &, int, int)> solve = [&](vector<int> &qqry, int l, int r)
    {
        if (l == r - 1)
        {
            for (int i : qqry)
                ans[i] = a[ord[l]];
            return;
        }
        int mid = (l + r) / 2;
        vector<int> lqry, rqry;
        for (int i = r - 1; i >= mid; i--)
        {
            int u = ord[i];
            vis[u] = 1;
            for (auto &[v, w] : g[u])
                if (vis[v])
                    dsu.unite(u, v);
        }
        for (int j : qqry)
            if (dsu.same(qry[j].first, qry[j].second))
                rqry.push_back(j);
            else
                lqry.push_back(j);
        solve(lqry, l, mid);
        for (int i = mid; i < r; i++)
        {
            int u = ord[i];
            for (auto &[v, w] : g[u])
                if (vis[v])
                    dsu.rollback();
            vis[u] = 0;
        }
        solve(rqry, mid, r);
    };
    vector<int> qqry(q);
    iota(qqry.begin(), qqry.end(), 0);
    solve(qqry, 0, n);
    for (int i = 0; i < q; i++)
        cout << ans[i] << '\n';
    return 0;
}

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