This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#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=400;
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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |