Submission #1110742

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110742		anmattroi	Bridges (APIO19_bridges)	C++14	100 / 100	2915 ms	8452 KiB

bridges

#include <bits/stdc++.h>

#define maxn 50005
#define maxm 100005

using namespace std;

constexpr int B = 320;

int n, m, q, n1, n2;

inline constexpr int csk(int u) {return (u-1)/B+1;}
inline constexpr int csd(int u) {return (u-1)*B+1;}
inline constexpr int csc(int u) {return min(q, u*B);}

int par[maxn], sz[maxn];

struct Dsu_Quadruple {
    int u, v, szu, szv;
    Dsu_Quadruple() {}
    Dsu_Quadruple(int _u, int _v, int _szu, int _szv) : u(_u), v(_v), szu(_szu), szv(_szv) {}
};

vector<Dsu_Quadruple> Stack;

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

void union_set(int u, int v, bool keep = false) {
    u = find_set(u); v = find_set(v);
    if (u == v) return;
    if (sz[u] > sz[v]) swap(u, v);

    if (keep) Stack.emplace_back(u, v, sz[u], sz[v]);

    par[u] = v;
    sz[v] += sz[u];
}

void rollBack() {
    while (!Stack.empty()) {
        auto [u, v, szu, szv] = Stack.back(); Stack.pop_back();
        par[u] = u; par[v] = v;
        sz[u] = szu; sz[v] = szv;
    }
}

struct edge {
    int u, v, l, idx;
    edge() {}
    edge(int _u, int _v, int _l, int _idx) : u(_u), v(_v), l(_l), idx(_idx) {}

    bool operator < (const edge &t) const {
        return l < t.l;
    }
};

edge e[maxm];
bool dd[maxm];

struct query {
    int i, x, idx, rem;

    query() {}
    query(int _i, int _x, int _idx) : i(_i), x(_x), idx(_idx) {}

    bool operator < (const query &t) const {
        return x < t.x;
    }
};

query Type1[B+5], Type2[B+5];

int kq[maxm], tmp = 0;

edge edges[maxm];


int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        int u, v, l;
        cin >> u >> v >> l;
        e[i] = edge(u, v, l, i);
    }

    cin >> q;

    auto solve = [&](int len) -> void {
        n1 = n2 = 0;

        for (int i = 1; i <= n; i++) {par[i] = i; sz[i] = 1;}

        for (int i = 1; i <= m; i++) {
            dd[i] = true;
            edges[i] = e[i];
        }

        sort(edges + 1, edges + m + 1);

        vector<int> nho;

        for (int i = 1; i <= len; i++) {
            int type, o, x; cin >> type >> o >> x;
            if (type == 1) {
                Type1[++n1] = query(o, x, i);
                nho.emplace_back(o);
                dd[o] = false;
            }
            else {
                Type2[++n2] = query(o, x, ++tmp);
                Type2[n2].rem = n1;
            }
        }

        sort(nho.begin(), nho.end());
        nho.erase(unique(nho.begin(), nho.end()), nho.end());

        sort(Type2 + 1, Type2 + n2 + 1);

        for (int i = n2, it = m; i >= 1; i--) {
            while (it >= 1 && edges[it].l >= Type2[i].x) {
                if (!dd[edges[it].idx]) {--it; continue;}
                union_set(edges[it].u, edges[it].v);
                --it;
            }

            for (int j = Type2[i].rem; j >= 1; j--) {
                if (dd[Type1[j].i]) continue;
                dd[Type1[j].i] = true;
                if (Type1[j].x >= Type2[i].x) {
                    int I = Type1[j].i;
                    union_set(e[I].u, e[I].v, 1);
                }
            }
            for (int x : nho) {
                if (dd[x]) {
                    dd[x] = false;
                    continue;
                }
                if (e[x].l >= Type2[i].x) union_set(e[x].u, e[x].v, 1);
            }
            kq[Type2[i].idx] = sz[find_set(Type2[i].i)];
            rollBack();
        }

        for (int i = 1; i <= n1; i++) e[Type1[i].i].l = Type1[i].x;
    };

    for (int o = 1; o <= csk(q); o++) {
        int len = csc(o) - csd(o) + 1;
        solve(len);
    }

    for (int i = 1; i <= tmp; i++) cout << kq[i] << "\n";


}
/*
7 8
1 2 5
1 6 5
2 3 5
2 7 5
3 4 5
4 5 5
5 6 5
6 7 5
12
2 1 6
1 1 1
2 1 2
1 2 3
2 2 2
1 5 2
1 3 1
2 2 4
2 4 2
1 8 1
2 1 1
2 1 3
*/

Compilation message (stderr)

bridges.cpp: In function 'void rollBack()':
bridges.cpp:44:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   44 |         auto [u, v, szu, szv] = Stack.back(); Stack.pop_back();
      |              ^

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