| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 340852 | ogibogi2004 | 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;
const int MAXN=5e4+6;
const int MAXM=1e5+6;
const int SQRT=500;
int n,m,q;
int ans[MAXM];
struct edge
{
int u,v,w;
bool operator<(edge const& other)const
{
if(w!=other.w)return w<other.w;
return v<other.v;
}
};
struct query
{
int type;
int a,b;
bool operator<(query const& other)const
{
if(b!=other.b)return b<other.b;
return type<other.type;
}
};
struct query1
{
int time;
int s,w;
bool operator<(query1 const& other)const
{
return w<other.w;
}
};
vector<edge>e;
vector<vector<query> >blocks;
bool used[MAXM];
bool changed[MAXM];
int par[MAXN],rnk[MAXN],sz[MAXN];
struct save
{
int u,v,rnku,rnkv,szu,szv;
};
stack<save>lol;
int getRoot(int u)
{
if(u==par[u])return u;
return getRoot(par[u]);
}
void join(int u,int v)
{
lol.push({u,v,rnk[u],rnk[v],sz[u],sz[v]});
if(rnk[u]>rnk[v])
{
par[v]=u;
sz[u]+=sz[v];
}
else if(rnk[v]>rnk[u])
{
par[u]=v;
sz[v]+=sz[u];
}
else
{
par[v]=u;
++rnk[v];
sz[u]+=sz[v];
}
}
void rollback()
{
save xd=lol.top();lol.pop();
par[xd.u]=xd.u;
par[xd.v]=xd.v;
sz[xd.u]=xd.szu;
sz[xd.v]=xd.szv;
rnk[xd.u]=xd.rnku;
rnk[xd.v]=xd.rnkv;
}
void add_edge(edge o)
{
int u=getRoot(o.u);
int v=getRoot(o.v);
if(u!=v)join(u,v);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>n>>m;
for(int i=0;i<m;++i)
{
int x,y,z;
cin>>x>>y>>z;
e.emplace_back({x,y,-z});
}
cin>>q;
for(int i=0;i<q;++i)
{
if(blocks.size()==0||blocks.back().size()==SQRT)blocks.emplace_back();
int t;
cin>>t;
if(t==1)
{
int b,r;
cin>>b>>r;
--b;
blocks.back().emplace_back({t,b,-r});
}
if(t==2)
{
int w,s;
cin>>s>>w;
blocks.back().emplace_back({t,s,-w});
}
}
memset(ans,-1,sizeof(ans));
int s=0;
vector<edge>unchanged;vector<query1>a;vector<int>used_edges;
for(int i=0;i<blocks.size();++i)
{
for(auto ivan:blocks[i])
{
if(ivan.type==1)changed[ivan.a]=1;
}
unchanged.clear();
for(int j=0;j<e.size();++j)
{
if(!changed[j])unchanged.emplace_back(e[j]);
}
sort(unchanged.begin(),unchanged.end());
for(int j=1;j<=n;++j)
{
par[j]=j;sz[j]=1;
rnk[j]=1;
}
a.clear();
for(int j=0;j<blocks[i].size();++j)
{
if(blocks[i][j].type==2)
{
a.emplace_back({j+s,blocks[i][j].a,blocks[i][j].b});
}
}
sort(a.begin(),a.end());
used_edges.clear();
int pp=0;
for(int j=0;j<a.size();++j)
{
used_edges.clear();
while(pp<unchanged.size()&&unchanged[pp].w<=a[j].w)
{
add_edge(unchanged[pp]);++pp;
}
for(int l=a[j].time-s;l>=0;--l)
{
if(blocks[i][l].type==1)
{
if(used[blocks[i][l].a])
{
used[blocks[i][l].a]=1;
continue;
}
if(blocks[i][l].b>a[j].w)
{
used[blocks[i][l].a]=1;
continue;
}
int idx=blocks[i][l].a;
int n1=getRoot(e[idx].u);
int n2=getRoot(e[idx].v);
if(n1!=n2)
{
join(n1,n2);
used_edges.emplace_back(idx);
}
used[blocks[i][l].a]=1;
}
}
for(int l=a[j].time-s;l<blocks[i].size();++l)
{
if(blocks[i][l].type==2)continue;
if(used[blocks[i][l].a])
{
continue;
}
int idx=blocks[i][l].a;
if(e[idx].w>a[j].w)
{
used[idx]=1;
continue;
}
int n1=getRoot(e[idx].u);
int n2=getRoot(e[idx].v);
if(n1!=n2)
{
join(n1,n2);
used_edges.emplace_back(idx);
}
used[idx]=1;
}
ans[a[j].time]=sz[getRoot(a[j].s)];
for(int l=used_edges.size()-1;l>=0;--l)
{
rollback();
}
for(int l=blocks[i].size()-1;l>=0;--l)
{
if(blocks[i][l].type==1)
{
used[blocks[i][l].a]=0;
}
}
}
for(int j=0;j<blocks[i].size();++j)
{
if(blocks[i][j].type==1)
{
e[blocks[i][j].a].w=blocks[i][j].b;
changed[blocks[i][j].a]=0;
}
}
s+=blocks[i].size();
}
for(int i=0;i<=q;++i)
{
if(ans[i]!=-1)cout<<ans[i]<<'\n';
}
return 0;
}