Submission #975756

#	Time	Username	Problem	Language	Result	Execution time	Memory
975756		Unforgettablepl	Bridges (APIO19_bridges)	C++17	14 / 100	3036 ms	15248 KiB

bridges

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

#define int long long

const int sqrtq = 300;

struct UFDS{
    vector<int> p,siz;
    UFDS(int n):p(n+1),siz(n+1,1){iota(p.begin(), p.end(),0);}
    int findRoot(int x){
        return p[x]==x ? x : findRoot(p[x]);
    }
    pair<int,int> unite(int a,int b){
        a = findRoot(a);
        b = findRoot(b);
        if(a==b)return {-1,-1};
        if(siz[a]<siz[b])swap(a,b);
        siz[a]+=siz[b];
        p[b]=a;
        return {a,b};
    }
    void rollback(pair<int,int> update){
        if(update.first==-1)return;
        p[update.second]=update.second;
        siz[update.first]-=siz[update.second];
    }
};

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++;}
        vector<pair<int,int>> rolls;
        for(auto[timu,up]:updates){
            if((timu<tim and up.second>=wt) or (tim<timu and edgelist[up.first].first>=wt))rolls.emplace_back(dsu.unite(edgelist[up.first].second.first,edgelist[up.first].second.second));
        }
        ans.emplace_back(tim,dsu.siz[dsu.findRoot(pos)]);
        reverse(rolls.begin(), rolls.end());
        for(auto&x:rolls)dsu.rollback(x);
    }
    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();
        }
    }
    if(curr)answer(updates,queries);
}

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