#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=50000;
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;
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;
for(;p<e.size() && 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
bridges.cpp: In function 'void solve(int)':
bridges.cpp:89:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(;p<e.size() && e[p].v>=ques.y;p++) merge(e[p].x,e[p].y);
~^~~~~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:108: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:109: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:110: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:112: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++;
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Incorrect |
417 ms |
888 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
3072 ms |
3440 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
3020 ms |
3084 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
156 ms |
6256 KB |
Output is correct |
2 |
Correct |
69 ms |
3540 KB |
Output is correct |
3 |
Correct |
60 ms |
5272 KB |
Output is correct |
4 |
Correct |
49 ms |
5364 KB |
Output is correct |
5 |
Correct |
115 ms |
8544 KB |
Output is correct |
6 |
Correct |
162 ms |
10120 KB |
Output is correct |
7 |
Correct |
116 ms |
8756 KB |
Output is correct |
8 |
Correct |
112 ms |
7036 KB |
Output is correct |
9 |
Correct |
115 ms |
7136 KB |
Output is correct |
10 |
Correct |
116 ms |
7676 KB |
Output is correct |
11 |
Correct |
136 ms |
8732 KB |
Output is correct |
12 |
Correct |
145 ms |
8936 KB |
Output is correct |
13 |
Correct |
135 ms |
9324 KB |
Output is correct |
14 |
Correct |
116 ms |
9168 KB |
Output is correct |
15 |
Correct |
114 ms |
8936 KB |
Output is correct |
16 |
Correct |
157 ms |
9976 KB |
Output is correct |
17 |
Correct |
160 ms |
9960 KB |
Output is correct |
18 |
Correct |
157 ms |
10080 KB |
Output is correct |
19 |
Correct |
170 ms |
10060 KB |
Output is correct |
20 |
Correct |
144 ms |
9800 KB |
Output is correct |
21 |
Correct |
146 ms |
9704 KB |
Output is correct |
22 |
Correct |
154 ms |
10472 KB |
Output is correct |
23 |
Correct |
110 ms |
8552 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
3072 ms |
3440 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Incorrect |
417 ms |
888 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |