제출 #1078261

#제출 시각아이디문제언어결과실행 시간메모리
1078261dosts다리 (APIO19_bridges)C++17
0 / 100
3102 ms12456 KiB
//Dost SEFEROĞLU
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<    
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>
const int MOD = 1e9+7,inf = 2e18;
struct DSU {
    int n,timer=0;
    stack<pii> st;
    vi dad,sz;
    DSU(int nn) {
        n = nn;
        dad.resize(nn+1);
        iota(all(dad),0ll);
        sz.assign(nn+1,1);
    }

    int find(int x) {
        if (x == dad[x]) return x;
        return find(dad[x]);
    }
    void unite(int x,int y) {
        int a = find(x),b = find(y);
        if (a == b) return;
        if (sz[a] < sz[b]) swap(a,b);
        dad[b] = a;
        sz[a] += sz[b];
        timer++;
        st.push({a,b});
    }
    void rollback(int tt) {
        while (timer > tt) {
            dad[st.top().ss] = st.top().ss;
            sz[st.top().ff] -= sz[st.top().ss];
            timer--;
            st.pop();
        }
    }
    void reset() {
        rollback(0);
        iota(all(dad),0ll);
    }
};

void solve() { 
    int n,m;
    cin >> n >> m;
    vi a(m+1),b(m+1),c(m+1);
    for (int i=1;i<=m;i++) cin >> a[i] >> b[i] >> c[i];
    int q;
    cin >> q;
    vi t(q+1),s(q+1),w(q+1);
    for (int i=1;i<=q;i++) cin >> t[i] >> s[i] >> w[i];
    vi ans(q+1,-1);
    const int B = 2;
    DSU dsu(n);
    vi joiner[q+1];
    for (int l=1;l<=q;l+=B) {
        int r = min(l+B-1,q);
        vi unchanged,changed,touch(m+1,0),asker;
        for (int i=l;i<=r;i++) {
            if (t[i] == 1) touch[s[i]] = i;
            else asker.push_back(i);
        }
        for (int i=1;i<=m;i++) if (!touch[i]) unchanged.push_back(i);
        for (int i=1;i<=m;i++) if (touch[i]) changed.push_back(i);
        for (int i=l;i<=r;i++) {
            if (t[i] == 1) continue;
            for (auto it : changed) {
                if (touch[it] > i && c[it] >= w[i]) joiner[i].push_back(it);
                else if (touch[it] < i && w[it] >= w[i]) joiner[i].push_back(it);
            }
        }
        sort(all(unchanged),[&](int x,int y){
            return c[x] > c[y];
        });
        sort(all(asker),[&](int x,int y) {
            return w[x] > w[y];
        });
        int sz = unchanged.size(); 
        int ptr = 0;
        for (auto i : asker) { 
            while (ptr < sz && c[unchanged[ptr]] >= w[i]) {
                dsu.unite(a[unchanged[ptr]],b[unchanged[ptr]]);
                ptr++;
            }
            int oldsz = dsu.timer;
            for (auto it : joiner[i]) dsu.unite(a[it],b[it]);
            ans[i] = dsu.sz[dsu.find(s[i])];
            dsu.rollback(oldsz);
        } 
        for (int i=l;i<=r;i++) if (t[i] == 1) c[s[i]] = w[i];
        dsu.reset();
    }
    for (int i=1;i<=q;i++) {
        if (ans[i] != -1) cout << ans[i] << '\n';
    }
}
 
signed main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t; 
    while (t --> 0) solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...