Submission #960666

#	Time	Username	Problem	Language	Result	Execution time	Memory
960666		MisterReaper	Bridges (APIO19_bridges)	C++17	100 / 100	1558 ms	124812 KiB

bridges

#include <bits/stdc++.h>
using i64 = long long;

constexpr int maxN = 5E4 + 5;

std::vector<std::pair<int, int>> operations;
int par[maxN], sz[maxN];
void reset() {
    std::iota(par, par + maxN, 0);
    std::fill(sz, sz + maxN, 1);
    operations.clear();
}

int get(int a) {
    if(par[a] == a) {
        return a;
    }
    return get(par[a]);
}

bool unite(int u, int v) {
    u = get(u), v = get(v);
    if(u == v) {
        return false;
    }
    if(sz[u] > sz[v]) {
        std::swap(u, v);
    }
    par[u] = v;
    sz[v] += sz[u];
    operations.emplace_back(u, v);
    return true;
}

void rollback() {
    auto [u, v] = operations.back();
    operations.pop_back();
    par[u] = u;
    sz[v] -= sz[u];
}

int size(int a) {
    return sz[get(a)];
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m;
    std::cin >> n >> m;

    std::vector<bool> changed;
    std::vector<int> u(m), v(m), w(m);
    for(int i = 0; i < m; i++) {
        std::cin >> u[i] >> v[i] >> w[i];
        u[i]--, v[i]--;
    }

    int q;
    std::cin >> q;

    std::vector<int> t(q), x(q), y(q);
    for(int i = 0; i < q; i++) {
        std::cin >> t[i] >> x[i] >> y[i];
        x[i]--;
    }

    constexpr int B = 1000;

    std::vector<std::vector<int>> deck(q);
    std::vector<int> ans(q);
    for(int l = 0; l < q; l += B) {
        int r = std::min(q, l + B);
        changed.assign(m, false);
        reset();

        std::vector<int> ask;
        for(int i = l; i < r; i++) {
            if(t[i] == 1) {
                changed[x[i]] = true;
            } else {
                ask.emplace_back(i);
            }
        }

        std::vector<int> edges, able;
        for(int i = 0; i < m; i++) {
            if(!changed[i]) {
                edges.emplace_back(i);
            } else {
                able.emplace_back(i);
            }
        }

        for(int i = l; i < r; i++) {
            if(t[i] == 1) {
                w[x[i]] = y[i];
            } else {
                for(int j : able) {
                    if(y[i] <= w[j]) {
                        deck[i].emplace_back(j);
                    }
                }
            }
        }

        std::sort(edges.begin(), edges.end(), [&](int lhs, int rhs) -> bool {
            return w[lhs] > w[rhs];
        });
        std::sort(ask.begin(), ask.end(), [&](int lhs, int rhs) -> bool {
            return y[lhs] > y[rhs];
        });
        int p = 0;
        for(int i : ask) {
            while(p != edges.size() && w[edges[p]] >= y[i]) {
                unite(u[edges[p]], v[edges[p]]);
                p++;
            }
            int ps = operations.size();
            for(int j : deck[i]) {
                unite(u[j], v[j]);
            }
            ans[i] = size(x[i]);
            while(operations.size() != ps) {
                rollback();
            }
            deck[i].clear();
        }
    }

    for(int i = 0; i < q; i++) {
        if(t[i] == 2) {
            std::cout << ans[i] << '\n';
        }
    }

    return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:116:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |             while(p != edges.size() && w[edges[p]] >= y[i]) {
      |                   ~~^~~~~~~~~~~~~~~
bridges.cpp:125:37: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  125 |             while(operations.size() != ps) {
      |                   ~~~~~~~~~~~~~~~~~~^~~~~

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