Submission #492360

#	Time	Username	Problem	Language	Result	Execution time	Memory
492360		Mike4235	Evacuation plan (IZhO18_plan)	C++17	100 / 100	580 ms	57012 KiB

plan

/*#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")*/
 
#include <bits/stdc++.h>
  
#define for1(i,a,b) for (int i = a; i <= b; i++)
#define for2(i,a,b) for (int i = a; i >= b; i--)
#define int long long

#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pb push_back
 
/*
__builtin_popcountll(x) : Number of 1-bit
__builtin_ctzll(x) : Number of trailing 0
*/
 
const long double PI = 3.1415926535897932384626433832795;
const int INF = 1000000000000000000;
const int MOD = 1000000007;
const int MOD2 = 1000000009;
const long double EPS = 1e-6;

using namespace std;

int n, m, k, q;
int d[100005], par[100005], sz[100005], res[100005];
set<int> se[100005];
priority_queue<pii, vector<pii>, greater<pii>> pq;
vector<pii> v;
vector<pii> g[100005];

int find_set(int v) {
    return (v == par[v] ? v : par[v] = find_set(par[v]));
}

void join_sets(int a, int b, int w) {
    a = find_set(a);
    b = find_set(b);

    if (a == b) return;

    if (sz[a] < sz[b]) swap(a, b);
    par[b] = a;
    sz[a] += sz[b];

    if (sz(se[a]) < sz(se[b])) swap(se[a], se[b]);
    for (auto x : se[b]) {
        if (se[a].find(x) != se[a].end()) {
            res[x] = w;
            se[a].erase(x);
        }
        else se[a].insert(x);
    }
}

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

    // freopen("cf.inp", "r", stdin);
    // freopen("cf.out", "w", stdout);

    cin >> n >> m;
    for1(i,1,m) {
        int a, b, w;
        cin >> a >> b >> w;
        g[a].push_back({b, w});
        g[b].push_back({a, w});
    }

    for1(i,1,n) {
        par[i] = i;
        sz[i] = 1;
        d[i] = INF;
    }

    cin >> k;
    while (k--) {
        int a;
        cin >> a;
        d[a] = 0;
        pq.push({0, a});
    }

    while (!pq.empty()) {
        int u = pq.top().second, d_u = pq.top().first;
        pq.pop();

        if (d[u] != d_u) continue;

        for (auto e : g[u]) {
            int v = e.first, w = e.second;
            if (d[u] + w < d[v]) {
                d[v] = d[u] + w;
                pq.push({d[v], v});
            }
        }
    }

    for1(i,1,n) v.push_back({d[i], i});
    sort(v.begin(), v.end(), greater<pii>());

    cin >> q;
    for1(i,1,q) {
        int s, t;
        cin >> s >> t;
        se[s].insert(i);
        se[t].insert(i);
    }

    for (auto p : v) {
        int u = p.second, w = p.first;
        for (auto e : g[u]) {
            int v = e.first;
            if (d[v] >= w) join_sets(u, v, w);
        }
    }

    for1(i,1,q) cout << res[i] << "\n";
    
}

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