Submission #844045

#	Time	Username	Problem	Language	Result	Execution time	Memory
844045		GrandTiger1729	Evacuation plan (IZhO18_plan)	C++17	41 / 100	4083 ms	35836 KiB

plan

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

struct DSU
{
    vector<int> rt;
    DSU(int n)
    {
        rt.resize(n);
        iota(rt.begin(), rt.end(), 0);
    }
    int find(int u)
    {
        if (u == rt[u]) return u;
        return rt[u] = 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);
        rt[u] = v;
    }
};

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    // freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);
    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);
            }
        }
    }
    // for (int i = 0; i < n; i++)
    //     cerr << a[i] << " \n"[i == n - 1];
    // cerr << endl;
    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);
    for (int &u : ord)
    {
        vis[u] = 1;
        for (auto &[v, w] : g[u])
            if (vis[v])
                dsu.unite(u, v);
        for (int i = 0; i < q; i++)
            if (ans[i] == -1 && dsu.same(qry[i].first, qry[i].second))
                ans[i] = a[u];
    }
    for (int i = 0; i < q; i++)
        cout << ans[i] << '\n';
    return 0;
}

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