Submission #1254787

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254787		_dtq_	Evacuation plan (IZhO18_plan)	C++20	10 / 100	1135 ms	589824 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 ll N = 5e5 + 9;

ll t, n, m, i, j, u[N], v[N], w[N], k[N], dis[N], q, pa[N], sz[N];

vector<pair<ll,ll>>vec[N];

void dijkstra()
{
    priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>>q;

    for( int w = 1; w <= n; w ++ ) dis[w] = 1e18;

    for( int w = 1; w <= t; w ++ ) dis[k[w]] = 0, q.push({0, k[w]});

    while(!q.empty())
    {
        ll 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<pair<ll, pair<ll,ll>>>box;

vector<ll>dsu[N];

void make_( ll x )
{
    pa[x] = x, sz[x] = 1;
    dsu[x].pb(x);
    vec[x].pb({x, 1e18});
}

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

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

    if(x == y) return;

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

    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<ll,ll>x, pair<ll,ll>y)
    {
        return x.se < y.se;
    });

    cin >> t;

    for( i = 1; i <= t; i ++ ) cin >> k[i];

    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({w[i], {u[i], v[i]}});
    }

    sort(all(box), [](pair<ll, pair<ll,ll>>x, pair<ll, pair<ll,ll>>y)
    {
        return x.fi > y.fi;
    });

    for(auto r : box) union_set(r.se.fi, r.se.se, r.fi);

    cin >> q;

    while( q -- )
    {
        ll x, y;
        cin >> x >> y;

        ll 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: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 ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:79:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |         freopen(TN ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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