Submission #1182634

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182634		GGOSHAB	Bridges (APIO19_bridges)	C++20	14 / 100	1456 ms	41992 KiB

bridges

#ifdef ONPC
    #define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>

#ifndef ONPC
    #pragma GCC target("avx")
    #pragma GCC target("popcnt")

    #define cerr if (false) cerr
#endif

using namespace std;

#define all(v) begin(v), end(v)
#define watch(x) cerr << #x << ": " << x << endl;

typedef long long ll;
typedef unsigned long long ull;

typedef pair<int, int> Pint;
typedef pair<ll, ll> Pll;

mt19937_64 gen64(chrono::steady_clock::now().time_since_epoch().count());
inline ll rnd(ll l = LLONG_MIN, ll r = LLONG_MAX) {
    return uniform_int_distribution<ll>(l, r)(gen64);
}

template<class T>
bool umin(T &a, const T &b) {
    return (a > b ? a = b, true : false);
}

template<class T>
bool umax(T &a, const T &b) {
    return (a < b ? a = b, true : false);
}

const int mod = 998244353;

ll mult(ll a, ll b) {
    return (a * b) % mod;
}

template<class T>
void add(T &a, const T &b) {
    a = (a + b) % mod;
}

const int inf = int(1e9) + 10;
const ll INF = ll(1e18) + 10;

const int maxn = 1e5 + 10, maxc = 10;
constexpr int sqn = sqrt(maxn) + 10;

struct DSU {
    vector<int> p, w;
    DSU(int n) : p(n + 1), w(n + 1, 1) {
        iota(all(p), 0);
    }
    int leader(int v) {
        return (p[v] == v ? v : p[v] = leader(p[v]));
    }
    bool unite(int v, int u) {
        v = leader(v), u = leader(u);
        if (v == u) {
            return false;
        }
        if (w[v] < w[u]) {
            swap(v, u);
        }
        p[u] = v;
        w[v] += w[u];
        return true;
    }
    void clear() {
        fill(all(w), 1);
        iota(all(p), 0);
    }
};

struct edge {
    int v = 0, u = 0, w = 0, t = 0;
};

bool operator<(edge a, edge b) {
    return make_tuple(-a.w, a.t, a.v, a.u) < make_tuple(-b.w, b.t, b.v, b.u);
}

struct query {
    int v = 0, w = 0, t = 0, tp = 0;
};

void solve() {
    int n, m;
    cin >> n >> m;
    vector<edge> e(m);
    for (auto &[v, u, w, t] : e) {
        cin >> v >> u >> w; t = -1; v--, u--;
    }

    int q;
    cin >> q;
    vector<query> qrs(q);
    for (int i = 0; i < q; ++i) {
        auto &[v, w, t, tp] = qrs[i];
        cin >> tp >> v >> w; v--;
        t = i;
    }

    set<edge> s;
    for (auto &r : e) {
        s.insert(r);
    }

    vector<vector<Pint>> g(n);
    vector<bool> used(n);
    vector<int> ans(q);
    vector<vector<edge>> upd(m);
    for (int i = 0; i < m; ++i) {
        upd[i].push_back(e[i]);
    }
    for (int bl = 0; bl * sqn < q; ++bl) {
        int l = bl * sqn, r = min((bl + 1) * sqn, q);
        vector<pair<edge, int>> buffer;
        map<int, vector<int>> mp;
        for (int i = l; i < r; ++i) {
            if (qrs[i].tp == 1) {
                int id = qrs[i].v;
                if (s.count(e[id])) {
                    s.erase(e[id]);
                }
                e[id].w = qrs[i].w;
                e[id].t = i;
                upd[id].push_back(e[id]);
                buffer.push_back({e[id], id});
            } else {
                mp[-qrs[i].w].push_back(i);
            }
        }

        DSU dsu(n);
        auto it = s.begin();
        for (auto &[_w, qr] : mp) {
            int w = _w * -1;
            while (it != s.end() && it->w >= w) {
                dsu.unite(it->v, it->u);
                it++;
            }
            for (auto &id : qr) {
                auto [v, w, t, tp] = qrs[id];
                for (auto [_r, i] : buffer) {
                    auto rit = upper_bound(all(upd[i]), edge{0, 0, 0, t}, [](edge a, edge b) { return a.t < b.t; });
                    if (rit == upd[i].begin()) continue;
                    auto r = *prev(rit);
                    if (r.t <= t) {
                        int v = dsu.leader(r.v), u = dsu.leader(r.u);
                        if (v != u) {
                            g[v].push_back({u, r.w});
                            g[u].push_back({v, r.w});
                        }
                    }
                }

                queue<int> q;
                q.push(dsu.leader(v));
                used[dsu.leader(v)] = true;
                while (!q.empty()) {
                    int v = q.front(); q.pop();
                    ans[t] += dsu.w[v];
                    for (auto [u, uw] : g[v]) {
                        if (w <= uw && !used[u]) {
                            used[u] = true;
                            q.push(u);
                        }
                    }
                }

                used[dsu.leader(v)] = false;
                for (auto [_r, i] : buffer) {
                    auto rit = upper_bound(all(upd[i]), edge{0, 0, t, 0}, [](edge a, edge b) { return a.t < b.t; });
                    if (rit == upd[i].begin()) continue;
                    auto r = *prev(rit);
                    if (r.t <= t) {
                        int v = dsu.leader(r.v), u = dsu.leader(r.u);
                        if (v != u) {
                            g[v].clear();
                            g[u].clear();
                            used[v] = used[u] = false;
                        }
                    }
                }
            }

        }

        for (auto &[r, id] : buffer) {
            s.insert(e[id]);
            upd[id].clear();
        }
        dsu.clear();
    }

    for (int i = 0; i < q; ++i) {
        if (qrs[i].tp == 2) {
            cout << ans[i] << '\n';
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

• Subtask 1: 0 / 13
• Subtask 2: 0 / 16
• Subtask 3: 0 / 17
• Subtask 4: 14 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27