Submission #1364675

#TimeUsernameProblemLanguageResultExecution timeMemory
1364675silence25다리 (APIO19_bridges)C++20
100 / 100
1141 ms29336 KiB
// author: yanybayev

#include "bits/stdc++.h"

using namespace std;

#define ff first
#define ss second
#define pp pop_back
#define ll long long
#define pb push_back
#define ls(v) (int)v.size()
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define wr cout << "------------------------" << endl
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}

const int N = 1e5 + 5;
int par[N];
int sz[N];
int B = 1000;
int u[N];
int v[N];
int w[N];
int t[N];
int x[N];
int y[N];
int changed[N];
stack<int> st;
vector<int> ext[N];
int ans[N];

int find(int x) {
    if (x == par[x]) return x;
    return find(par[x]);
}

void Union(int a, int b) {
    if ((a = find(a)) == (b = find(b))) return;
    if (sz[a] < sz[b]) swap(a, b);
    st.push(b);
    par[b] = a;
    sz[a] += sz[b];    
}

void rollback(int x) {
    while (ls(st) > x) {
        int b = st.top(); st.pop();
        sz[par[b]] -= sz[b];
        par[b] = b;
    }
}

signed main(){
#ifdef yanybayev
    freopen("file.in","r",stdin);
#endif
    #define print(...) 42

    ios::sync_with_stdio(false);cin.tie(nullptr);
    int n, m; cin >> n >> m;
    for (int i = 1; i <= m; ++ i) cin >> u[i] >> v[i] >> w[i];
    int q; cin >> q;
    for (int i = 1; i <= q; ++ i) cin >> t[i] >> x[i] >> y[i];
    for (int l = 1; l <= q; l += B){
        iota(par + 1, par + n + 1, 1);
        fill(sz + 1, sz + n + 1, 1);
        fill(changed + 1, changed + m + 1, false);
        int r = min(q, l + B - 1);
        vector<int> upd, ask;
        for (int i = l; i <= r; ++ i) {
            if (t[i] == 1) {
                changed[x[i]] = 1;
                upd.pb(i);
            }
            else {
                ask.pb(i);
            }
        }
        vector<int> unchanged;
        for (int i = 1; i <= m; ++ i) if (!changed[i]) unchanged.pb(i);
        for (int i = l; i <= r; ++ i) {
            if (t[i] == 1) {
                w[x[i]] = y[i];
            }
            else {
                ext[i - l].clear();
                for (auto it : upd) if (w[x[it]] >= y[i]) ext[i - l].pb(x[it]);
            }
        }
        sort(all(ask), [&](int A, int B) {
            return y[A] > y[B];
        });
        sort(all(unchanged), [&](int A, int B) {
            return w[A] > w[B];
        });
        int idx = 0;
        for (auto i : ask) {
            while (idx < ls(unchanged) and w[unchanged[idx]] >= y[i]) {
                Union(u[unchanged[idx]], v[unchanged[idx]]);
                idx += 1;
            }
            int snap = ls(st);
            for (auto j : ext[i - l]) {
                Union(u[j], v[j]);
            }
            ans[i] = sz[find(x[i])];
            rollback(snap);
        }
    }
    for (int i = 1; i <= q; ++ i) if (t[i] == 2) cout << ans[i] << endl;
    cout << endl;
    return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...