제출 #1354478

#제출 시각아이디문제언어결과실행 시간메모리
1354478Born_To_Laugh다리 (APIO19_bridges)C++17
44 / 100
3021 ms5268 KiB
// Born_To_Laugh - Hughie Do
#include <bits/stdc++.h>
#define alle(AC) AC.begin(), AC.end()
#define fi first
#define se second
using namespace std;
typedef long long ll;
[[maybe_unused]] const int MOD = 998244353, INF = 1e9 + 7;
struct DSU
{
    int n;
    vector<int> par;
    vector<int> sz;
    vector<pair<int, int>> unis;
    DSU(int len){
        n = len;
        par.assign(n + 1, 0);
        sz.assign(n + 1, 1);
        for(int i=0; i<=n; ++i) par[i] = i;
    }
    int headset(int a){
        if(a == par[a]) return a;
        return headset(par[a]);
    }
    int getsz(int a){
        a = headset(a);
        return sz[a];
    }
    bool unionset(int a, int b){
        a = headset(a);
        b = headset(b);
        if(a == b) return 0;
        if(sz[a] < sz[b]) swap(a, b);
        par[b] = a;
        sz[a] += sz[b];
        unis.push_back({a, b});
        return 1;
    }
    void rollback(int cnt){
        assert(cnt <= unis.size());
        while(cnt--){
            int a = unis.back().fi, b = unis.back().se;
            par[b] = b;
            sz[a] -= sz[b];
            unis.pop_back();
        }
    }
};

const int maxn = 1e5 + 10;
const int sq = 1000;
int n, m, q;
array<int, 3> edges[maxn];
array<int, 3> qrs[maxn];
ll ans[maxn];

void solve(){
    cin >> n >> m;
    for(int i=1; i<=m; ++i) cin >> edges[i][0] >> edges[i][1] >> edges[i][2];
    cin >> q;
    for(int i=1; i<=q; ++i) cin >> qrs[i][0] >> qrs[i][1] >> qrs[i][2];
    for(int i=0; i<=q/sq; ++i){
        DSU dsu(n);
        vector<int> unch;
        vector<array<int, 3>> blqr;//a, wei, pos
        set<int> changes;

        for(int j = max(1, i * sq); j < min(q + 1, (i + 1) * sq); ++j){
            if(qrs[j][0] == 1) changes.insert(qrs[j][1]);
            else blqr.push_back({qrs[j][1], qrs[j][2], j});
        }
        for(int i=1; i<=m; ++i){
            if(changes.find(i) == changes.end()) unch.push_back(i);
        }

        sort(alle(unch), [](int a, int b){
            return edges[a][2] > edges[b][2];
        });
        sort(alle(blqr), [](array<int, 3> a, array<int, 3> b){
            return a[1] > b[1];
        });
        
        int id = -1;
        for(auto &elm: blqr){
            int node = elm[0], wei = elm[1], pos = elm[2];
            while(id + 1 < unch.size() && edges[unch[id + 1]][2] >= wei){
                dsu.unionset(edges[unch[id + 1]][0], edges[unch[id + 1]][1]);
                id++;
            }
            set<int> added;
            int cnt = 0;
            for(int j=pos; j>=max(1, i * sq); --j){
                if(qrs[j][0] == 1){
                    int a = qrs[j][1];
                    int newwei = qrs[j][2];
                    if(added.find(a) == added.end()){
                        added.insert(a);
                        if(newwei >= wei)
                            cnt += dsu.unionset(edges[a][0], edges[a][1]);
                    }
                }
            }
            for(auto &sth: changes){
                if(added.find(sth) == added.end()){
                    if(edges[sth][2] >= wei)
                        cnt += dsu.unionset(edges[sth][0], edges[sth][1]);
                }
            }
            ans[pos] = dsu.getsz(node);
            dsu.rollback(cnt);
        }
        for(int j = max(1, i * sq); j < min(q + 1, (i + 1) * sq); ++j){
            if(qrs[j][0] == 1){
                edges[qrs[j][1]][2] = qrs[j][2];
            }
        }
    }
    for(int i=1; i<=q; ++i)
        if(ans[i] != 0) cout << ans[i] << '\n';
}
signed main(){
    // freopen("inp.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    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...