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>
#define MAX_N 500005
#define MAX_M 1000005
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(),(v).end()
using namespace std;
typedef long long LL;
typedef long double LD;
typedef pair<int,int> pii;
typedef pair<LL,LL> pil;
struct edge{
int x,y,v;
}E[MAX_M],Q[MAX_M];
struct node{
int t,i,b,a;
};
struct infor{
int x,y,hx,hy,ex,ey;
};
int n,m;
int qn;
int par[MAX_N],height[MAX_N],ea[MAX_N];
bool chk[MAX_M];
const int b=300;
vector<edge> e;
vector<node> lst;
vector<pii> ans;
stack<infor> st;
int find_par(int x){return par[x]==x?x:find_par(par[x]);}
void init(){
for(int i=1;i<=n;i++){
par[i]=i;
height[i]=ea[i]=1;
}
}
int merge(int x,int y){
int p=find_par(x);
int q=find_par(y);
if(p==q) return 0;
st.push({p,q,height[p],height[q],ea[p],ea[q]});
if(height[p]>height[q]){
ea[p]+=ea[q];
par[q]=p;
}else{
if(height[p]==height[q]) height[q]++;
ea[q]+=ea[p];
par[p]=q;
}
return 1;
}
void _back(int cnt){
while(st.size() && cnt--){
infor p = st.top();
par[p.x]=p.x;par[p.y]=p.y;
height[p.x]=p.hx;height[p.y]=p.hy;
ea[p.x]=p.ex;ea[p.y]=p.ey;
st.pop();
}
while(st.size()) st.pop();
}
void solve(int k){
for(int i=1;i<=m;i++) chk[i]=false;
lst.clear();lst.resize(0);
for(int i=0;i<qn;i++){
if(Q[i].v==1){
chk[Q[i].x]=true;
lst.pb({i,Q[i].x,E[Q[i].x].v,Q[i].y});
Q[i].v=-1;
}else Q[i].v=i;
}
e.clear();e.resize(0);
for(int i=1;i<=m;i++){
if(!chk[i]) e.pb(E[i]);
}
sort(Q,Q+qn,[&](const edge x,const edge y){
if(x.v==-1) return false;
if(y.v==-1) return true;
return (x.y>y.y);
});
sort(all(e),[&](const edge x,const edge y){return x.v>y.v;});
init();
int p=0;
for(int i=0;i<qn;i++){
edge ques = Q[i];
if(ques.v==-1) break;
int cn=0;
int eee=e.size();
for(;p<eee && e[p].v>=ques.y;p++) merge(e[p].x,e[p].y);
for(node ne:lst){
int x=E[ne.i].x;
int y=E[ne.i].y;
int v;
if(ne.t>ques.v) v=ne.b;
else v=ne.a;
if(v>=ques.y) cn+=merge(x,y);
}
ans.pb({k+ques.v,ea[find_par(ques.x)]});
_back(cn);
}
for(node ne:lst) E[ne.i].v=ne.a;
qn=0;
}
int main(){
int i;
scanf("%d %d",&n,&m);
for(i=1;i<=m;i++) scanf("%d %d %d",&E[i].x,&E[i].y,&E[i].v);
int q;scanf("%d",&q);
for(i=1;i<=q;i++){
scanf("%d %d %d",&Q[qn].v,&Q[qn].x,&Q[qn].y);qn++;
if(qn==b) solve(i);
}
solve(i);
sort(all(ans));
for(pii print:ans) printf("%d\n",print.se);
return 0;
}
Compilation message (stderr)
bridges.cpp: In function 'int main()':
bridges.cpp:110:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&n,&m);
~~~~~^~~~~~~~~~~~~~~
bridges.cpp:111:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(i=1;i<=m;i++) scanf("%d %d %d",&E[i].x,&E[i].y,&E[i].v);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:112:13: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int q;scanf("%d",&q);
~~~~~^~~~~~~~~
bridges.cpp:114:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d",&Q[qn].v,&Q[qn].x,&Q[qn].y);qn++;
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |