Submission #563595

#	Time	Username	Problem	Language	Result	Execution time	Memory
563595		Ooops_sorry	Bridges (APIO19_bridges)	C++17	59 / 100	2644 ms	15872 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 = 333, M = 1e5 + 10, INF = 1e9;
int par[N], sz[N];
bool used[M];
vector<array<int, 4>> arr;
set<pair<int,int>> val[N];

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.pb({b, par[b], a, sz[a]});
    par[b] = a;
    sz[a] += sz[b];
}

void upd(int n) {
    while (arr.size() > n) {
        auto mas = arr.back();
        arr.pop_back();
        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--;
        val[i].insert({-1, w[i]});
    }
    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]--;
        if (u[i][0] == 1) {
            val[u[i][1]].insert({i, u[i][2]});
        }
    }
    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 = arr.size();
            for (auto to : b) {
                auto it = prev(val[to].upper_bound({qu[j][2], INF}));
                assert(it->first < qu[j][2]);
                if (it->second >= qu[j][0]) {
                    union_set(e[to].first, e[to].second);
                }
            }
            ans[qu[j][2]] = sz[find_set(qu[j][1])];
            upd(was);
        }
        upd(0);
        for (int j = 0; 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] << endl;
        }
    }
    return 0;
}

Compilation message (stderr)

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

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