Submission #551273

#	Time	Username	Problem	Language	Result	Execution time	Memory
551273		hoanghq2004	Bridges (APIO19_bridges)	C++14	13 / 100	3080 ms	11420 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 = 300;

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;
        if (u != other.u) return u < other.u;
        return v < other.v;
    }
} 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;
}

/*
3 4
1 2 5
2 3 2
3 1 4
2 3 8
2
1 4 1
2 2 5

*/

int cmd[N], x[N], y[N];
int flag[N], cur[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 (T == q - 1) {
            for (int i = 1; i <= n; ++i) par[i] = i, sz[i] = 1;
            vector <tuple <int, int, int> > ask;
            vector <int> _;
            for (int i = 0; i < cnt; ++i) {
                if (cmd[i] == 1) {
                    flag[x[i]] = 1;
                    _.push_back(x[i]);
                } else {
                    ask.push_back({y[i], x[i], i});
                }
            }
            sort(ask.begin(), ask.end(), greater<>());
            auto iter = s.begin();
            for (auto [w, z, id]: ask) {
                while (1) {
                    if (iter == s.end() || iter -> w < w) break;
                    if (!flag[iter -> i]) Union(iter -> u, iter -> v);
//                    cout << iter -> u << ' ' << iter -> v << ' ' << iter -> w << ' ' << w << '\n';
                    ++iter;
                }
                for (auto i: _) cur[i] = e[i].w;
                temp = 1;
                for (int i = 0; i < id; ++i)
                    if (cmd[i] == 1) cur[x[i]] = y[i];
                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';
                }
            }
        }
    }
}

Compilation message (stderr)

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

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