| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 552764 | jjaewon | Bridges (APIO19_bridges) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
#define fi first
#define se second
#define endl '\n'
#define y1 holyshit
#define all(x) x.begin(),x.end()
const int inf=0x3f3f3f3f;
#define SZ 700
struct DATA{
//type 0: edge, type 1: query 1, type 2: query 2
int type,idx,u,v,d;
bool operator<(const DATA& p) const{ return d==p.d?type<p.type:d<p.d; }
}edge[100010];
vector<DATA> query;
int N,M,Q,ans[100010];
int p[50010],sz[50010];
stack<pii> st;
int find(int x){ return x==p[x]?x:find(p[x]); }
bool merge(int x,int y,bool undo){
x=find(x); y=find(y);
if(x==y) return 0;
if(sz[x]<sz[y]) swap(x,y);
sz[x]+=sz[y];
p[y]=x;
if(undo) st.push({x,y});
return 1;
}
void solve(){
vector<DATA> v;
bool used[100010]={0};
for(auto i:query){
if(i.type==1) used[i.idx]=1;
else if(i.type==2) v.push_back(i);
}
for(auto i:edge) if(!used[i.idx]) v.push_back(i);
sort(all(v));
reverse(all(v));
for(int i=1;i<=N;i++) p[i]=i, sz[i]=1;
for(auto i:v){
if(i.type==0) merge(i.u,i.v,0);
else{
bool flag=0;
for(auto j:query){
if(i.idx==j.idx) flag=1;
if(j.type==1){
if((!flag&&j.d>=i.d)||(flag&&edge[j.u].d>=i.d))
merge(edge[j.u].u,edge[j.u].v,1);
}
}
ans[i.idx]=sz[find(i.u)];
while(!st.empty()){
auto [x,y]=st.top();
sz[x]-=sz[y];
p[y]=y;
st.pop();
}
}
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
cin>>N>>M;
for(int i=1;i<=M;i++){
int u,v,d; cin>>u>>v>>d;
edge[i]={0,i,u,v,d};
}
cin>>Q;
for(int i=1;i<=Q;i++){
int t,a,b; cin>>t>>a>>b;
query.push_back({t,i,a,0,b});
if(i%SZ==0){
solve();
for(auto j:query) if(j.type==1) edge[j.u]=j.v;
query.clear();
}
}
solve();
for(int i=1;i<=Q;i++) if(ans[i]>0) cout<<ans[i]<<endl;
return 0;
}