Submission #934558

#	Time	Username	Problem	Language	Result	Execution time	Memory
934558		VladaMG98	Bridges (APIO19_bridges)	C++17	14 / 100	1484 ms	9280 KiB

bridges

// Problem: B - Bridges
// Contest: Virtual Judge - 2024-02-27 APIO Simulation
// URL: https://vjudge.net/contest/612540#problem/B
// Memory Limit: 512 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define print(A,t) cerr << #A << ": "; copy(all(A),ostream_iterator<t>(cerr," " )); cerr << endl
#define prArr(A,n,t)  cerr << #A << ": "; copy(A,A + n,ostream_iterator<t>(cerr," " )); cerr << endl
#define what_is(x) cerr << #x << " is " << x << endl
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int MAXN = 50010, MAXM = 100010, MAXQ = 100010;

int N, M, Q;
int from[MAXM], to[MAXM], weg[MAXM];
int type[MAXQ], a[MAXQ], b[MAXQ], ans[MAXQ];

struct event {
    int key, index;
    // index > 0 -- it is an edge index
    // index < 0 -- it is a query index
    event() {}
    event (int _key, int _index) : key(_key), index(_index) {}
    bool operator <(const event &other) const {
        if (key == other.key) return index < other.index;
        return key < other.key;
    }
};

struct dsu_rollback {
    vi par, sz;
    stack<int> roll;
    dsu_rollback (int _n) {
        par.resize(_n + 1);
        sz.resize(_n + 1);
        for (int i = 1; i <= _n; i++) {
            par[i] = i;
            sz[i] = 1;
        }
    }
    int get (int x) { while (par[x] != x) x = par[x]; return x; }
    bool unite (int u, int v) {
        u = get(u);
        v = get(v);
        if (u == v) return false;
        if (sz[u] > sz[v]) swap(u, v);
        roll.push(u);
        par[u] = par[v];
        sz[v] += sz[u];
        return true;
    }
    void rollback (int wanted) {
        while (sz(roll) > wanted) {
            int k = roll.top(); roll.pop();
            sz[par[k]] -= sz[k];
            par[k] = k;
        }
    }
    int get_size (int u) {
        return sz[get(u)];
    }
};

bool in_current[MAXM];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    vector<event> ALL_EVENTS;
    cin >> N >> M;
    for (int i = 1; i <= M; i++) {
        cin >> from[i] >> to[i] >> weg[i];
    }

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

    vector<event> initial_events;
    for (int j = 1; j <= M; j++) {
        initial_events.emplace_back(weg[j], j);
    }

    sort(all(initial_events));

    const int B = 500;
    for (int i = 1; i <= Q; i += B) {
        int l = i, r = min(Q, l + B - 1);
        // we want to process all the queries between l and r

        set<int> current_vec;
        for (int j = l; j <= r; j++) {
            if (type[j] == 1) {
                current_vec.insert(a[j]);
                in_current[a[j]] = true;
            }
        }

        // gathering all previous edges
        vector<event> small_events;

        // gathering all the queries
        for (int j = l; j <= r; j++) {
            if (type[j] == 2) {
                small_events.emplace_back(b[j], -j);
            }
        }
        sort(all(small_events));

        vector<event> all_events; all_events.reserve(sz(initial_events) + sz(small_events));
        merge(all(initial_events), all(small_events), back_inserter(all_events));

        // sorting everything together
        reverse(all(all_events));
        dsu_rollback d(N);

        for (auto ev : all_events) {
            if (ev.index > 0) {
                if (in_current[ev.index]) continue;
                d.unite(from[ev.index], to[ev.index]);
            } else {
                set<int> curr = current_vec;
                // it is a query, so create a small graph
                int prev_size = d.roll.size();
                int query_index = -ev.index;
                for (int j = query_index - 1; j >= l; j--) {
                    if (type[j] == 2) continue;
                    if (curr.count(a[j])) {
                        if (b[j] >= ev.key) {
                            d.unite(from[a[j]], to[a[j]]);
                        }
                        curr.erase(a[j]);
                    }
                }
                for (auto e : curr) {
                    if (weg[e] >= ev.key) d.unite(from[e], to[e]);
                }
                ans[query_index] = d.get_size(a[query_index]);
                d.rollback(prev_size);
            }
        }

        for (int j = l; j <= r; j++) {
            if (type[j] == 1) {
                weg[a[j]] = b[j];
                in_current[a[j]] = false;
            }
        }
    }

    for (int i = 1; i <= Q; i++) {
        if (type[i] == 2) {
            cout << ans[i] << endl;
        }
    }
    return 0;
}

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