Submission #706909

#	Time	Username	Problem	Language	Result	Execution time	Memory
706909		jhwest2	Bridges (APIO19_bridges)	C++14	0 / 100	3065 ms	4996 KiB

bridges

#include <bits/stdc++.h>
using namespace std;

const int N = 101010;
const int B = 200;

int n, m, q, u[N], v[N], w[N], s[N], t[N], y[N], z[N], weight[N], ans[N];
bool used[N];

struct dsu {
    int pp[N], sz[N], rk[N];
    vector<array<int, 3>> rb;

    void init() {
        iota(pp, pp + N, 0);
        fill(sz, sz + N, 1);
    }
    int find(int a) {
        return (pp[a] == a) ? a : find(pp[a]);
    }
    void merge(int a, int b) {
        a = find(a); b = find(b);
        if (a != b) {
            rb.push_back({1, b, pp[b]});
            pp[b] = a;

            rb.push_back({2, a, sz[a]});
            sz[a] += sz[b];

            if (rk[a] == rk[b]) {
                rb.push_back({3, a, rk[a]});
                rk[a]++;
            }
        }
    }
    void rollback(int v) {
        while (rb.size() > v) {
            auto [x, y, z] = rb.back();
            rb.pop_back();

            if (x == 1)
                pp[y] = z;
            if (x == 2)
                sz[y] = z;
            if (x == 3)
                rk[y] = z;
        }
    }
} d1;

mt19937 rnd(1557);
int rng(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rnd);
}
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    // cin >> n >> m;
    n = 50000;
    m = 100000;

    for (int i = 1; i <= m; i++) {
        // cin >> u[i] >> v[i] >> w[i];
        u[i] = rng(1, n - 1);
        v[i] = rng(u[i] + 1, n);
        w[i] = rng(1, 100);
    }
    // cin >> q;
    q = 10000;
    for (int i = 1; i <= q; i++) {
        // cin >> t[i] >> y[i] >> z[i];
        t[i] = rng(1, 2);
        y[i] = rng(1, n);
        z[i] = rng(1, 100);
    }
    for (int i = 1; i <= m; i++)
        s[i] = i;

    vector<int> upd, ask;
    for (int x = 1; x <= q; x++) {
        if (t[x] == 1)
            upd.push_back(x), used[y[x]] = 1;
        else
            ask.push_back(x);
        
        if (upd.size() == B || x == q) {
            sort(s + 1, s + 1 + m, [&](int i, int j) {
                return w[i] > w[j];
            });

            sort(ask.begin(), ask.end(), [&](int i, int j) {
                return z[i] > z[j];
            });
            
            vector<int> edges;
            for (int i : upd)
                edges.push_back(y[i]);
            
            sort(edges.begin(), edges.end());
            edges.erase(unique(edges.begin(), edges.end()), edges.end());

            for (int j : edges)
                weight[j] = w[j];

            d1.init();
            int p = 1;
            for (auto i : ask) {
                while (p <= m && w[s[p]] >= z[i]) {
                    if (!used[s[p]]) 
                        d1.merge(u[s[p]], v[s[p]]);
                    ++p;
                }

                for (int j : upd) {
                    if (j <= i)
                        w[y[j]] = z[j];
                }

                int sz = d1.rb.size();
                for (int j : edges) {
                    int a = d1.find(u[j]);
                    int b = d1.find(v[j]);

                    if (w[j] >= z[i]) {
                        d1.merge(a, b);
                    }
                }
                ans[i] = d1.sz[d1.find(y[i])];
                d1.rollback(sz);

                for (int j : edges)
                    w[j] = weight[j];
            }

            for (auto i : upd) {
                used[i] = 0;
                w[y[i]] = z[i];
            }
        }
    }
    for (int i = 1; i <= q; i++) {
        if (t[i] == 2)
            cout << ans[i] << '\n';
    }
}

Compilation message (stderr)

bridges.cpp: In member function 'void dsu::rollback(int)':
bridges.cpp:37:26: warning: comparison of integer expressions of different signedness: 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   37 |         while (rb.size() > v) {
      |                ~~~~~~~~~~^~~
bridges.cpp:38:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   38 |             auto [x, y, z] = rb.back();
      |                  ^

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