Submission #1292106

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292106		norman165	Bridges (APIO19_bridges)	C++20	16 / 100	3093 ms	11956 KiB

bridges

#include <bits/stdc++.h>

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define int long long
#define yes() cout << "Yes\n"
#define no() cout << "No\n"

using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;

const int inf = 1e18;
const int mod = 1e9 + 7;
const int maxn = 18;
const int mod1 = 998244353;
const int mod2 = 1e18 + 1;
const int mod3 = 1e9 + 9;
const int mod4 = 333333333;
const int mod5 = 200000;
const int mod6 = 10007;
const int mod7 = (1ll << 50);
const int mod8 = (1ll << 30) + 1;
const int mod9 = 1050000011;
const int k = 300;
const int w = 5e5 + 100;
const ld EPS = 1e-8;

int LOG = 30;

struct DSU {
    vector<int> p, sz;
    vector<pair<int, int>> history;
    int n;

    DSU(int x) {
        n = x;
        p.assign(n, 0);
        sz.assign(n, 1);
        iota(all(p), 0ll);
    }

    int get(int x) {
        if (p[x] == x) return x;
        return get(p[x]);
    }

    bool check(int a, int b) {return get(a) == get(b);}
    void unite(int a, int b) {
        a = get(a), b = get(b);
        if (a == b) return;
        if (sz[a] < sz[b]) swap(a, b);
        p[b] = a;
        sz[a] += sz[b];
        history.push_back({a, b});
    }

    int version() {return history.size();}
    void rollback(int x) {
        while (version() > x) {
            auto [a, b] = history.back();
            history.pop_back();
            p[b] = b;
            sz[a] -= sz[b];
        }
    }
};

struct e {
    int a, b, c, i;
};

void solve() {
    int n, m;
    cin >> n >> m;

    vector<e> g(m);
    for (auto& i : g) cin >> i.a >> i.b >> i.c;
    for (auto& i : g) i.a--, i.b--;
    vector<e> que;

    int q;
    cin >> q;
    while (q--) {
        int t, s, w;
        cin >> t >> s >> w;
        s--;
        int tmp10 = que.size();
        que.push_back({t, s, w, tmp10});

        if (!(q == 0 || que.size() >= k)) continue;
        vector<int> g1(m, 1);
        for (auto& [t1, s1, w1, idx] : que) if (t1 == 1) g1[s1] = 0;
        vector<e> gol;
        for (int i = 0; i < m; i++) {
            if (!g1[i]) continue;
            auto [u, v, c, idx] = g[i];
            gol.push_back({u, v, c});
        }

        vector<e> quer;
        sort(all(gol), [](e a, e b) {return a.c < b.c;});
        reverse(all(gol));
        for (int i = 0; i < que.size(); i++) if (que[i].a == 2) quer.push_back(que[i]);
        sort(all(quer), [](e a, e b) {return a.c < b.c;});
        reverse(all(quer));

        DSU dsu(n);
        vector<int> ans(que.size(), -1);
        int prime = 0;
        int prime1 = -1;
        for (auto& i : quer) {
            prime1++;
            w = i.c;

            while (prime < gol.size() && gol[prime].c >= w) {
                dsu.unite(gol[prime].a, gol[prime].b);
                prime++;
            }

            int sz = dsu.version();
            int idx = i.i;
            for (int j = 0; j < idx; j++) {
                if (que[j].a == 2) continue;
                if (que[j].c >= w) {
                    dsu.unite(g[que[j].b].a, g[que[j].b].b);
                }
            }

            for (int j = idx; j < que.size(); j++) {
                if (que[j].a == 2) continue;
                if (g[que[j].b].c >= w) {
                    dsu.unite(g[que[j].b].a, g[que[j].b].b);
                }
            }

            ans[i.i] = dsu.sz[dsu.get(i.b)];
            dsu.rollback(sz);
        }

        for (auto& [a, b, c, idx] : que) if (a == 1) g[b].c = c;
        que.clear();
        for (int& i : ans) if (i != -1) cout << i << "\n";
    }
}

signed main() {
    // cout.precision(16);

    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    // cin >> t;

    while (t--) {
        solve();
    }
}

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