Submission #1200306

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200306		trufanov.p	Bridges (APIO19_bridges)	C++20	73 / 100	3087 ms	5832 KiB

bridges

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <string>
#include <queue>
#include <unordered_set>
#include <deque>
#include <numeric>
#include <cmath>
#include <unordered_map>

using namespace std;

#pragma GCC optimize("O3")
#pragma GCC optimization("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

typedef long long ll;

struct Edge {
    int u, v, lim, ind;
    Edge(int u, int v, int lim, int ind) :u(u), v(v), lim(lim), ind(ind) {}
    bool operator <(const Edge& other) const {
        return lim > other.lim;
    }
};

struct FirstType {
    int t, ind, nlim;
    FirstType(int t, int ind, int nlim) :t(t), ind(ind), nlim(nlim) {}
};

struct SecondType {
    int t, v, w;
    SecondType(int t, int v, int w) :t(t), v(v), w(w) {}
    bool operator <(const SecondType& other) const {
        return w > other.w;
    }
};

enum class Array {
    P, D, SZ
};

struct RollBack {
    Array arr;
    int pos, old;
    RollBack(Array arr, int pos, int old) :arr(arr), pos(pos), old(old) {}
};

struct DSU {
    vector<int> p, d, sz;
    vector<RollBack> rolls;
    DSU(int n) {
        p.resize(n);
        iota(p.begin(), p.end(), 0);
        d.resize(n);
        sz.resize(n, 1);
    }
    int get_par(int v) {
        if (v == p[v]) {
            return v;
        }
        return get_par(p[v]);
    }
    void unite(int u, int v, bool save = false) {
        u = get_par(u);
        v = get_par(v);
        if (u != v) {
            if (d[u] > d[v]) {
                swap(u, v);
            }
            if (save) {
                rolls.push_back(RollBack(Array::P, u, p[u]));
            }
            p[u] = v;
            if (d[u] == d[v]) {
                if (save) {
                    rolls.push_back(RollBack(Array::D, v, d[v]));
                }
                d[v]++;
            }
            if (save) {
                rolls.push_back(RollBack(Array::SZ, v, sz[v]));
            }
            sz[v] += sz[u];
        }
    }
    int get_ans(int v) {
        return sz[get_par(v)];
    }
    void rollback() {
        for (int i = rolls.size() - 1; i > -1; --i) {
            if (rolls[i].arr == Array::P) {
                p[rolls[i].pos] = rolls[i].old;
            } else if (rolls[i].arr == Array::D) {
                d[rolls[i].pos] = rolls[i].old;
            } else {
                sz[rolls[i].pos] = rolls[i].old;
            }
        }
        rolls.clear();
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector<Edge> edges;
    for (int i = 0; i < m; ++i) {
        int u, v, lim;
        cin >> u >> v >> lim;
        u--, v--;
        edges.push_back(Edge(u, v, lim, i));
    }
    int q;
    cin >> q;
    vector<int> ans(q, -1);
    int C = (int)sqrt(q);
    vector<vector<FirstType>> ft;
    vector<vector<SecondType>> st;
    for (int i = 0; i < q; ++i) {
        if (i / C == ft.size()) {
            ft.push_back(vector<FirstType>());
            st.push_back(vector<SecondType>());
        }
        int type;
        cin >> type;
        if (type == 1) {
            int ind, lim;
            cin >> ind >> lim;
            ind--;
            ft[i / C].push_back(FirstType(i, ind, lim));
        } else {
            int v, w;
            cin >> v >> w;
            v--;
            st[i / C].push_back(SecondType(i, v, w));
        }
    }
    int blocks = ft.size();
    for (int b = 0; b < blocks; ++b) {
        sort(edges.begin(), edges.end());
        vector<int> perm(m);
        for (int i = 0; i < m; ++i) {
            perm[edges[i].ind] = i;
        }
        sort(st[b].begin(), st[b].end());
        DSU dsu(n);
        int it = 0;
        unordered_set<int> changed;
        for (auto& ftq : ft[b]) {
            changed.insert(ftq.ind);
        }
        for (auto& stq : st[b]) {
            while (it < m && edges[it].lim >= stq.w) {
                if (!changed.count(edges[it].ind)) {
                    dsu.unite(edges[it].u, edges[it].v);
                }
                it++;
            }
            unordered_map<int, int> last;
            for (auto& ftq : ft[b]) {
                if (ftq.t < stq.t) {
                    last[ftq.ind] = ftq.nlim;
                } else {
                    if (edges[perm[ftq.ind]].lim >= stq.w && !last.count(ftq.ind)) {
                        dsu.unite(edges[perm[ftq.ind]].u, edges[perm[ftq.ind]].v, true);
                    }
                }
            }
            for (auto& e : last) {
                if (e.second >= stq.w) {
                    dsu.unite(edges[perm[e.first]].u, edges[perm[e.first]].v, true);
                }
            }
            ans[stq.t] = dsu.get_ans(stq.v);
            dsu.rollback();
        }
        for (auto& ftq : ft[b]) {
            edges[perm[ftq.ind]].lim = ftq.nlim;
        }
    }
    for (int i = 0; i < q; ++i) {
        if (ans[i] != -1) {
            cout << ans[i] << '\n';
        }
    }
}

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