Submission #959709

#	Time	Username	Problem	Language	Result	Execution time	Memory
959709		Blagoj	Bridges (APIO19_bridges)	C++17	100 / 100	1652 ms	91348 KiB

bridges

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define ll long long
#define all(x) (x).begin(), (x).end()

const int K = 1000, N = 50100;

struct Edge {
    int f, t, w;
};

struct Query {
    int t, x, w;
};

struct State {
    int x, y, rnkX, rnkY;
};

struct DSU {
    stack<State> s;
    int rnk[N], ldr[N];

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

    int Find(int x) {
        if (ldr[x] == x) return x;
        return Find(ldr[x]);
    }

    void Union(int x, int y) {
        x = Find(x), y = Find(y);
        if (x == y) return;
        if (rnk[y] > rnk[x]) swap(x, y);
        s.push({x, y, rnk[x], rnk[y]});
        ldr[y] = x;
        rnk[x] += rnk[y];
    }

    void rollback(int x) {
        while (s.size() > x) {
            auto top = s.top();
            s.pop();
            ldr[top.x] = top.x;
            ldr[top.y] = top.y;
            rnk[top.x] = top.rnkX;
            rnk[top.y] = top.rnkY; 
        }
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    vector<Edge> v(m);
    for (int i = 0; i < m; i++) cin >> v[i].f >> v[i].t >> v[i].w;
    int q;
    cin >> q;
    vector<Query> qr(q);
    for (int i = 0; i < q; i++) {
        cin >> qr[i].t >> qr[i].x >> qr[i].w;
        if (qr[i].t == 1) qr[i].x--;
    }
    DSU dsu;
    vector<int> ans(q, -1);
    bool changed[m];
    for (int l = 0; l < q; l += K) {
        int r = min(q - 1, l + K - 1);
        dsu.init();
        memset(changed, 0, sizeof(changed));
        vector<int> noChange, update, ask;
        for (int i = l; i <= r; i++) {
            if (qr[i].t == 1) {
                changed[qr[i].x] = 1;
                update.push_back(i);
            }
            else ask.push_back(i);
        }
        for (int i = 0; i < m; i++) {
            if (changed[i]) continue;
            noChange.push_back(i);
        }
        vector<int> join[K];
        for (int i = l; i <= r; i++) {
            if (qr[i].t == 1) v[qr[i].x].w = qr[i].w;
            else {
                for (auto x : update) {
                    if (v[qr[x].x].w >= qr[i].w) join[i - l].push_back(qr[x].x);
                }
            }
        }

        sort(all(noChange), [&] (int a, int b) {
            return v[a].w > v[b].w;
        });

        sort(all(ask), [&] (int a, int b) {
            return qr[a].w > qr[b].w;
        });

        int ptr = 0;
        for (auto x : ask) {
            while (ptr < noChange.size() && v[noChange[ptr]].w >= qr[x].w) {
                dsu.Union(v[noChange[ptr]].f, v[noChange[ptr]].t);
                ptr++;
            }
            int sz = dsu.s.size();
            for (auto y : join[x - l]) dsu.Union(v[y].f, v[y].t);
            ans[x] = dsu.rnk[dsu.Find(qr[x].x)];
            dsu.rollback(sz);
        }
    }
    for (int i = 0; i < q; i++) if (ans[i] != -1) cout << ans[i] << endl;
}

Compilation message (stderr)

bridges.cpp: In member function 'void DSU::rollback(int)':
bridges.cpp:49:25: warning: comparison of integer expressions of different signedness: 'std::stack<State>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   49 |         while (s.size() > x) {
      |                ~~~~~~~~~^~~
bridges.cpp: In function 'int main()':
bridges.cpp:113:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |             while (ptr < noChange.size() && v[noChange[ptr]].w >= qr[x].w) {
      |                    ~~~~^~~~~~~~~~~~~~~~~

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