#include <bits/stdc++.h>
#define forf(i,a,b) for(int i = a; i<=b; i++)
#define all(v) v.begin(),v.end()
using namespace std;
typedef long long ll;
int N,M,Q;
pair<int, int> edge[100001];
pair<int, int> edgeidx[1000001];
vector<pair<int,int> > adj[100001];
int chk[100001];
int dfs(int now, int c){
chk[now] = 1;
int ret = 1;
for(auto &[nxt,cost] : adj[now]){
if(chk[nxt]) continue;
if(cost < c) continue;
ret += dfs(nxt,c);
}
return ret;
}
struct Query{
int st, c, id;
bool operator<(const Query &r) const{
if(c==r.c) return id<r.id;
return c<r.c;
}
} q[100001];
struct DSU{
int grp[100001];
int sz[100001];
void init(){
forf(i,1,N){
grp[i] = i;
sz[i] = 1;
}
}
int fi(int x){
if(grp[x] == x) return x;
return grp[x] = fi(grp[x]);
}
void un(int x, int y){
x = fi(x); y = fi(y);
sz[y] += sz[x]; sz[x] = 0;
grp[x] = y;
}
} dsu;
struct Event{
int t;
int q;
int u,v;
int id;
bool operator<(const Event &r) const{
if(t == r.t){
if(q==r.q) return id<r.id;
return q<r.q;
}
else return t>r.t;
}
};
vector<Event> events;
int ans[100001];
int main(){
scanf("%d %d" , &N,&M);
forf(i,1,M){
int u,v,c;
scanf("%d %d %d" , &u,&v,&c);
edge[i] = {u,v};
edgeidx[i] = {adj[u].size(),adj[v].size()};
adj[u].push_back({v,c});
adj[v].push_back({u,c});
events.push_back({c,0,u,v,i});
}
scanf("%d" , &Q);
forf(i,1,Q){
int cmd,a,b;
scanf("%d %d %d" , &cmd,&a,&b);
events.push_back({b,1,a,0,i});
}
sort(all(events));
dsu.init();
for(auto &i : events){
if(i.q){
ans[i.id] = dsu.sz[dsu.fi(i.u)];
}
else{
if(dsu.fi(i.u) != dsu.fi(i.v)) dsu.un(i.u,i.v);
}
}
forf(i,1,Q) printf("%d\n" , ans[i]);
}
Compilation message
bridges.cpp: In function 'int main()':
bridges.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
66 | scanf("%d %d" , &N,&M);
| ~~~~~^~~~~~~~~~~~~~~~~
bridges.cpp:69:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
69 | scanf("%d %d %d" , &u,&v,&c);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:77:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
77 | scanf("%d" , &Q);
| ~~~~~^~~~~~~~~~~
bridges.cpp:80:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
80 | scanf("%d %d %d" , &cmd,&a,&b);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
6488 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
65 ms |
13604 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
55 ms |
13292 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
92 ms |
17376 KB |
Output is correct |
2 |
Correct |
37 ms |
10448 KB |
Output is correct |
3 |
Correct |
45 ms |
11760 KB |
Output is correct |
4 |
Correct |
38 ms |
11500 KB |
Output is correct |
5 |
Correct |
84 ms |
17132 KB |
Output is correct |
6 |
Correct |
92 ms |
15928 KB |
Output is correct |
7 |
Correct |
86 ms |
15704 KB |
Output is correct |
8 |
Correct |
76 ms |
15356 KB |
Output is correct |
9 |
Correct |
63 ms |
15072 KB |
Output is correct |
10 |
Correct |
63 ms |
14748 KB |
Output is correct |
11 |
Correct |
79 ms |
15076 KB |
Output is correct |
12 |
Correct |
81 ms |
15076 KB |
Output is correct |
13 |
Correct |
81 ms |
16352 KB |
Output is correct |
14 |
Correct |
80 ms |
16340 KB |
Output is correct |
15 |
Correct |
83 ms |
15904 KB |
Output is correct |
16 |
Correct |
88 ms |
15176 KB |
Output is correct |
17 |
Correct |
87 ms |
16868 KB |
Output is correct |
18 |
Correct |
86 ms |
15836 KB |
Output is correct |
19 |
Correct |
86 ms |
15580 KB |
Output is correct |
20 |
Correct |
80 ms |
16096 KB |
Output is correct |
21 |
Correct |
90 ms |
15572 KB |
Output is correct |
22 |
Correct |
84 ms |
16100 KB |
Output is correct |
23 |
Correct |
75 ms |
15836 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
65 ms |
13604 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
6488 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |