Submission #1078254

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078254		dosts	Bridges (APIO19_bridges)	C++17	14 / 100	1409 ms	145932 KiB

bridges

//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 = 1000;
    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[touch[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;
        touch.assign(m+1,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();
}

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