Submission #198304

#	Time	Username	Problem	Language	Result	Execution time	Memory
198304		TAISA_	Bridges (APIO19_bridges)	C++14	46 / 100	3030 ms	9788 KiB

bridges

#include <bits/stdc++.h>
#pragma GCC target("avx2")
#define all(vec) vec.begin(), vec.end()
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
constexpr ll INF = (1LL << 30) - 1LL;
constexpr ll LINF = (1LL << 60) - 1LL;
constexpr ll MOD = 1e9 + 7;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }
int u[100000], v[100000], d[100000], par[50000], siz[50000];
int t[100000], s[100000], w[100000], vis[100000], res[100000], tmp[100000],
    rb[100000];
struct UnionFind {
    int now;
    void build(int n) {
        for (int i = 0; i < n; i++) {
            par[i] = i, siz[i] = 1;
        }
        now = 0;
    }
    inline int find(int x) {
        if (par[x] == x) {
            return x;
        } else {
            return find(par[x]);
        }
    }
    inline bool unite(int u, int v) {
        u = find(u), v = find(v);
        if (u == v)
            return false;
        if (siz[u] < siz[v])
            swap(u, v);
        par[v] = u;
        rb[now] = v;
        siz[u] += siz[v];
        now++;
        return true;
    }
    bool same(int u, int v) { return find(u) == find(v); }
    void rollback(int t) {
        for (int j = now - 1; j >= t; j--) {
            siz[par[rb[j]]] -= siz[rb[j]];
            par[rb[j]] = rb[j];
        }
        now = t;
    }
};
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    const int b = 500;
    int n, m;
    cin >> n >> m;
    vector<P> es(m);
    for (int i = 0; i < m; i++) {
        cin >> u[i] >> v[i] >> d[i];
        --u[i];
        --v[i];
    }
    int q;
    cin >> q;
    fill(res, res + q, -1);
    fill(tmp, tmp + m, -1);
    priority_queue<pair<P, int>> qs;
    UnionFind uf;
    for (int i = 0; i < q; i++) {
        cin >> t[i] >> s[i] >> w[i];
        --s[i];
    }
    for (int i = 0; i < q; i++) {
        vector<int> vs;
        if (t[i] == 1) {
            vis[s[i]] = 1;
        } else {
            qs.push(make_pair(P(w[i], s[i]), i));
        }
        if (i % b < b - 1 && i != q - 1) {
            continue;
        }
        for (int j = 0; j < m; j++) {
            es[j] = P(d[j], j);
        }
        sort(all(es), greater<P>());
        int id = 0;
        uf.build(n);
        int fs = (i / b) * b;
        int cnt = 0;
        while (!qs.empty()) {
            int ww = qs.top().first.first, st = qs.top().first.second,
                idx = qs.top().second;
            qs.pop();
            while (id < m && es[id].first >= ww) {
                if (!vis[es[id].second]) {
                    uf.unite(u[es[id].second], v[es[id].second]);
                    cnt++;
                }
                id++;
            }
            for (int k = fs; k < idx; k++) {
                if (t[k] == 1) {
                    tmp[s[k]] = w[k];
                }
            }
            for (int k = fs; k < idx; k++) {
                if (t[k] == 1 && w[k] == tmp[s[k]] && w[k] >= ww) {
                    uf.unite(u[s[k]], v[s[k]]);
                }
            }
            for (int k = idx + 1; k <= i; k++) {
                if (t[k] == 1 &&
                    (tmp[s[k]] == -1 ? d[s[k]] : tmp[s[k]]) >= ww) {
                    uf.unite(u[s[k]], v[s[k]]);
                }
            }
            for (int k = fs; k < idx; k++) {
                if (t[k] == 1) {
                    tmp[s[k]] = -1;
                }
            }
            res[idx] = siz[uf.find(st)];
            uf.rollback(cnt);
        }
        for (int j = i; j >= fs; j--) {
            if (t[j] == 1 && vis[s[j]]) {
                d[s[j]] = w[j];
                vis[s[j]] = 0;
            }
        }
    }
    for (int i = 0; i < q; i++) {
        if (res[i] != -1) {
            cout << res[i] << '\n';
        }
    }
}

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