Submission #1182933

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182933		GGOSHAB	Bridges (APIO19_bridges)	C++20	100 / 100	1170 ms	12736 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 = 1000;

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<(const edge &a, const 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;
};

int cur_edges = 0;
int head[maxn], nxt[maxn], to[maxn];
bool vused[maxn];
void add_edge(int v, int u) {
    to[cur_edges] = u;
    nxt[cur_edges] = head[v];
    head[v] = cur_edges++;
}

void clear_graph() {
    cur_edges = 0;
}

int dfs(vector<bool> &used, DSU &dsu, int v) {
    used[v] = true;
    int res = dsu.w[v];
//    for (int u : g[v]) {
//        if (!used[u]) {
//            res += dfs(g, used, dsu, u);
//        }
//    }

    int e = head[v];
    while (e != -1) {
        if (!used[to[e]]) {
            res += dfs(used, dsu, to[e]);
        }
        e = nxt[e];
    }

    return res;
}

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<int>> 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]);
//    }
    DSU dsu(n);
    vector<pair<edge, int>> buffer;
    vector<Pint> mp;
    vector<bool> usede(m);
    fill(all(head), -1);
    for (int bl = 0; bl * sqn < q; ++bl) {
        buffer.clear();
        mp.clear();
        int l = bl * sqn, r = min((bl + 1) * sqn, q);
        for (int i = l; i < r; ++i) {
            if (qrs[i].tp == 1) {
                int id = qrs[i].v;
                if (s.count(e[id])) {
                    buffer.push_back({e[id], 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.push_back({-qrs[i].w, i});
            }
        }

        reverse(all(buffer));
        sort(all(mp));
        auto it = s.begin();
        for (auto &[_w, id] : mp) {
            clear_graph();
            int w = _w * -1;
            while (it != s.end() && it->w >= w) {
                dsu.unite(it->v, it->u);
                it++;
            }
            {
                auto [v, w, t, tp] = qrs[id];
                for (auto [r, i] : buffer) {
                    if (usede[i]) continue;
                    if (r.t <= t) {
                        usede[i] = true;
                        int v = dsu.leader(r.v), u = dsu.leader(r.u);
                        if (v != u && w <= r.w) {
//                            g[v].push_back(u);
//                            g[u].push_back(v);
                            add_edge(v, u);
                            add_edge(u, v);
                        }
                    }
                }

//                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];
//                    int e = head[v];
//                    while (e != -1) {
//                        if (!used[to[e]]) {
//                            used[to[e]] = true;
//                            q.push(to[e]);
//                        }
//                        e = nxt[e];
//                    }
//                }
                ans[t] = dfs(used, dsu, dsu.leader(v));

                used[dsu.leader(v)] = false;
                for (auto [r, i] : buffer) {
                    usede[i] = false;
                    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;
                        head[v] = head[u] = -1;
                    }
                }
            }
        }

        for (auto &[r, id] : buffer) {
            s.insert(e[id]);
        }
        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: 13 / 13
• Subtask 2: 16 / 16
• Subtask 3: 17 / 17
• Subtask 4: 14 / 14
• Subtask 5: 13 / 13
• Subtask 6: 27 / 27