Submission #1303881

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303881		chithanhnguyen	Evacuation plan (IZhO18_plan)	C++20	100 / 100	584 ms	55556 KiB

plan

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ld long double
#define pii pair<int, int>
#define fi first
#define se second
#define __builtin_popcount __builtin_popcountll
#define all(x) (x).begin(), (x).end()
#define BIT(x, i) (((x) >> (i)) & 1)
#define MASK(x) ((1ll << (x)))

#define debug(a, l, r) for (int _i = (l); _i <= (r); ++_i) cout << (a)[_i] << ' '; cout << '\n';

struct DSU{
    int n;
    vector<int> par, sz;
 
    DSU(int n) : n(n), par(n + 5), sz(n + 5) {
        iota(all(par), 0);
        fill(all(sz), 1);
    }
 
    int findSet(int x) {
        return (x == par[x] ? x : par[x] = findSet(par[x]));
    }
 
    bool unite(int x, int y) {
        x = findSet(x); y = findSet(y);
        if (x == y) return 0;
        if (sz[x] < sz[y]) swap(x, y);
 
        sz[x] += sz[y];
        par[y] = x;
 
        return 1;
    }
 
    int size(int u) {
        return sz[findSet(u)];
    }
 
    bool same(int u, int v) {
        return findSet(u) == findSet(v);
    }
};

const int MAXN = 1e5 + 5;
const int INF  = 1e18 + 5;
int n, m, q, k, dist[MAXN];
int l[MAXN], r[MAXN], res[MAXN];
pii queries[MAXN];
bitset<MAXN> mark;
vector<pii> adj[MAXN];
vector<int> sources;
int city[MAXN];

void dijkstra() {
    for (int i = 1; i <= n; ++i) dist[i] = INF;

    priority_queue<pii, vector<pii>, greater<pii>> pq;
    for (auto u : sources) {
        dist[u] = 0;
        pq.push({0, u});
    }

    while (!pq.empty()) {
        int u = pq.top().se, cost = pq.top().fi;
        pq.pop();

        if (cost > dist[u]) continue;

        for (auto &e : adj[u]) {
            int v = e.fi, w = e.se;

            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
}

void init() {
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int u, v, w; cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    cin >> k;
    for (int i = 1; i <= k; ++i) {
        int g; cin >> g;
        sources.push_back(g);
    }

    dijkstra();
    // debug(dist, 1, n);
    iota(city + 1, city + n + 1, 1);
    sort(city + 1, city + n + 1, [] (int x, int y) {
        return dist[x] < dist[y];
    });
    // debug(city, 1, n);
}

/*
void solve() {
    int q; cin >> q;
    int s, t; cin >> s >> t;

    int l = 1, r = n, ans = 1;

    while (l <= r) {
        int mid = (l + r) >> 1;
        mark.reset();
        DSU dsu(n);
        for (int i = mid; i <= n; ++i) mark[city[i]] = 1;
        for (int i = mid; i <= n; ++i) {
            int u = city[i];
            for (auto &e : adj[u]) {
                int v = e.fi;
                if (mark[v]) dsu.unite(u, v);
            }
        }

        if (dsu.same(s, t)) {
            ans = mid;
            l = mid + 1;
        } else r = mid - 1;
    }

    cout << dist[city[ans]];
}*/

void solve() {
    cin >> q;
    for (int i = 1; i <= q; ++i) {
        int s, t; cin >> s >> t;
        l[i] = 1; r[i] = n;
        queries[i] = {s, t};
    }

    vector<vector<int>> candidate(n + 5, vector<int>());
    while (true) {
        bool any = 0;
        for (int i = 1; i <= q; ++i) {
            if (l[i] <= r[i]) {
                any = 1;
                int mid = (l[i] + r[i]) >> 1;
                candidate[mid].push_back(i);
            }
        }

        if (!any) break;

        mark.reset();
        DSU dsu(n);
        for (int mid = n; mid >= 1; --mid) {
            mark[city[mid]] = 1;
            for (auto &e : adj[city[mid]]) {
                int v = e.fi;
                if (mark[v]) dsu.unite(city[mid], v);
            }

            for (int qry : candidate[mid]) {
                int s = queries[qry].fi;
                int t = queries[qry].se;

                if (dsu.same(s, t)) {
                    res[qry] = mid;
                    l[qry] = mid + 1;
                } else r[qry] = mid - 1;
            }
        }

        // Reset
        for (int i = 1; i <= n; ++i) candidate[i].clear();
    }

    for (int i = 1; i <= q; ++i) cout << dist[city[res[i]]] << '\n';
}

signed main() {
    #ifdef NCTHANH
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);

    init();
    solve();

    return 0;
}

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