Submission #378580

#	Time	Username	Problem	Language	Result	Execution time	Memory
378580		abc864197532	Evacuation plan (IZhO18_plan)	C++17	100 / 100	725 ms	105744 KiB

plan

#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define pii pair<int, int>
#define pll pair<lli, lli>
#define X first
#define Y second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define test(x) cout << #x << ' ' << x << endl
#define printv(x) {\
    for (auto a : x) cout << x << ' ';\
    cout << endl;\
}
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
const int N = 100000;

struct edge {
    int u, v, w;
};

struct query {
    int u, v, id;
};

struct Dsu {
    vector <int> dsu, sz, pt;
    vector <pii> move_dsu, move_sz;
    int n;
    Dsu (int _n) : n(_n) {
        dsu.resize(n);
        sz.assign(n, 1);
        iota(all(dsu), 0);
    }
    int Find(int x) {
        if (dsu[x] == x) return x;
        return Find(dsu[x]);
    }
    bool Union(int u, int v) {
        u = Find(u), v = Find(v);
        if (u == v) return false;
        if (sz[u] > sz[v]) swap(u, v);
        move_dsu.eb(u, dsu[u]);
        move_sz.eb(v, sz[v]);
        dsu[u] = v;
        sz[v] += sz[u];
        return true;
    }
    void addPoint() {
        pt.pb(move_dsu.size());
    }
    void rollback() {
        int t = pt.back(); pt.pop_back();
        while (move_dsu.size() > t) {
            int a, b;
            tie(a, b) = move_dsu.back(); move_dsu.pop_back();
            dsu[a] = b;
            tie(a, b) = move_sz.back(); move_sz.pop_back();
            sz[a] = b;
        }
    }
    bool same(int u, int v) {
        return Find(u) == Find(v);
    }
} dsu(N);

vector <edge> g;
vector <pii> adj[N], d;
int ans[N], dis[N];
priority_queue <pii, vector <pii>, greater<pii>> pq;

void solve(vector <query> Q, int l, int r) {
    if (Q.empty()) return;
    if (r - l == 1) {
        for (query &q : Q) ans[q.id] = l;
        return;
    }
    int m = l + r >> 1;
    dsu.addPoint();
    for (auto it = lower_bound(all(d), mp(m, -1)); it != d.end() && it->X < r; ++it) {
        int v = it->Y;
        for (pii A : adj[v]) if (dis[A.X] >= m) {
            dsu.Union(v, A.X);
        }
    }
    vector <query> tl, tr;
    for (query &q : Q) {
        if (dsu.same(q.u, q.v)) tr.pb(q);
        else tl.pb(q);
    }
    solve(tl, l, m);
    dsu.rollback();
    solve(tr, m, r);
}

void build() {
    int d, v;
    while (!pq.empty()) {
        tie(d, v) = pq.top(); pq.pop();
        if (dis[v] < d) continue;
        for (pii e : adj[v]) if (dis[e.X] > dis[v] + e.Y) {
            dis[e.X] = dis[v] + e.Y;
            pq.emplace(dis[e.X], e.X);
        }
    }
}

int main () {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m, k, q;
    cin >> n >> m;
    for (int i = 0, u, v, w; i < m; ++i) {
        cin >> u >> v >> w, --u, --v;
        adj[u].eb(v, w);
        adj[v].eb(u, w);
        g.pb({u, v, w});
    }
    for (int i = 0; i < n; ++i) dis[i] = 1 << 30;
    cin >> k;
    set <int> npp;
    while (k--) cin >> q, npp.insert(--q), dis[q] = 0, pq.emplace(dis[q], q);
    build();
    for (int i = 0; i < n; ++i) d.eb(dis[i], i);
    sort(all(d));
    cin >> q;
    vector <query> Q(q);
    for (int i = 0; i < q; ++i) cin >> Q[i].u >> Q[i].v, Q[i].u--, Q[i].v--, Q[i].id = i;
    solve(Q, 0, 1 << 30);
    for (int i = 0; i < q; ++i) cout << ans[i] << '\n';
}
/*
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 member function 'void Dsu::rollback()':
plan.cpp:56:32: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   56 |         while (move_dsu.size() > t) {
      |                ~~~~~~~~~~~~~~~~^~~
plan.cpp: In function 'void solve(std::vector<query>, int, int)':
plan.cpp:80:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   80 |     int m = l + r >> 1;
      |             ~~^~~

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