Submission #551298

#	Time	Username	Problem	Language	Result	Execution time	Memory
551298		hoanghq2004	Bridges (APIO19_bridges)	C++14	100 / 100	2695 ms	13608 KiB

bridges

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 1e5 + 10;
const int B = 400;

int n, m, q;
struct edges {
    int u, v, w, i;
    int operator < (const edges& other) const {
        if (w != other.w) return w > other.w;
        return i < other.i;
    }
} e[N];

set <edges> s;
int temp, num;
int par[N], sz[N];
int ans[N];

struct dta {
    int u, par, sz;
} old[N];

int Find(int u) {
    if (u == par[u]) return u;
    if (temp) old[num++] = {u, par[u], sz[u]};
    return par[u] = Find(par[u]);
}

void Union(int u, int v) {
    if ((u = Find(u)) == (v = Find(v))) return;
    if (temp) {
        old[num++] = {u, par[u], sz[u]};
        old[num++] = {v, par[v], sz[v]};
    }
    if (sz[u] < sz[v]) swap(u, v);
    par[v] = u;
    sz[u] += sz[v];
}

void rollback() {
    for (int i = num - 1; i >= 0; --i) {
        int u = old[i].u;
        par[u] = old[i].par;
        sz[u] = old[i].sz;
    }
    num = 0;
}

int cmd[N], x[N], y[N];
int flag[N], cur[N];

struct triple {
    int x, y, z;
    int operator < (const triple& other) const {
        if (x != other.x) return x > other.x;
        if (y != other.y) return y > other.y;
        return z > other.z;
    }
} ask[N], upd[N];

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        cin >> e[i].u >> e[i].v >> e[i].w;
        e[i].i = i;
        s.insert(e[i]);
    }
    cin >> q;
    int cnt = 0;
    for (int T = 0; T < q; ++T) {
        cin >> cmd[cnt] >> x[cnt] >> y[cnt];
        ++cnt;
        if (cnt == B || T == q - 1) {
            for (int i = 1; i <= n; ++i) par[i] = i, sz[i] = 1;
            vector <int> _;
            int n1 = 0, n2 = 0;
            for (int i = 0; i < cnt; ++i) {
                if (cmd[i] == 1) {
                    flag[x[i]] = 1, _.push_back(x[i]);
                    upd[n2++] = {y[i], x[i], i};
                } else {
                    ask[n1++] = {y[i], x[i], i};
                }
            }
            sort(ask, ask + n1);
            auto iter = s.begin();
            for (int j = 0; j < n1; ++j) {
                auto [w, z, id] = ask[j];
                while (1) {
                    if (iter == s.end() || iter -> w < w) break;
                    if (!flag[iter -> i]) Union(iter -> u, iter -> v);
                    ++iter;
                }
                for (auto i: _) cur[i] = e[i].w;
                temp = 1;
                for (int i = 0; i < n2; ++i) {
                    if (upd[i].z > id) break;
                    cur[upd[i].y] = upd[i].x;
                }
                for (auto i: _)
                    if (cur[i] >= w) Union(e[i].u, e[i].v);
                ans[id] = sz[Find(z)];
                temp = 0;
                rollback();
            }
            for (int i = 0; i < cnt; ++i) {
                if (cmd[i] == 1) {
                    s.erase(e[x[i]]);
                    e[x[i]].w = y[i];
                    s.insert(e[x[i]]);
                    flag[x[i]] = 0;
                } else {
                    cout << ans[i] << '\n';
                }
            }
            cnt = 0;
        }
    }
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:100:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  100 |                 auto [w, z, id] = ask[j];
      |                      ^

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