Submission #1254801

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254801		_dtq_	Evacuation plan (IZhO18_plan)	C++17	100 / 100	300 ms	31784 KiB

plan

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define sz(x) (ll)(x.size())
#define all(v) v.begin(), v.end()
#define se second
#define fi first
using namespace std;

const int N = 5e5 + 9;

const ll M = 1e5 + 9;

int t, n, m, i, j, u[N], v[N], w[N], dis[M], q_, pa[M];

vector<pair<int,int>>vec[M];
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>>q;

void dijkstra()
{
    while(!q.empty())
    {
        int x = q.top().se, kc = q.top().fi;

        q.pop();

        if(kc != dis[x]) continue;

        for(auto y : vec[x])
            if(dis[y.fi] > dis[x] + y.se)
            {
                dis[y.fi] = dis[x] + y.se;
                q.push({dis[y.fi], y.fi});
            }
    }
}

vector<int>box;

vector<int>dsu[M];

void make_( int x )
{
    pa[x] = x;
    dsu[x].pb(x);
    vec[x].pb({x, 1e9});
}

int find_ ( int x )
{
    return pa[x] == x ? x : pa[x] = find_(pa[x]);
}

void union_set( int x, int y, int z )
{
    x = find_(x), y = find_(y);

    if(x == y) return;

    if(sz(dsu[x]) <= sz(dsu[y]))
        swap(x, y);

        pa[y] = x;

    for(auto x_ : dsu[y])
    {
        dsu[x].pb(x_);

        vec[x_].pb({x, z});
    }
}
int main()
{
#define TN ""
    if(fopen(TN ".inp", "r"))
    {
        freopen(TN ".inp", "r", stdin);
        freopen(TN ".out", "w", stdout);
    }
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> m;

    for( i = 1; i <= m; i ++ )
    {
        cin >> u[i] >> v[i] >> w[i];

        vec[u[i]].pb({v[i], w[i]});

        vec[v[i]].pb({u[i], w[i]});
    }
    for( i = 1; i <= n; i ++ ) sort(all(vec[i]), [](pair<int,int>x, pair<int,int>y)
    {
        return x.se < y.se;
    });

    cin >> t;
    for( i = 1; i <= n; i ++ ) dis[i] = 1e9;


    for( i = 1; i <= t; i ++ )
    {
        int x; cin >> x;
        dis[x] = 0;
        q.push({0, x});
    }

    dijkstra();

    for( i = 1; i <= n; i ++ ) vec[i].clear(), make_(i);

    for( i = 1; i <= m; i ++ )
    {
        w[i] = min(dis[u[i]], dis[v[i]]);
        box.pb(i);
    }

    sort(all(box), [](int x, int y)
    {
        return w[x] > w[y];
    });

    for(auto r : box) union_set(u[r], v[r], w[r]);

    cin >> q_;

    while( q_ -- )
    {
        int x, y;
        cin >> x >> y;

        int maxn = 0;

        for( auto u : vec[x] )
            for( auto v : vec[y] )
            {
                if(u.fi == v.fi)
                    maxn = max(maxn, min(u.se, v.se));
            }

        cout << maxn << "\n";
    }


    return 0;
}
/*
9 12
1 9 4
1 2 5
2 3 7
2 4 3
4 3 6
3 6 4
8 7 10
6 7 5
5 8 1
9 5 7
5 4 12
6 8 2
2
4 7
5
1 6
5 3
4 8
5 8
1 5
*/

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:77:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |         freopen(TN ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:78:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |         freopen(TN ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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