#include<bits/stdc++.h>
using namespace std ;
const int MX = 1e5 + 5 , block = 911 ;
struct query
{
int type = 0 , vertice = 0 , edge = 0 , weight = 0 , idx = 0 ;
};
bool cmp(pair<int,int> &a , pair<int,int> &b)
{
if(a.first!=b.first) return a.first > b.first ;
return a.second > b.second ;
}
bool cmp1(query &a , query &b)
{
if(a.weight!=b.weight) return a.weight > b.weight ;
return a.idx < b.idx ;
}
vector<query> temp ;
vector<pair<int,int> > edges , edg ;
int ans[MX] , typ[MX] , val[MX] , vis[MX] , cur[MX] , temp_siz , n , m ;
struct dsu_rollback
{
int u = 0 , v = 0 , siz_u = 0 , siz_v = 0 ;
};
struct dsu
{
vector<int> par , siz ;
stack<dsu_rollback> s ;
void init(int n)
{
par = vector<int> (n+5,0) ;
siz = vector<int> (n+5,0) ;
for(int i = 1 ; i <= n ; ++i)
{
par[i] = i ;
siz[i] = 1 ;
}
}
int find_root(int a)
{
if(par[a]==a) return a ;
return find_root(par[a]) ;
}
int union_edge(int a , int b)
{
int root_a = find_root(a) , root_b = find_root(b) ;
if(root_a==root_b) return 0 ;
if(siz[root_b]>siz[root_a]) swap(root_a,root_b) ;
s.push({root_a,root_b,siz[root_a],siz[root_b]}) ;
par[root_b] = root_a ;
siz[root_a] += siz[root_b] ;
return 1 ;
}
void rollback()
{
if(s.empty()) return ;
dsu_rollback cur = s.top() ;
s.pop() ;
par[cur.u] = cur.u ;
siz[cur.u] = cur.siz_u ;
par[cur.v] = cur.v ;
siz[cur.v] = cur.siz_v ;
}
int find_siz(int x)
{
return siz[find_root(x)] ;
}
};
void process()
{
dsu D ;
D.init(n) ;
vector<query> upd , out ;
vector<int> unused ;
unused.reserve(block) ;
upd.reserve(block) ;
out.reserve(block) ;
for(query &q : temp)
{
if(q.type==1)
{
vis[q.edge] = 1 ;
upd.emplace_back(q) ;
}
else out.emplace_back(q) ;
}
for(int i = 1 ; i <= m ; ++i)
{
if(vis[i]) unused.emplace_back(i) ;
}
sort(out.begin(),out.end(),cmp1) ;
sort(edg.begin(),edg.end(),cmp) ;
int cr = 0 ;
for(query &q : out)
{
while((cr<m) && (edg[cr].first>=q.weight))
{
if(!vis[edg[cr].second]) D.union_edge(edges[edg[cr].second].first,edges[edg[cr].second].second) ;
++cr ;
}
int rollback = 0 ;
for(query &p : upd)
{
if(p.idx>q.idx) break ;
cur[p.edge] = p.weight ;
}
for(query &p : upd)
{
if(p.idx>q.idx) break ;
if(cur[p.edge]>=q.weight)
{
rollback += D.union_edge(edges[p.edge].first,edges[p.edge].second) ;
cur[p.edge] = -1 ;
}
}
for(int &i : unused)
{
if(cur[i]) continue ;
if(val[i]>=q.weight)
{
rollback += D.union_edge(edges[i].first,edges[i].second) ;
cur[i] = -1 ;
}
}
ans[q.idx] = D.find_siz(q.vertice) ;
while(rollback)
{
D.rollback() ;
--rollback ;
}
for(int &i : unused)
{
cur[i] = 0 ;
}
}
for(query &q : upd)
{
val[q.edge] = q.weight ;
}
for(int i = 0 ; i < m ; ++i)
{
if(vis[edg[i].second])
{
edg[i].first = val[edg[i].second] , vis[edg[i].second] = 0 , cur[i] = 0 ;
}
}
temp.clear() , temp_siz = 0 ;
}
int main()
{
scanf("%d%d",&n,&m) ;
edges.reserve(MX) ;
edges.emplace_back(make_pair(0,0)) ;
temp.reserve(block) ;
for(int i = 1 ; i <= m ; ++i)
{
int a , b , d ;
scanf("%d%d%d",&a,&b,&d) ;
edges.emplace_back(make_pair(a,b)) ;
val[i] = d ;
edg.emplace_back(make_pair(val[i],i)) ;
}
int q ;
scanf("%d",&q) ;
for(int i = 1 ; i <= q ; ++i)
{
int type ;
scanf("%d",&type) ;
typ[i] = type ;
if(type==1)
{
int b , r ;
scanf("%d%d",&b,&r) ;
query f = {1,0,b,r,i} ;
temp.emplace_back(f) , ++temp_siz ;
}
else
{
int s , w ;
scanf("%d%d",&s,&w) ;
query f = {2,s,0,w,i} ;
temp.emplace_back(f) , ++temp_siz ;
}
if(temp_siz==block) process() ;
}
if(temp_siz) process() ;
for(int i = 1 ; i <= q ; ++i)
{
if(typ[i]==2) printf("%d\n",ans[i]) ;
}
return 0 ;
}
Compilation message
bridges.cpp: In function 'int main()':
bridges.cpp:162:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
162 | scanf("%d%d",&n,&m) ;
| ~~~~~^~~~~~~~~~~~~~
bridges.cpp:169:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
169 | scanf("%d%d%d",&a,&b,&d) ;
| ~~~~~^~~~~~~~~~~~~~~~~~~
bridges.cpp:175:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
175 | scanf("%d",&q) ;
| ~~~~~^~~~~~~~~
bridges.cpp:179:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
179 | scanf("%d",&type) ;
| ~~~~~^~~~~~~~~~~~
bridges.cpp:184:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
184 | scanf("%d%d",&b,&r) ;
| ~~~~~^~~~~~~~~~~~~~
bridges.cpp:191:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
191 | scanf("%d%d",&s,&w) ;
| ~~~~~^~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
33 ms |
468 KB |
Output is correct |
4 |
Correct |
5 ms |
412 KB |
Output is correct |
5 |
Correct |
15 ms |
468 KB |
Output is correct |
6 |
Correct |
13 ms |
468 KB |
Output is correct |
7 |
Correct |
18 ms |
432 KB |
Output is correct |
8 |
Correct |
19 ms |
456 KB |
Output is correct |
9 |
Correct |
20 ms |
468 KB |
Output is correct |
10 |
Correct |
20 ms |
468 KB |
Output is correct |
11 |
Correct |
20 ms |
396 KB |
Output is correct |
12 |
Correct |
22 ms |
536 KB |
Output is correct |
13 |
Correct |
30 ms |
452 KB |
Output is correct |
14 |
Correct |
23 ms |
408 KB |
Output is correct |
15 |
Correct |
20 ms |
596 KB |
Output is correct |
16 |
Correct |
20 ms |
404 KB |
Output is correct |
17 |
Correct |
19 ms |
452 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1551 ms |
4048 KB |
Output is correct |
2 |
Correct |
1566 ms |
3780 KB |
Output is correct |
3 |
Correct |
1563 ms |
3812 KB |
Output is correct |
4 |
Correct |
1582 ms |
3868 KB |
Output is correct |
5 |
Correct |
1588 ms |
3828 KB |
Output is correct |
6 |
Correct |
2145 ms |
4080 KB |
Output is correct |
7 |
Correct |
2171 ms |
4196 KB |
Output is correct |
8 |
Correct |
2177 ms |
4072 KB |
Output is correct |
9 |
Correct |
46 ms |
1244 KB |
Output is correct |
10 |
Correct |
1493 ms |
4032 KB |
Output is correct |
11 |
Correct |
1415 ms |
3864 KB |
Output is correct |
12 |
Correct |
1337 ms |
4132 KB |
Output is correct |
13 |
Correct |
1277 ms |
3768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1220 ms |
2916 KB |
Output is correct |
2 |
Correct |
897 ms |
1736 KB |
Output is correct |
3 |
Correct |
1369 ms |
3004 KB |
Output is correct |
4 |
Correct |
1191 ms |
2900 KB |
Output is correct |
5 |
Correct |
41 ms |
1312 KB |
Output is correct |
6 |
Correct |
1378 ms |
2984 KB |
Output is correct |
7 |
Correct |
1116 ms |
2976 KB |
Output is correct |
8 |
Correct |
1028 ms |
3084 KB |
Output is correct |
9 |
Correct |
796 ms |
3108 KB |
Output is correct |
10 |
Correct |
726 ms |
3036 KB |
Output is correct |
11 |
Correct |
818 ms |
2892 KB |
Output is correct |
12 |
Correct |
708 ms |
2844 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1284 ms |
4740 KB |
Output is correct |
2 |
Correct |
46 ms |
1304 KB |
Output is correct |
3 |
Correct |
131 ms |
2408 KB |
Output is correct |
4 |
Correct |
123 ms |
2412 KB |
Output is correct |
5 |
Correct |
1071 ms |
4780 KB |
Output is correct |
6 |
Correct |
1281 ms |
4820 KB |
Output is correct |
7 |
Correct |
1087 ms |
4744 KB |
Output is correct |
8 |
Correct |
728 ms |
3468 KB |
Output is correct |
9 |
Correct |
734 ms |
3424 KB |
Output is correct |
10 |
Correct |
699 ms |
3300 KB |
Output is correct |
11 |
Correct |
989 ms |
4012 KB |
Output is correct |
12 |
Correct |
961 ms |
4232 KB |
Output is correct |
13 |
Correct |
998 ms |
4328 KB |
Output is correct |
14 |
Correct |
1107 ms |
4840 KB |
Output is correct |
15 |
Correct |
1119 ms |
4800 KB |
Output is correct |
16 |
Correct |
1257 ms |
4640 KB |
Output is correct |
17 |
Correct |
1263 ms |
4724 KB |
Output is correct |
18 |
Correct |
1283 ms |
4724 KB |
Output is correct |
19 |
Correct |
1306 ms |
4660 KB |
Output is correct |
20 |
Correct |
1099 ms |
4556 KB |
Output is correct |
21 |
Correct |
1081 ms |
4540 KB |
Output is correct |
22 |
Correct |
1175 ms |
4880 KB |
Output is correct |
23 |
Correct |
983 ms |
4448 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1551 ms |
4048 KB |
Output is correct |
2 |
Correct |
1566 ms |
3780 KB |
Output is correct |
3 |
Correct |
1563 ms |
3812 KB |
Output is correct |
4 |
Correct |
1582 ms |
3868 KB |
Output is correct |
5 |
Correct |
1588 ms |
3828 KB |
Output is correct |
6 |
Correct |
2145 ms |
4080 KB |
Output is correct |
7 |
Correct |
2171 ms |
4196 KB |
Output is correct |
8 |
Correct |
2177 ms |
4072 KB |
Output is correct |
9 |
Correct |
46 ms |
1244 KB |
Output is correct |
10 |
Correct |
1493 ms |
4032 KB |
Output is correct |
11 |
Correct |
1415 ms |
3864 KB |
Output is correct |
12 |
Correct |
1337 ms |
4132 KB |
Output is correct |
13 |
Correct |
1277 ms |
3768 KB |
Output is correct |
14 |
Correct |
1220 ms |
2916 KB |
Output is correct |
15 |
Correct |
897 ms |
1736 KB |
Output is correct |
16 |
Correct |
1369 ms |
3004 KB |
Output is correct |
17 |
Correct |
1191 ms |
2900 KB |
Output is correct |
18 |
Correct |
41 ms |
1312 KB |
Output is correct |
19 |
Correct |
1378 ms |
2984 KB |
Output is correct |
20 |
Correct |
1116 ms |
2976 KB |
Output is correct |
21 |
Correct |
1028 ms |
3084 KB |
Output is correct |
22 |
Correct |
796 ms |
3108 KB |
Output is correct |
23 |
Correct |
726 ms |
3036 KB |
Output is correct |
24 |
Correct |
818 ms |
2892 KB |
Output is correct |
25 |
Correct |
708 ms |
2844 KB |
Output is correct |
26 |
Correct |
1474 ms |
3924 KB |
Output is correct |
27 |
Correct |
1838 ms |
4044 KB |
Output is correct |
28 |
Correct |
1546 ms |
4060 KB |
Output is correct |
29 |
Correct |
1182 ms |
3928 KB |
Output is correct |
30 |
Correct |
1766 ms |
4036 KB |
Output is correct |
31 |
Correct |
1783 ms |
3960 KB |
Output is correct |
32 |
Correct |
1913 ms |
3872 KB |
Output is correct |
33 |
Correct |
1663 ms |
3808 KB |
Output is correct |
34 |
Correct |
1565 ms |
3968 KB |
Output is correct |
35 |
Correct |
1560 ms |
3920 KB |
Output is correct |
36 |
Correct |
1225 ms |
3852 KB |
Output is correct |
37 |
Correct |
1219 ms |
3816 KB |
Output is correct |
38 |
Correct |
1194 ms |
3908 KB |
Output is correct |
39 |
Correct |
966 ms |
3880 KB |
Output is correct |
40 |
Correct |
951 ms |
3868 KB |
Output is correct |
41 |
Correct |
952 ms |
3976 KB |
Output is correct |
42 |
Correct |
921 ms |
3784 KB |
Output is correct |
43 |
Correct |
910 ms |
3820 KB |
Output is correct |
44 |
Correct |
899 ms |
3760 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
33 ms |
468 KB |
Output is correct |
4 |
Correct |
5 ms |
412 KB |
Output is correct |
5 |
Correct |
15 ms |
468 KB |
Output is correct |
6 |
Correct |
13 ms |
468 KB |
Output is correct |
7 |
Correct |
18 ms |
432 KB |
Output is correct |
8 |
Correct |
19 ms |
456 KB |
Output is correct |
9 |
Correct |
20 ms |
468 KB |
Output is correct |
10 |
Correct |
20 ms |
468 KB |
Output is correct |
11 |
Correct |
20 ms |
396 KB |
Output is correct |
12 |
Correct |
22 ms |
536 KB |
Output is correct |
13 |
Correct |
30 ms |
452 KB |
Output is correct |
14 |
Correct |
23 ms |
408 KB |
Output is correct |
15 |
Correct |
20 ms |
596 KB |
Output is correct |
16 |
Correct |
20 ms |
404 KB |
Output is correct |
17 |
Correct |
19 ms |
452 KB |
Output is correct |
18 |
Correct |
1551 ms |
4048 KB |
Output is correct |
19 |
Correct |
1566 ms |
3780 KB |
Output is correct |
20 |
Correct |
1563 ms |
3812 KB |
Output is correct |
21 |
Correct |
1582 ms |
3868 KB |
Output is correct |
22 |
Correct |
1588 ms |
3828 KB |
Output is correct |
23 |
Correct |
2145 ms |
4080 KB |
Output is correct |
24 |
Correct |
2171 ms |
4196 KB |
Output is correct |
25 |
Correct |
2177 ms |
4072 KB |
Output is correct |
26 |
Correct |
46 ms |
1244 KB |
Output is correct |
27 |
Correct |
1493 ms |
4032 KB |
Output is correct |
28 |
Correct |
1415 ms |
3864 KB |
Output is correct |
29 |
Correct |
1337 ms |
4132 KB |
Output is correct |
30 |
Correct |
1277 ms |
3768 KB |
Output is correct |
31 |
Correct |
1220 ms |
2916 KB |
Output is correct |
32 |
Correct |
897 ms |
1736 KB |
Output is correct |
33 |
Correct |
1369 ms |
3004 KB |
Output is correct |
34 |
Correct |
1191 ms |
2900 KB |
Output is correct |
35 |
Correct |
41 ms |
1312 KB |
Output is correct |
36 |
Correct |
1378 ms |
2984 KB |
Output is correct |
37 |
Correct |
1116 ms |
2976 KB |
Output is correct |
38 |
Correct |
1028 ms |
3084 KB |
Output is correct |
39 |
Correct |
796 ms |
3108 KB |
Output is correct |
40 |
Correct |
726 ms |
3036 KB |
Output is correct |
41 |
Correct |
818 ms |
2892 KB |
Output is correct |
42 |
Correct |
708 ms |
2844 KB |
Output is correct |
43 |
Correct |
1284 ms |
4740 KB |
Output is correct |
44 |
Correct |
46 ms |
1304 KB |
Output is correct |
45 |
Correct |
131 ms |
2408 KB |
Output is correct |
46 |
Correct |
123 ms |
2412 KB |
Output is correct |
47 |
Correct |
1071 ms |
4780 KB |
Output is correct |
48 |
Correct |
1281 ms |
4820 KB |
Output is correct |
49 |
Correct |
1087 ms |
4744 KB |
Output is correct |
50 |
Correct |
728 ms |
3468 KB |
Output is correct |
51 |
Correct |
734 ms |
3424 KB |
Output is correct |
52 |
Correct |
699 ms |
3300 KB |
Output is correct |
53 |
Correct |
989 ms |
4012 KB |
Output is correct |
54 |
Correct |
961 ms |
4232 KB |
Output is correct |
55 |
Correct |
998 ms |
4328 KB |
Output is correct |
56 |
Correct |
1107 ms |
4840 KB |
Output is correct |
57 |
Correct |
1119 ms |
4800 KB |
Output is correct |
58 |
Correct |
1257 ms |
4640 KB |
Output is correct |
59 |
Correct |
1263 ms |
4724 KB |
Output is correct |
60 |
Correct |
1283 ms |
4724 KB |
Output is correct |
61 |
Correct |
1306 ms |
4660 KB |
Output is correct |
62 |
Correct |
1099 ms |
4556 KB |
Output is correct |
63 |
Correct |
1081 ms |
4540 KB |
Output is correct |
64 |
Correct |
1175 ms |
4880 KB |
Output is correct |
65 |
Correct |
983 ms |
4448 KB |
Output is correct |
66 |
Correct |
1474 ms |
3924 KB |
Output is correct |
67 |
Correct |
1838 ms |
4044 KB |
Output is correct |
68 |
Correct |
1546 ms |
4060 KB |
Output is correct |
69 |
Correct |
1182 ms |
3928 KB |
Output is correct |
70 |
Correct |
1766 ms |
4036 KB |
Output is correct |
71 |
Correct |
1783 ms |
3960 KB |
Output is correct |
72 |
Correct |
1913 ms |
3872 KB |
Output is correct |
73 |
Correct |
1663 ms |
3808 KB |
Output is correct |
74 |
Correct |
1565 ms |
3968 KB |
Output is correct |
75 |
Correct |
1560 ms |
3920 KB |
Output is correct |
76 |
Correct |
1225 ms |
3852 KB |
Output is correct |
77 |
Correct |
1219 ms |
3816 KB |
Output is correct |
78 |
Correct |
1194 ms |
3908 KB |
Output is correct |
79 |
Correct |
966 ms |
3880 KB |
Output is correct |
80 |
Correct |
951 ms |
3868 KB |
Output is correct |
81 |
Correct |
952 ms |
3976 KB |
Output is correct |
82 |
Correct |
921 ms |
3784 KB |
Output is correct |
83 |
Correct |
910 ms |
3820 KB |
Output is correct |
84 |
Correct |
899 ms |
3760 KB |
Output is correct |
85 |
Correct |
2137 ms |
5336 KB |
Output is correct |
86 |
Correct |
207 ms |
3184 KB |
Output is correct |
87 |
Correct |
147 ms |
3192 KB |
Output is correct |
88 |
Correct |
1912 ms |
5520 KB |
Output is correct |
89 |
Correct |
2123 ms |
5212 KB |
Output is correct |
90 |
Correct |
1848 ms |
5228 KB |
Output is correct |
91 |
Correct |
1577 ms |
3880 KB |
Output is correct |
92 |
Correct |
1592 ms |
4104 KB |
Output is correct |
93 |
Correct |
2216 ms |
3916 KB |
Output is correct |
94 |
Correct |
1832 ms |
4668 KB |
Output is correct |
95 |
Correct |
1838 ms |
4636 KB |
Output is correct |
96 |
Correct |
1996 ms |
4716 KB |
Output is correct |
97 |
Correct |
1590 ms |
5220 KB |
Output is correct |
98 |
Correct |
1623 ms |
5028 KB |
Output is correct |
99 |
Correct |
2139 ms |
5404 KB |
Output is correct |
100 |
Correct |
2154 ms |
5372 KB |
Output is correct |
101 |
Correct |
2234 ms |
5352 KB |
Output is correct |
102 |
Correct |
2197 ms |
5548 KB |
Output is correct |
103 |
Correct |
2208 ms |
4816 KB |
Output is correct |
104 |
Correct |
2190 ms |
4852 KB |
Output is correct |
105 |
Correct |
1644 ms |
4596 KB |
Output is correct |
106 |
Correct |
1319 ms |
4412 KB |
Output is correct |
107 |
Correct |
1579 ms |
4968 KB |
Output is correct |
108 |
Correct |
2137 ms |
5024 KB |
Output is correct |
109 |
Correct |
1844 ms |
4528 KB |
Output is correct |