Submission #890661

#TimeUsernameProblemLanguageResultExecution timeMemory
890661aykhnEvacuation plan (IZhO18_plan)C++17
0 / 100
349 ms62404 KiB
#include <bits/stdc++.h>
 
// author : aykhn
 
using namespace std;
typedef long long ll;
 
#define pb push_back
#define ins insert
#define mpr make_pair
#define all(v) v.begin(), v.end()
#define bpc __builtin_popcountll
#define pii pair<ll, ll>
#define pll pair<ll, ll>
#define fi first
#define se second
#define int ll
#define infll 0x3F3F3F3F3F3F3F3F
#define inf 0x3F3F3F3F

struct DSU
{
    vector<int> e;
    void init(int n)
    {
        e.assign(n + 1, -1);
    }
    int get(int x)
    {
        if (e[x] < 0) return x;
        return e[x] = get(e[x]);
    }
    int tog(int x, int y)
    {
        return get(x) == get(y);
    }
    int unite(int x, int y)
    {
        x = get(x);
        y = get(y);
        if (x == y) return 0;
        if (e[x] > e[y]) swap(x, y);
        e[x] += e[y];
        e[y] = x;
        return 1;
    }
};

const int MXN = 5e5 + 5;

int n, m;
vector<array<int, 2>> adj[MXN];
int dist[MXN];
int l[MXN], r[MXN];
priority_queue<array<int, 2>, vector<array<int, 2>>, greater<array<int, 2>>> pq;

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) dist[i] = inf;
    vector<array<int, 3>> e(m);
    for (int i = 0; i < m; i++)
    {
        cin >> e[i][1] >> e[i][2] >> e[i][0];
        adj[e[i][1]].pb({e[i][2], e[i][0]});
        adj[e[i][2]].pb({e[i][1], e[i][0]});
    }
    int k;
    cin >> k;
    while (k--)
    {
        int x;
        cin >> x;
        dist[x] = 0;
        pq.push({0, x});
    }
    while (!pq.empty())
    {
        array<int, 2> from = pq.top();
        pq.pop();
        if (from[0] > dist[from[1]]) continue;
        for (array<int, 2> v : adj[from[1]])
        {
            if (dist[v[0]] > from[0] + v[1])
            {
                dist[v[0]] = from[0] + v[1];
                pq.push({dist[v[0]], v[0]});
            }
        }
    }
    for (int i = 0; i < m; i++) e[i][0] = min(dist[e[i][1]], dist[e[i][2]]);
    sort(e.rbegin(), e.rend());
    int Q;
    cin >> Q;
    assert(Q == 1);
    int s, t;
    cin >> s >> t;
    int l = 0;
    int r = m + 1;
    while (l < r)
    {
        DSU dsu;
        dsu.init(n);
        int mid = (l + r + 1) >> 1;
        for (int i = 0; i < e.size() && e[i][0] >= mid; i++) dsu.unite(e[i][1], e[i][2]);
        if (dsu.tog(s, t)) l = mid;
        else r = mid - 1;
    }
    cout << l << '\n';


    
    // vector<array<int, 2>> q(Q);
    // for (int i = 0; i < q.size(); i++) cin >> q[i][0] >> q[i][1], l[i] = 0, r[i] = m + 1;
    // for (int lg = 0; lg < 21; lg++)
    // {
    //     DSU dsu;
    //     dsu.init(n);
    //     vector<array<int, 2>> b;
    //     for (int i = 0; i < q.size(); i++) b.pb({(l[i] + r[i]) >> 1, i});
    //     sort(b.rbegin(), b.rend());
    //     int j = 0;
    //     for (int i = 0; i < b.size(); i++)
    //     {
    //         int id = b[i][1];
    //         while (j < e.size() && e[j][0] >= b[i][0]) dsu.unite(e[j][1], e[j][2]), j++;
    //         if (dsu.tog(q[id][0], q[id][1])) l[id] = b[i][0];
    //         else r[id] = b[i][0];
    //     }
    // }
    // for (int i = 0; i < q.size(); i++) cout << l[i] << '\n';
}

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:107:27: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |         for (int i = 0; i < e.size() && e[i][0] >= mid; i++) dsu.unite(e[i][1], e[i][2]);
      |                         ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...