Submission #729967

#TimeUsernameProblemLanguageResultExecution timeMemory
729967MtSakaBridges (APIO19_bridges)C++17
59 / 100
3078 ms6208 KiB
    #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=334;
        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";
    }
#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...