Submission #563604

#	Time	Username	Problem	Language	Result	Execution time	Memory
563604		Ooops_sorry	Bridges (APIO19_bridges)	C++17	100 / 100	2337 ms	6136 KiB

bridges

#include<bits/stdc++.h>

using namespace std;

#define pb push_back
#define ld long double
#define ll long long

mt19937 rnd(51);

const int N = 50010, K = 800, M = 1e5 + 10, INF = 1e9;
int par[N], sz[N], Sz = 0;
bool used[M], ed[M];
array<int, 4> arr[M];

int find_set(int v) {
    while (v != par[v]) {
        v = par[v];
    }
    return v;
}

void union_set(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a == b) return;
    if (sz[a] < sz[b]) {
        swap(a, b);
    }
    arr[Sz++] = {b, par[b], a, sz[a]};
    par[b] = a;
    sz[a] += sz[b];
}

void upd(int n) {
    while (Sz > n) {
        auto mas = arr[--Sz];
        par[mas[0]] = mas[1];
        sz[mas[2]] = mas[3];
    }
}

signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif // LCOAL
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    for (int i = 0; i < N; i++) {
        sz[i] = 1;
        par[i] = i;
    }
    int n, m;
    cin >> n >> m;
    vector<pair<int,int>> e(m);
    vector<int> w(m);
    for (int i = 0; i < m; i++) {
        cin >> e[i].first >> e[i].second >> w[i];
        e[i].first--, e[i].second--;
    }
    int q;
    cin >> q;
    vector<array<int, 3>> u(q);
    vector<int> ans(q, -1);
    for (int i = 0; i < q; ++i) {
        cin >> u[i][0] >> u[i][1] >> u[i][2];
        u[i][1]--;
    }
    for (int i = 0; i < q; i += K) {
        vector<array<int, 3>> qu;
        for (int j = i; j < min(i + K, q); ++j) {
            if (u[j][0] == 1) {
                used[u[j][1]] = 1;
            } else {
                qu.pb({u[j][2], u[j][1], j});
            }
        }
        vector<int> a, b;
        for (int j = 0; j < m; ++j) {
            if (!used[j]) {
                a.pb(j);
            } else {
                b.pb(j);
            }
        }
        sort(a.begin(), a.end(), [&](int i, int j){return w[i] > w[j];});
        sort(qu.rbegin(), qu.rend());
        int ind = 0;
        for (int j = 0; j < qu.size(); ++j) {
            while (ind < a.size() && w[a[ind]] >= qu[j][0]) {
                union_set(e[a[ind]].first, e[a[ind]].second);
                ind++;
            }
            int was = Sz;
            for (int f = qu[j][2]; f >= i; --f) {
                if (u[f][0] == 1 && !ed[u[f][1]]) {
                    ed[u[f][1]] = 1;
                    if (u[f][2] >= qu[j][0]) {
                        union_set(e[u[f][1]].first, e[u[f][1]].second);
                    }
                }
            }
            for (auto to : b) {
                if (!ed[to]) {
                    if (w[to] >= qu[j][0]) {
                        union_set(e[to].first, e[to].second);
                    }
                }
            }
            ans[qu[j][2]] = sz[find_set(qu[j][1])];
            upd(was);
            for (int f = qu[j][2]; f >= i; --f) {
                if (u[f][0] == 1) {
                    ed[u[f][1]] = 0;
                }
            }
        }
        upd(0);
        for (int j = i; j < min(i + K, q); ++j) {
            if (u[j][0] == 1) {
                used[u[j][1]] = 0;
                w[u[j][1]] = u[j][2];
            }
        }
    }
    for (int i = 0; i < q; i++) {
        if (ans[i] != -1) {
            cout << ans[i] << '\n';
        }
    }
    return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:89:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |         for (int j = 0; j < qu.size(); ++j) {
      |                         ~~^~~~~~~~~~~
bridges.cpp:90:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |             while (ind < a.size() && w[a[ind]] >= qu[j][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