Submission #558974

#	Time	Username	Problem	Language	Result	Execution time	Memory
558974		nutella	Bridges (APIO19_bridges)	C++17	100 / 100	2249 ms	14376 KiB

bridges

//#define _GLIBCXX_DEBUG

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>

using namespace std;

//#include <ext/pb_ds/assoc_container.hpp>
//
//using namespace __gnu_pbds;
//
//template<typename T>
//using ordered_set = tree<T, null_type, less < T>, rb_tree_tag, tree_order_statistics_node_update>;

template<typename T>
using normal_queue = priority_queue<T, vector<T>, greater<>>;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

#define trace(x) cout << #x << ": " << (x) << endl;
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define uniq(x) x.resize(unique(all(x)) - begin(x))
#define sz(s) ((int) size(s))
#define pii pair<int, int>
#define mp(x, y) make_pair(x, y)
#define int128 __int128
#define pb push_back
#define popb pop_back
#define eb emplace_back
#define fi first
#define se second
#define itn int

typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef double db;
typedef unsigned int uint;


template<typename T>
bool ckmn(T &x, T y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}

template<typename T>
bool ckmx(T &x, T y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}

int bit(int x, int b) {
    return (x >> b) & 1;
}

int rand(int l, int r) { return (int) ((ll) rnd() % (r - l + 1)) + l; }


const ll infL = 3e18;
const int infI = 1000000000 + 7;
const int infM = 0x3f3f3f3f; //a little bigger than 1e9
const ll infML = 0x3f3f3f3f3f3f3f3fLL; //4.5e18
const int N = 50002, M = 100001, B = 500, Q = 100001;
const int mod = 998244353;
const ld eps = 1e-9;

int p[N], sz[N];

void init(int n) {
    fill(sz, sz + n, 1);
    iota(p, p + n, 0);
}

int get(int a) {
    return (a == p[a] ? a : p[a] = get(p[a]));
}

void mrg(int a, int b) {
    a = get(a), b = get(b);
    if (a == b) return;
    if (sz[a] < sz[b]) swap(a, b);
    p[b] = a;
    sz[a] += sz[b];
}

bool used[N], nww[M];
vector<pair<int, int>> g[N];
int now = 0, wnow, U[M], V[M], W[M], prv[M + Q], nxt[M + Q], tp[Q], x[Q], y[Q], ans[Q], prvv[Q];

vector<int> vis;

void dfs(int v) {
    vis.push_back(v);
    used[v] = true;
    now += sz[v];
    for (auto [to, ww]: g[v]) {
        if (!used[to] && ww >= wnow) {
            dfs(to);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        cin >> U[i] >> V[i] >> W[i];
        --U[i], --V[i];
        prv[i] = i;
    }
    int q;
    cin >> q;
    vector<array<int, 3>> qu(q + m); //w, type, i
    for (int i = 0; i < q; ++i) {
        cin >> tp[i] >> x[i] >> y[i];
        --x[i];
        qu[i + m] = {-y[i], tp[i], i + m};
        if (tp[i] == 1) {
            nxt[prv[x[i]]] = i;
            prvv[i] = prv[x[i]];
            prv[x[i]] = i + m;
        }
    }
    for (int i = 0; i < m; ++i) {
        nxt[prv[i]] = infI;
        qu[i] = {-W[i], 1, i};
    }
    sort(all(qu));
    for (int i = 0; i < q; i += B) {
        int r = min(i + B, q);
        init(n);
        for (auto t: qu) {
            if (t[1] == 1 && nxt[t[2]] >= r) {
                if (t[2] >= m) {
                    int id = t[2] - m;
                    if (id < i) {
                        mrg(U[x[id]], V[x[id]]);
                    }
                } else {
                    mrg(U[t[2]], V[t[2]]);
                }
            } else if (t[1] == 2) {
                int j = t[2] - m;
                if (j < i || j >= r) continue;
                for (int k = j; k >= i; --k) {
                    if (tp[k] == 1 && !nww[x[k]]) {
                        nww[x[k]] = true;
                        int a = get(U[x[k]]), b = get(V[x[k]]);
                        g[a].emplace_back(b, y[k]), g[b].emplace_back(a, y[k]);
                    }
                }
                for (int k = j; k < r; ++k) {
                    if (tp[k] == 1 && !nww[x[k]]) {
                        int z = prvv[k];
                        int w;
                        if (z >= m) {
                            w = y[z - m];
                        } else {
                            w = W[z];
                        }
                        nww[x[k]] = true;
                        int a = get(U[x[k]]), b = get(V[x[k]]);
                        g[a].emplace_back(b, w), g[b].emplace_back(a, w);
                    }
                }
                wnow = y[j];
                dfs(get(x[j]));
                ans[j] = now;
                now = 0;
                for (int z: vis) {
                    used[z] = false;
                }
                vis.clear();
                for (int k = r - 1; k >= i; --k) {
                    if (tp[k] == 1 && nww[x[k]]) {
                        nww[x[k]] = false;
                        int a = get(U[x[k]]), b = get(V[x[k]]);
                        g[a].clear(), g[b].clear();
                    }
                }
            }
        }
    }
    for (int i = 0; i < q; ++i) {
        if (tp[i] == 2) {
            cout << ans[i] << '\n';
        }
    }
    return 0;
}

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