Submission #490317

#	Time	Username	Problem	Language	Result	Execution time	Memory
490317		dooompy	Bridges (APIO19_bridges)	C++17	100 / 100	1948 ms	32568 KiB

bridges

#include "bits/stdc++.h"

using namespace std;

using ll = long long;

const int B = 1000;

int u[100005], v[100005], d[100005];
int t[100005], a[100005], b[100005];
vector<int> to_add[1005];
int par[100005], sz[100005];
int ans[100005];

stack<int> st;

void reset() {
    iota(par + 1, par + 100001, 1);
    fill(sz, sz + 100005, 1);
}
int find(int a) {
    while (a != par[a]) a = par[a];
    return a;
}

void onion(int a, int b) {
    a = find(a), b = find(b);
    if (a == b) return;
    if (sz[a] < sz[b]) swap(a, b);
    sz[a] += sz[b];
    par[b] = par[a];
    st.push(b);
}

void rollback(int s) {
    while (st.size() > s) {
        int  k = st.top();
        st.pop();
        sz[par[k]] -= sz[k];
        par[k] = k;
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
//    freopen("", "r", stdin);
//    freopen("", "w", stdout);

    int n, m; cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        cin >> u[i] >> v[i] >> d[i];
    }

    int q; cin >> q;

    for (int i = 1; i <= q; i++) {
        cin >> t[i] >> a[i] >> b[i];
    }

    for (int l = 1; l <= q; l += B) {
        int r = min(l + B, q + 1);

        reset();

        vector<int> ask, update, unchanged;
        vector<bool> changes(100005);

        for (int i = l; i < r; i++) {

            if (t[i] == 2) {
                // ask
                ask.push_back(i);
            } else {
                // change
                update.push_back(i);
                changes[a[i]] = true;
            }
        }

        for (int i = 1; i <= m; i++) {
            if (!changes[i]) {
                unchanged.push_back(i);
            }
        }

        for (int i = l; i < r; i++) {
            if (t[i] == 1) {
                d[a[i]] = b[i];
            } else {
                to_add[i-l].clear();
                for (auto x : update) {
                    if (d[a[x]] >= b[i]) {
                        to_add[i - l].push_back(a[x]);
                    }
                }
            }
        }

        sort(ask.begin(), ask.end(), [](int x, int y) {
            return b[x] > b[y];
        });

        sort(unchanged.begin(), unchanged.end(), [](int x, int y) {
            return d[x] > d[y];
        });

        int ptr = 0;

        for (int j : ask) {
            while (ptr < unchanged.size() && d[unchanged[ptr]] >= b[j]) {
                onion(u[unchanged[ptr]], v[unchanged[ptr]]);
                ptr++;
            }

            int now = st.size();

            for (auto a  : to_add[j - l]) {
                onion(v[a], u[a]);
            }

            ans[j] = sz[find(a[j])];
            rollback(now);

        }

    }
    for (int i = 1; i <= q; i++) {
        if (t[i] == 2) cout << ans[i] << "\n";
    }
}

Compilation message (stderr)

bridges.cpp: In function 'void rollback(int)':
bridges.cpp:36:22: warning: comparison of integer expressions of different signedness: 'std::stack<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   36 |     while (st.size() > s) {
      |            ~~~~~~~~~~^~~
bridges.cpp: In function 'int main()':
bridges.cpp:112:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |             while (ptr < unchanged.size() && d[unchanged[ptr]] >= b[j]) {
      |                    ~~~~^~~~~~~~~~~~~~~~~~

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