Submission #975776

#	Time	Username	Problem	Language	Result	Execution time	Memory
975776		Unforgettablepl	Bridges (APIO19_bridges)	C++17	16 / 100	3014 ms	11868 KiB

bridges

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int sqrtq = 300;

struct UFDS {
    vector<int> p, sz;
    // stores previous unites
    vector<pair<int &, int>> history;
    UFDS(int n) : p(n), sz(n, 1) { iota(p.begin(), p.end(), 0); }

    int get(int x) { return x == p[x] ? x : get(p[x]); }

    void unite(int a, int b) {
        a = get(a);
        b = get(b);
        if (a == b) { return; }
        if (sz[a] < sz[b]) { swap(a, b); }

        // save this unite operation
        history.push_back({sz[a], sz[a]});
        history.push_back({p[b], p[b]});

        p[b] = a;
        sz[a] += sz[b];
    }

    int snapshot() { return history.size(); }

    void rollback(int until) {
        while (snapshot() > until) {
            history.back().first = history.back().second;
            history.pop_back();
        }
    }
};

pair<int,pair<int,int>> edgelist[100001];
int n,m;

void answer(vector<pair<int,pair<int,int>>> &updates,vector<tuple<int,int,int>> &queries){
    vector<bool> updated(m+1);
    for(auto&i:updates)updated[i.second.first]=true;
    vector<pair<int,pair<int,int>>> edges;
    for(int i=1;i<=m;i++)if(!updated[i])edges.emplace_back(edgelist[i]);
    sort(edges.rbegin(),edges.rend());
    sort(queries.rbegin(),queries.rend());
    auto iter = edges.begin();
    UFDS dsu(50001);
    vector<pair<int,int>> ans;
    for(auto[wt,tim,pos]:queries){
        while(iter!=edges.end() and iter->first>=wt){dsu.unite(iter->second.first,iter->second.second);iter++;}
        int snap = dsu.snapshot();
        for(auto[timu,up]:updates){
            if((timu<tim and up.second>=wt) or (tim<timu and edgelist[up.first].first>=wt))dsu.unite(edgelist[up.first].second.first,edgelist[up.first].second.second);
        }
        ans.emplace_back(tim,dsu.sz[dsu.get(pos)]);
        dsu.rollback(snap);
    }
    for(auto[tim,up]:updates)edgelist[up.first].first=up.second;
    sort(ans.begin(), ans.end());
    for(auto[tim,an]:ans)cout<<an<<'\n';
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for(int i=1;i<=m;i++)cin>>edgelist[i].second.first>>edgelist[i].second.second>>edgelist[i].first;
    int q;
    cin >> q;
    int curr = 0;
    vector<pair<int,pair<int,int>>> updates;
    vector<tuple<int,int,int>> queries;
    for(int i=1;i<=q;i++){
        int type,a,b;cin>>type>>a>>b;
        if(type==1){
            updates.emplace_back(i,make_pair(a,b));
        } else {
            queries.emplace_back(b,i,a);
        }
        if(++curr==sqrtq){
            answer(updates,queries);
            updates.clear();
            queries.clear();
            curr=0;
        }
    }
    if(curr)answer(updates,queries);
}

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