Submission #978842

#	Time	Username	Problem	Language	Result	Execution time	Memory
978842		ZHIRDILBILDIZ	Bridges (APIO19_bridges)	C++14	100 / 100	1525 ms	14848 KiB

bridges

#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int, int>

using namespace std;
const int N = 1e5 + 10;
const int B = 1000;

int p[N];
int sz[N];
int ans[N];
vector<pair<int*, int>> hint;
void init (int _sz) {
    hint.clear();
    for (int i = 0; i < _sz + 10; ++i)
        p[i] = i,
            sz[i] = 1;
}
int get (int u) {
    if (u != p[u])
        return get(p[u]);
    return p[u];
}
void join (int u, int v) {
    u = get(u);
    v = get(v);
    if (u == v)
        return;
    if (sz[u] > sz[v])
        swap(u, v);
    hint.push_back({&sz[v], sz[v]});
    hint.push_back({&p[u], u});
    sz[v] += sz[u];
    p[u] = v;
}
void rollback (int sz) {
    while (hint.size() > sz) {
        auto now = hint.back();
        *now.fi = now.se;
        hint.pop_back();
    }
}

signed main () {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int n, m;
    cin >> n >> m;
    int u[m], v[m], w[m];

    for (int i = 0; i < m; ++i) {
        cin >> u[i] >> v[i] >> w[i];
        --u[i];
        --v[i];
    }

    int q;
    cin >> q;

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

    vector<int> need[B + 10];
    for (int l = 0; l < q; l += B) {
        init(n);
        int r = min(q, l + B);

        vector<int> upd;
        vector<pii> ask, not_upd;

        bool us[m] = {};

        for (int j = l; j < r; ++j)
            if (type[j] == 1) {
                upd.push_back(j);
                us[x[j]] = 1;
            } else
                ask.push_back({y[j], j});

        for (int i = 0; i < m; ++i)
            if (!us[i])
                not_upd.push_back({w[i], i});

        for (int j = l; j < r; ++j)
            if (type[j] == 1)
                w[x[j]] = y[j];
            else {
                need[j - l].clear();
                for (int q : upd)
                    if (w[x[q]] >= y[j]) need[j - l].push_back(x[q]);
            }

        sort(not_upd.begin(), not_upd.end());
        reverse(not_upd.begin(), not_upd.end());
        sort(ask.begin(), ask.end());
        reverse(ask.begin(), ask.end());

        int uk = 0;
        for (auto j : ask) {
            while (uk < not_upd.size() && not_upd[uk].fi >= j.fi) {
                int pos = not_upd[uk].se;
                // cout << "join " << u[pos] << ' ' << v[pos] << '\n';
                join(u[pos], v[pos]);
                ++uk;
            }
            int was = hint.size();
            for (int q : need[j.se - l])
                join(u[q], v[q]);
            ans[j.se] = sz[get(x[j.se])];
            rollback(was);
        }
    }

    for (int i = 0; i < q; ++i)
        if (type[i] == 2)
            cout << ans[i] << '\n';

    return 0;
}

// 7 8
// 1 5 100
// 1 2 200
// 5 2 30
// 5 3 25
// 3 6 11
// 3 7 12
// 3 4 9
// 5 4 17
// 7
// 2 1 200
// 2 1 100
// 2 3 25
// 2 3 10
// 2 7 12
// 2 5 30
// 2 1 25

Compilation message (stderr)

bridges.cpp: In function 'void rollback(int)':
bridges.cpp:38:24: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int*, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   38 |     while (hint.size() > sz) {
      |            ~~~~~~~~~~~~^~~~
bridges.cpp: In function 'int main()':
bridges.cpp:105:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |             while (uk < not_upd.size() && not_upd[uk].fi >= j.fi) {
      |                    ~~~^~~~~~~~~~~~~~~~

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