Submission #870960

#	Time	Username	Problem	Language	Result	Execution time	Memory
870960		LOLOLO	Bridges (APIO19_bridges)	C++17	100 / 100	1474 ms	13484 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
#define           f     first
#define           s     second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (int)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())
 
const int N = 5e4 + 100;
const int M = 1e5 + 100;
const int L = 1000;

int p[N], sz[N], u[M], v[M], d[M], s[M], w[M], in[M], t[M], ans[M];
bool change[M];

vector <int> save[L + 1];
int action[M], st[M], cc = 0;

inline int find(int n) {
    while (p[n])
        n = p[n];

    return n;
}

void unite(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b)
        return;

    if (sz[a] < sz[b])
        swap(a, b);

    st[cc] = b;
    cc++;
    p[b] = a;
    sz[a] += sz[b];
    assert(cc < M);
}

void rollback(int x) {
    while (cc > x) {
        cc--;
        int t = st[cc];

        sz[p[t]] -= sz[t];
        p[t] = 0;
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        cin >> u[i] >> v[i] >> d[i];
    }

    int q;
    cin >> q;

    for (int i = 1; i <= q; i++) {
        cin >> t[i] >> s[i] >> w[i];
    }

    for (int k = 1; k <= q; k += L) {
        cc = 0;
        int l = k, r = min(q, k + L - 1);
        fill(sz + 1, sz + 1 + n, 1);
        fill(p + 1, p + 1 + n, 0);

        vector <int> ask, up, un;

        for (int i = l; i <= r; i++) {
            if (t[i] == 1) {
                change[s[i]] = 1;
            } else {
                ask.pb(i);
            }
        }

        for (int i = 1; i <= m; i++) {
            if (change[i] == 0) {
                un.pb(i);
            } else {
                up.pb(i);
            }
        }

        for (int i = l; i <= r; i++) {
            if (t[i] == 1) {
                d[s[i]] = w[i]; 
            } else {
                save[i - l].clear();
                for (int j : up) {
                    if (d[j] >= w[i]) {
                        save[i - l].pb(j);
                    }
                }
            }
        }

        sort(ask.begin(), ask.end(), [&](int a, int b) { return w[a] > w[b]; });
        sort(un.begin(), un.end(), [&](int a, int b) { return d[a] > d[b]; });
        int j = 0;

        for (int x : ask) {
            while (j < sz(un) && w[x] <= d[un[j]]) {
                unite(u[un[j]], v[un[j]]);
                j++;
            }

            int tmp = cc;
            for (int t : save[x - l]) {
                unite(u[t], v[t]);
            }

            ans[x] = sz[find(s[x])];
            rollback(tmp);
        }

        for (int x : up)
            change[x] = 0;
    }

    for (int i = 1; i <= q; i++) {
        if (t[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