Submission #729966

#	Time	Username	Problem	Language	Result	Execution time	Memory
729966		MtSaka	Bridges (APIO19_bridges)	C++17	100 / 100	2510 ms	10472 KiB

bridges

#include<bits/stdc++.h>
#define overload(a,b,c,d,...) d
#define rep1(a) for(ll _=0;_<(ll)a;++_)
#define rep2(i,a) for(ll i=0;i<(ll)a;++i)
#define rep3(i,a,b) for(ll i=a;i<(ll)b;++i)
#define rep(...) overload(__VA_ARGS__,rep3,rep2,rep1)(__VA_ARGS__)
#define rrep1(i,a) for(ll i=(ll)a-1;i>=0;--i)
#define rrep2(i,a,b) for(ll i=(ll)b-1;i>=(ll)a;--i)
#define rrep(...) overload(__VA_ARGS__,rrep2,rrep1)(__VA_ARGS__)
#define all(a) a.begin(),a.end()
#define lb(v,x) lower_bound(all(v),x);
#define ub(v,x) upper_bound(all(v),x);
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
template<typename T,typename U>
inline bool chmin(T&a,const U&b){return (a>b?a=b,true:false);}
template<typename T,typename U>
inline bool chmax(T&a,const U&b){return (a<b?a=b,true:false);}
struct dsu{
    private:
    vector<int>p;
    vector<pair<int,int>>history;
    public:
    dsu(int n):p(n,-1){}
    int root(int x){return (p[x]<0?x:root(p[x]));}
    int size(int a){return -p[root(a)];}
    void merge(int u,int v){
        u=root(u),v=root(v);
        if(u==v)return ;
        if(p[u]>p[v])swap(u,v);
        history.emplace_back(v,p[v]);
        p[u]+=p[v];
        p[v]=u;
    }
    void snapshot(){history.clear();}
    void rollback(){
        while(history.size()){
            auto [u,sz]=history.back();history.pop_back();
            p[p[u]]-=sz;
            p[u]=sz;
        }
    }
};
struct edge{
    int u,v,w;
};
struct query{
    int t,x,w,idx;
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;cin>>n>>m;
    vector<edge>es(m);
    rep(i,m){
        int u,v,w;cin>>u>>v>>w;u--,v--;
        es[i]=edge{u,v,w};
    }
    int q;cin>>q;
    vector<query>qs(q);
    vector<int>ans(q);
    rep(i,q){
        cin>>qs[i].t>>qs[i].x>>qs[i].w;
        qs[i].idx=i;
        qs[i].x--;
    }
    constexpr int B=500;
    for(int l=0;l<q;l+=B){
        const int r=min(q,l+B);
        const int sz=r-l;
        vector<bool>changed(m,false);
        vector<query>qu;
        rep(i,l,r){
            if(qs[i].t==1)changed[qs[i].x]=1;
            else qu.emplace_back(qs[i]);
        }
        vector<edge>pre;
        vector<int>chg;
        rep(i,m){
            //cerr<<changed[i]<<" ";
            if(changed[i])chg.push_back(i);
            else pre.push_back(es[i]);
        }//cerr<<endl;
        sort(all(pre),[](const auto&l,const auto&r){
            return l.w<r.w;
        });
        sort(all(qu),[](const auto&l,const auto&r){
            return l.w>r.w;
        });
        vector<vector<int>>merge(sz);
        rep(i,l,r){
            if(qs[i].t==1)es[qs[i].x].w=qs[i].w;
            else for(auto j:chg)if(es[j].w>=qs[i].w)merge[i-l].emplace_back(j);
        }
        dsu d(n);
        for(auto [t,x,w,idx]:qu){
            //cerr<<t<<" "<<x<<" "<<w<<" "<<idx<<endl;
            while(!pre.empty()&&pre.back().w>=w){
                //cerr<<pre.back().u<<" "<<pre.back().v<<" "<<pre.back().w<<endl;
                d.merge(pre.back().u,pre.back().v);
                pre.pop_back();
            }
            d.snapshot();
            //cerr<<1<<endl;
            for(auto j:merge[idx-l]){
                //cerr<<es[j].u<<" "<<es[j].v<<endl;
                d.merge(es[j].u,es[j].v);
            }
            ans[idx]=d.size(x);
            d.rollback();
        }
    }
    rep(i,q)if(qs[i].t==2)cout<<ans[i]<<"\n";
}

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