Submission #1069354

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069354		Perl32	Bridges (APIO19_bridges)	C++17	100 / 100	2136 ms	9972 KiB

bridges

//I wrote this code 4 u <3
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

struct dsu {
    vector<int> p, sz;
    vector<pair<int, int>> r;

    dsu(int n) {
        p.resize(n);
        sz.resize(n, 1);
        iota(p.begin(), p.end(), 0);
    }

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

    bool unite(int x, int y) {
        x = get(x);
        y = get(y);
        if (x == y) {
            r.push_back({-1, -1});
            return false;
        }
        if (sz[x] < sz[y]) swap(x, y);
        p[y] = x;
        sz[x] += sz[y];
        r.push_back({y, x});
        return true;
    }

    int get_sz(int x) { return sz[get(x)]; }

    void yo() {
        auto [y, x] = r.back(); r.pop_back();
        if (y == -1) return;
        sz[x] -= sz[y];
        p[y] = y;
    }
};

const int K = 777;

signed main(int32_t argc, char *argv[]) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<array<int, 3>> e(m);
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        --u, --v;
        e[i] = {w, u, v};
    }
    int q;
    cin >> q;
    int T = 0;
    for (int l = 0; l < q; l += K) {
        int r = min(K, q - l);
        vector<int> del;
        vector<array<int, 3>> qry(r);
        for (int i = 0; i < r; ++i) {
            for (auto& x : qry[i]) cin >> x;
            --qry[i][1];
            if (qry[i][0] == 1) {
                del.push_back(qry[i][1]);
            }
        }
        sort(del.begin(), del.end());
        vector<int> ans(r, -1);
        vector<vector<int>> adj(r);
        vector<pair<int, int>> srt;
        for (int i = 0; i < r; ++i) {
            auto [t, v, x] = qry[i];
            if (t == 1) {
                e[v][0] = x;
            } else {
                srt.emplace_back(x, i);
                for (auto y : del) {
                    if (e[y][0] >= x) {
                        adj[i].push_back(y);
                    }
                }
            }
        }
        vector<array<int, 3>> aboba;
        for (int i = 0; i < m; ++i) {
            if (!binary_search(del.begin(), del.end(), i)) {
                aboba.push_back(e[i]);
            }
        }
        sort(aboba.begin(), aboba.end(), greater<>());
        sort(srt.begin(), srt.end(), greater<>());
        int ptr = 0;
        dsu d(n);
        for (auto [w, i] : srt) {
            while (ptr < (int) aboba.size() && aboba[ptr][0] >= w) {
                d.unite(aboba[ptr][1], aboba[ptr][2]);
                ++ptr;
            }
            for (auto x : adj[i]) {
                d.unite(e[x][1], e[x][2]);
            }
            ans[i] = d.get_sz(qry[i][1]);
            while (!adj[i].empty()) {
                d.yo();
                adj[i].pop_back();
            }
        }
        for (int i = 0; i < r; ++i) {
            if (ans[i] != -1) cout << ans[i] << '\n';
        }
    }
    return 0;
}

/*

 */

Compilation message (stderr)

bridges.cpp: In function 'int main(int32_t, char**)':
bridges.cpp:69:9: warning: unused variable 'T' [-Wunused-variable]
   69 |     int T = 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