Submission #378582

#	Time	Username	Problem	Language	Result	Execution time	Memory
378582		joylintp	Evacuation plan (IZhO18_plan)	C++17	54 / 100	521 ms	26464 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;

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

void uni(int a, int b)
{
    group[fnd(a)] = fnd(b);
}

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);
    while (M--)
        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 (!vis[p.F] && dis[p.F] > d + p.S)
                dis[p.F] = d + p.S, pq.push(MP(-dis[p.F], p.F));
    }

    int Q;
    cin >> Q;
    if (Q > 200)
    {
        int s, t;
        while (Q--)
        {
            cin >> s >> t;
            cout << min(dis[s], dis[t]) << '\n';
        }
    }
    else
    {
        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(), greater<pair<int, pair<int, int>>>());

        while (Q--)
        {
            int s, t;
            cin >> s >> t;

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

            int ans = 0;
            for (int i = 0; fnd(s) != fnd(t) && i < ev.size(); i++)
                ans = ev[i].F, uni(ev[i].S.F, ev[i].S.S);
            cout << ans << '\n';
        }
    }

    return 0;
}

//      *   *  *****  *   *  *   *   ****  ****    ****     **    **
//     *   *  *      **  *  *   *  *      *   *  *        * *   * *
//    *****  *****  * * *  *   *  *      ****   *       *  *     *
//   *   *      *  *  **  *   *  *      *  *   *       *****    *
//  *   *  *****  *   *   ***    ****  *   *    ****     *   *****

//      *****  *****  *   *  *      *****  *   *  *****  *****
//        *   *   *  *   *  *        *    **  *    *    *   *
//       *   *   *  *****  *        *    * * *    *    *****
//   *  *   *   *    *    *        *    *  **    *    *
//  ****   *****    *    *****  *****  *   *    *    *

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:93:51: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |             for (int i = 0; fnd(s) != fnd(t) && i < ev.size(); i++)
      |                                                 ~~^~~~~~~~~~~

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