Submission #1063105

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063105		manhlinh1501	Bridges (APIO19_bridges)	C++17	100 / 100	1675 ms	355880 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using pii = pair<int, int>;
const int MAXN = 1e5 + 5;
const int oo32 = 1e9 + 5;
const int BLOCK_SIZE = 1000;
#define prev ___prev
struct event {
    int type, x, y, p;
    event(int type = 0, int x = 0, int y = 0, int p = 0): type(type), x(x), y(y), p(p) {}
};

struct edge {
    int u, v, w;
    edge(int u = 0, int v = 0, int w = 0) : u(u), v(v), w(w) {}
};

int N, M, Q;
edge e[MAXN];
event query[MAXN];
int ans[MAXN];

struct DSU {
    int lab[MAXN];
    vector<tuple<int, int, int, int>> rb;

    void init(int N) {
        for(int i = 1; i <= N; i++)
            lab[i] = -1;
    }

    int root(int u) {
        if (lab[u] < 0)
            return u;

        return root(lab[u]);
    }

    bool join(int u, int v) {
        u = root(u);
        v = root(v);

        if (u == v)
            return false;

        if (lab[u] > lab[v])
            swap(u, v);

        lab[u] += lab[v];
        lab[v] = u;
        return true;
    }

    int size(int u) {
        return -lab[root(u)];
    }

    bool join_with_rollback(int u, int v) {
        u = root(u);
        v = root(v);

        if (u == v)
            return false;

        if (lab[u] > lab[v])
            swap(u, v);

        rb.emplace_back(u, lab[u], v, lab[v]);
        lab[u] += lab[v];
        lab[v] = u;
        return true;
    }

    void rollback() {
        auto [u, _u, v, _v] = rb.back();
        rb.pop_back();
        lab[u] = _u;
        lab[v] = _v;
    }

    void rollback_all() {
        while(!rb.empty()) rollback();
    }
} dsu;

bool is_change[MAXN];
int idx[MAXN];
vector<edge> prev[MAXN];
edge ne[MAXN];

void process(int l, int r) {
    dsu.init(N);
    vector<int> changed_edge;

    for(int i = 1; i <= M; i++) {
        ne[i] = e[i];
        is_change[i] = false;
        idx[i] = i;
    }

    sort(idx + 1, idx + M + 1, [&](const int a, const int b) {
        return e[a].w > e[b].w;
    });

    for(int i = l; i <= r; i++) {
        auto [type, x, y, p] = query[i];
        if(type == 1)
            is_change[x] = true;
    }

    for(int i = 1; i <= M; i++) {
        if(is_change[i])
            changed_edge.emplace_back(i);
    }

    for(int i = l; i <= r; i++) {
        auto [type, x, y, p] = query[i];
        if(type == 1)
            e[x].w = y;
        else {
            for(int z : changed_edge)
                prev[i].emplace_back(e[z]);
        }
    }

    sort(query + l, query + r + 1, [&](const event a, const event b) {
        return a.y > b.y;
    });

    int j = 1;
    for(int i = l; i <= r; i++) {
        auto [type, x, y, p] = query[i];
        if(type == 1)
            continue;
        while(j <= M and ne[idx[j]].w >= y) {
            if(is_change[idx[j]] == false) {
                dsu.join(ne[idx[j]].u, ne[idx[j]].v);
            }
            j++;
        }
        for(auto [u, v, w] : prev[p]) {
            if(w >= y) dsu.join_with_rollback(u, v);
        }
        ans[p] = dsu.size(x);
        dsu.rollback_all();
    }
}

signed main() {
#define TASK "code"

    if (fopen(TASK ".inp", "r")) {
        freopen(TASK ".inp", "r", stdin);
        freopen(TASK ".out", "w", stdout);
    }

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;

    for(int i = 1; i <= M; i++) {
        auto &[u, v, w] = e[i];
        cin >> u >> v >> w;
    }

    cin >> Q;
    for(int i = 1; i <= Q; i++) {
        auto &[type, x, y, p] = query[i];
        cin >> type >> x >> y;
        p = i;
    }

    for(int i = 1; i <= Q; i++) ans[i] = -1;

    for(int i = 1; i <= Q; i += BLOCK_SIZE) {
        process(i, min(Q, i + BLOCK_SIZE - 1));
    }

    for(int i = 1; i <= Q; i++) {
        if(ans[i] == -1)
            continue;
        cout << ans[i] << "\n";
    }
    return (0 ^ 0);
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:154:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  154 |         freopen(TASK ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:155:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  155 |         freopen(TASK ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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