Submission #379325

#	Time	Username	Problem	Language	Result	Execution time	Memory
379325		joylintp	Evacuation plan (IZhO18_plan)	C++17	100 / 100	828 ms	59080 KiB

plan

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

//#pragma gcc optimize("Ofast,unroll-loops")
//#pragma gcc target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma,abm,mmx,popcnt,tune=native")
//#define int long long
//#define double long double
#define MP make_pair
#define F first
#define S second
#define MOD 1000000007

vector<int> group, ans;
vector<set<int>> qry;

int fnd(int a)
{
    if (a == group[a])
        return a;
    else
        return group[a] = fnd(group[a]);
}

void uni(int a, int b, int w)
{
    int x = fnd(a), y = fnd(b);
    if (x != y)
    {
        if (qry[x].size() > qry[y].size())
            swap(x, y);

        group[x] = y;
        for (int i : qry[x])
            if (qry[y].count(i))
                ans[i] = w, qry[y].erase(i);
            else
                qry[y].insert(i);
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int N, M;
    cin >> N >> M;

    int a, b, w;
    vector<vector<pair<int, int>>> edge(N + 1);
    for (int i = 0; i < M; i++)
        cin >> a >> b >> w, edge[a].push_back(MP(b, w)), edge[b].push_back(MP(a, w));

    int k, g;
    vector<int> dis(N + 1, 2e9);
    priority_queue<pair<int, int>> pq;
    cin >> k;
    while (k--)
        cin >> g, dis[g] = 0, pq.push(MP(0, g));

    vector<bool> vis(N + 1);
    while (!pq.empty())
    {
        int d = -pq.top().F, u = pq.top().S;
        pq.pop();

        if (vis[u])
            continue;

        vis[u] = true;
        for (auto p : edge[u])
            if (dis[p.F] > d + p.S)
                dis[p.F] = d + p.S, pq.push(MP(-dis[p.F], p.F));
    }

    group.resize(N + 1);
    for (int i = 1; i <= N; i++)
        group[i] = i;

    int Q, s, t;
    cin >> Q, ans.resize(Q);
    qry.resize(N + 1);
    for (int i = 0; i < Q; i++)
        cin >> s >> t, qry[s].insert(i), qry[t].insert(i);

    vector<pair<int, pair<int, int>>> ev;
    for (int i = 1; i <= N; i++)
        for (auto p : edge[i])
            if (i < p.F)
                ev.push_back(MP(min(dis[i], dis[p.F]), MP(i, p.F)));
    sort(ev.begin(), ev.end()), reverse(ev.begin(), ev.end());

    for (auto p : ev)
        uni(p.S.F, p.S.S, p.F);

    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