#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
int n,m;
pair<int,int> e[100001];
int w[100001];
int q;
int t[100001],a[100001],b[100001];
void read()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int x,y,c;
cin>>x>>y>>c;
w[i]=c;
e[i]={x,y};
}
cin>>q;
for(int i=1;i<=q;i++)
{
cin>>t[i]>>a[i]>>b[i];
}
}
const int block=1000;
int used[100001];
vector<int> unch,qr,upd[100001];
bool cmp1(int x,int y)
{
return w[x]>w[y];
}
bool cmp2(int x,int y)
{
return b[x]>b[y];
}
struct rolling
{
int x,szx,y,szy,rnkx,rnky;
rolling(){}
rolling(int _x,int _szx,int rx,int _y,int _szy,int ry)
{
x=_x;
szx=_szx;
y=_y;
szy=_szy;
rnkx=rx;
rnky=ry;
}
};
stack<rolling> s;
int ans[100001],rnk[100001],par[100001],sz[100001];
void init()
{
for(int i=1;i<=n;i++)
{
sz[i]=1;
rnk[i]=0;
par[i]=i;
}
}
int find_parent(int x)
{
if(x==par[x])return x;
return find_parent(par[x]);
}
void unite(int idx)// idx is the index of the edge in e[]
{
int i=e[idx].first;
int j=e[idx].second;
i=find_parent(i);
j=find_parent(j);
if(i!=j)
{
if(rnk[i]>rnk[j])
swap(i,j);
s.push({i,sz[i],rnk[i],j,sz[j],rnk[j]});
par[i]=j;
sz[j]+=sz[i];
if(rnk[j]==rnk[i])
rnk[j]++;
}
}
void rollback(int prsz)
{
while(s.size()!=prsz)
{
rolling r=s.top();
s.pop();
par[r.x]=r.x;
sz[r.x]=r.szx;
par[r.y]=r.y;
sz[r.y]=r.szy;
}
}
void solve()
{
for(int l=1;l<=q;l+=block)
{
init();
unch.clear();// the unchanged edges' indexes
qr.clear();// the indexes of the queries in the original order
int r=l+block-1;
for(int i=l;i<=r;i++)
{
if(t[i]==1)
used[a[i]]=l;
}
for(int i=1;i<=m;i++)
{
if(used[i]!=l)
unch.push_back(i);
}
sort(unch.begin(),unch.end(),cmp1);
for(int i=l;i<=r;i++)
{
if(t[i]==1)
w[a[i]]=b[i];
if(t[i]==2)
{
qr.push_back(i);
for(int j=l;j<=r;j++)
if(t[j]==1&&w[a[j]]>=b[i])
upd[i].push_back(a[j]);
}
}
// sort queries by weight of car big to small, then add edges >=
// from the unchanged ones and the updates
// afterwards rollback to before the updates and go on
sort(qr.begin(),qr.end(),cmp2);
int j=0;
for(int i=0;i<qr.size();i++)
{
int lim=b[qr[i]];
while(j<unch.size()&&w[unch[j]]>=lim)
{
unite(unch[j]);
j++;
}
int prsz=s.size();
for(int j=0;j<upd[qr[i]].size();j++)
unite(upd[qr[i]][j]);
ans[qr[i]]=sz[find_parent(a[qr[i]])];
rollback(prsz);
}
}
for(int i=1;i<=q;i++)
if(t[i]==2)
cout<<ans[i]<<endl;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
read();
solve();
return 0;
}
Compilation message
bridges.cpp: In function 'void rollback(int)':
bridges.cpp:95:19: warning: comparison of integer expressions of different signedness: 'std::stack<rolling>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
95 | while(s.size()!=prsz)
| ~~~~~~~~^~~~~~
bridges.cpp: In function 'void solve()':
bridges.cpp:149:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
149 | for(int i=0;i<qr.size();i++)
| ~^~~~~~~~~~
bridges.cpp:152:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
152 | while(j<unch.size()&&w[unch[j]]>=lim)
| ~^~~~~~~~~~~~
bridges.cpp:159:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
159 | for(int j=0;j<upd[qr[i]].size();j++)
| ~^~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
6492 KB |
Output is correct |
2 |
Correct |
2 ms |
6492 KB |
Output is correct |
3 |
Correct |
40 ms |
13132 KB |
Output is correct |
4 |
Correct |
10 ms |
6492 KB |
Output is correct |
5 |
Correct |
48 ms |
13808 KB |
Output is correct |
6 |
Correct |
33 ms |
14200 KB |
Output is correct |
7 |
Correct |
39 ms |
14416 KB |
Output is correct |
8 |
Correct |
50 ms |
12564 KB |
Output is correct |
9 |
Correct |
48 ms |
18524 KB |
Output is correct |
10 |
Correct |
48 ms |
13464 KB |
Output is correct |
11 |
Correct |
48 ms |
13136 KB |
Output is correct |
12 |
Correct |
56 ms |
15648 KB |
Output is correct |
13 |
Correct |
55 ms |
13648 KB |
Output is correct |
14 |
Correct |
53 ms |
13036 KB |
Output is correct |
15 |
Correct |
55 ms |
13652 KB |
Output is correct |
16 |
Correct |
40 ms |
16720 KB |
Output is correct |
17 |
Correct |
43 ms |
15700 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1345 ms |
195788 KB |
Output is correct |
2 |
Correct |
1377 ms |
195984 KB |
Output is correct |
3 |
Correct |
1379 ms |
194656 KB |
Output is correct |
4 |
Correct |
1390 ms |
195756 KB |
Output is correct |
5 |
Correct |
1399 ms |
196376 KB |
Output is correct |
6 |
Correct |
1574 ms |
252552 KB |
Output is correct |
7 |
Correct |
1541 ms |
250720 KB |
Output is correct |
8 |
Correct |
1566 ms |
248572 KB |
Output is correct |
9 |
Correct |
104 ms |
6620 KB |
Output is correct |
10 |
Correct |
930 ms |
223332 KB |
Output is correct |
11 |
Correct |
872 ms |
222188 KB |
Output is correct |
12 |
Correct |
1145 ms |
177280 KB |
Output is correct |
13 |
Correct |
1140 ms |
169264 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1142 ms |
153184 KB |
Output is correct |
2 |
Correct |
752 ms |
118492 KB |
Output is correct |
3 |
Correct |
1210 ms |
181472 KB |
Output is correct |
4 |
Correct |
1096 ms |
152648 KB |
Output is correct |
5 |
Correct |
89 ms |
6600 KB |
Output is correct |
6 |
Correct |
1212 ms |
171592 KB |
Output is correct |
7 |
Correct |
1020 ms |
143896 KB |
Output is correct |
8 |
Correct |
907 ms |
127916 KB |
Output is correct |
9 |
Correct |
747 ms |
121812 KB |
Output is correct |
10 |
Correct |
766 ms |
109348 KB |
Output is correct |
11 |
Correct |
766 ms |
116088 KB |
Output is correct |
12 |
Correct |
662 ms |
105016 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1641 ms |
129016 KB |
Output is correct |
2 |
Correct |
90 ms |
6600 KB |
Output is correct |
3 |
Correct |
167 ms |
7572 KB |
Output is correct |
4 |
Correct |
86 ms |
7520 KB |
Output is correct |
5 |
Correct |
948 ms |
127572 KB |
Output is correct |
6 |
Correct |
1638 ms |
129048 KB |
Output is correct |
7 |
Correct |
925 ms |
127512 KB |
Output is correct |
8 |
Correct |
839 ms |
128544 KB |
Output is correct |
9 |
Correct |
851 ms |
128308 KB |
Output is correct |
10 |
Correct |
866 ms |
128708 KB |
Output is correct |
11 |
Correct |
1248 ms |
130676 KB |
Output is correct |
12 |
Correct |
1270 ms |
129128 KB |
Output is correct |
13 |
Correct |
1265 ms |
128992 KB |
Output is correct |
14 |
Correct |
871 ms |
127104 KB |
Output is correct |
15 |
Correct |
954 ms |
127048 KB |
Output is correct |
16 |
Correct |
1650 ms |
128592 KB |
Output is correct |
17 |
Correct |
1719 ms |
130576 KB |
Output is correct |
18 |
Correct |
1675 ms |
131056 KB |
Output is correct |
19 |
Correct |
1778 ms |
129136 KB |
Output is correct |
20 |
Correct |
1402 ms |
131100 KB |
Output is correct |
21 |
Correct |
1449 ms |
131124 KB |
Output is correct |
22 |
Correct |
1629 ms |
128200 KB |
Output is correct |
23 |
Correct |
960 ms |
116972 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1345 ms |
195788 KB |
Output is correct |
2 |
Correct |
1377 ms |
195984 KB |
Output is correct |
3 |
Correct |
1379 ms |
194656 KB |
Output is correct |
4 |
Correct |
1390 ms |
195756 KB |
Output is correct |
5 |
Correct |
1399 ms |
196376 KB |
Output is correct |
6 |
Correct |
1574 ms |
252552 KB |
Output is correct |
7 |
Correct |
1541 ms |
250720 KB |
Output is correct |
8 |
Correct |
1566 ms |
248572 KB |
Output is correct |
9 |
Correct |
104 ms |
6620 KB |
Output is correct |
10 |
Correct |
930 ms |
223332 KB |
Output is correct |
11 |
Correct |
872 ms |
222188 KB |
Output is correct |
12 |
Correct |
1145 ms |
177280 KB |
Output is correct |
13 |
Correct |
1140 ms |
169264 KB |
Output is correct |
14 |
Correct |
1142 ms |
153184 KB |
Output is correct |
15 |
Correct |
752 ms |
118492 KB |
Output is correct |
16 |
Correct |
1210 ms |
181472 KB |
Output is correct |
17 |
Correct |
1096 ms |
152648 KB |
Output is correct |
18 |
Correct |
89 ms |
6600 KB |
Output is correct |
19 |
Correct |
1212 ms |
171592 KB |
Output is correct |
20 |
Correct |
1020 ms |
143896 KB |
Output is correct |
21 |
Correct |
907 ms |
127916 KB |
Output is correct |
22 |
Correct |
747 ms |
121812 KB |
Output is correct |
23 |
Correct |
766 ms |
109348 KB |
Output is correct |
24 |
Correct |
766 ms |
116088 KB |
Output is correct |
25 |
Correct |
662 ms |
105016 KB |
Output is correct |
26 |
Correct |
1467 ms |
198656 KB |
Output is correct |
27 |
Correct |
1537 ms |
228196 KB |
Output is correct |
28 |
Correct |
1427 ms |
195132 KB |
Output is correct |
29 |
Correct |
1104 ms |
153624 KB |
Output is correct |
30 |
Correct |
1504 ms |
212836 KB |
Output is correct |
31 |
Correct |
1510 ms |
217184 KB |
Output is correct |
32 |
Correct |
1528 ms |
215580 KB |
Output is correct |
33 |
Correct |
1412 ms |
197820 KB |
Output is correct |
34 |
Correct |
1391 ms |
197404 KB |
Output is correct |
35 |
Correct |
1448 ms |
195696 KB |
Output is correct |
36 |
Correct |
1125 ms |
158788 KB |
Output is correct |
37 |
Correct |
1142 ms |
159420 KB |
Output is correct |
38 |
Correct |
1140 ms |
157732 KB |
Output is correct |
39 |
Correct |
938 ms |
144840 KB |
Output is correct |
40 |
Correct |
960 ms |
144304 KB |
Output is correct |
41 |
Correct |
931 ms |
141664 KB |
Output is correct |
42 |
Correct |
876 ms |
136368 KB |
Output is correct |
43 |
Correct |
860 ms |
135600 KB |
Output is correct |
44 |
Correct |
835 ms |
136648 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
6492 KB |
Output is correct |
2 |
Correct |
2 ms |
6492 KB |
Output is correct |
3 |
Correct |
40 ms |
13132 KB |
Output is correct |
4 |
Correct |
10 ms |
6492 KB |
Output is correct |
5 |
Correct |
48 ms |
13808 KB |
Output is correct |
6 |
Correct |
33 ms |
14200 KB |
Output is correct |
7 |
Correct |
39 ms |
14416 KB |
Output is correct |
8 |
Correct |
50 ms |
12564 KB |
Output is correct |
9 |
Correct |
48 ms |
18524 KB |
Output is correct |
10 |
Correct |
48 ms |
13464 KB |
Output is correct |
11 |
Correct |
48 ms |
13136 KB |
Output is correct |
12 |
Correct |
56 ms |
15648 KB |
Output is correct |
13 |
Correct |
55 ms |
13648 KB |
Output is correct |
14 |
Correct |
53 ms |
13036 KB |
Output is correct |
15 |
Correct |
55 ms |
13652 KB |
Output is correct |
16 |
Correct |
40 ms |
16720 KB |
Output is correct |
17 |
Correct |
43 ms |
15700 KB |
Output is correct |
18 |
Correct |
1345 ms |
195788 KB |
Output is correct |
19 |
Correct |
1377 ms |
195984 KB |
Output is correct |
20 |
Correct |
1379 ms |
194656 KB |
Output is correct |
21 |
Correct |
1390 ms |
195756 KB |
Output is correct |
22 |
Correct |
1399 ms |
196376 KB |
Output is correct |
23 |
Correct |
1574 ms |
252552 KB |
Output is correct |
24 |
Correct |
1541 ms |
250720 KB |
Output is correct |
25 |
Correct |
1566 ms |
248572 KB |
Output is correct |
26 |
Correct |
104 ms |
6620 KB |
Output is correct |
27 |
Correct |
930 ms |
223332 KB |
Output is correct |
28 |
Correct |
872 ms |
222188 KB |
Output is correct |
29 |
Correct |
1145 ms |
177280 KB |
Output is correct |
30 |
Correct |
1140 ms |
169264 KB |
Output is correct |
31 |
Correct |
1142 ms |
153184 KB |
Output is correct |
32 |
Correct |
752 ms |
118492 KB |
Output is correct |
33 |
Correct |
1210 ms |
181472 KB |
Output is correct |
34 |
Correct |
1096 ms |
152648 KB |
Output is correct |
35 |
Correct |
89 ms |
6600 KB |
Output is correct |
36 |
Correct |
1212 ms |
171592 KB |
Output is correct |
37 |
Correct |
1020 ms |
143896 KB |
Output is correct |
38 |
Correct |
907 ms |
127916 KB |
Output is correct |
39 |
Correct |
747 ms |
121812 KB |
Output is correct |
40 |
Correct |
766 ms |
109348 KB |
Output is correct |
41 |
Correct |
766 ms |
116088 KB |
Output is correct |
42 |
Correct |
662 ms |
105016 KB |
Output is correct |
43 |
Correct |
1641 ms |
129016 KB |
Output is correct |
44 |
Correct |
90 ms |
6600 KB |
Output is correct |
45 |
Correct |
167 ms |
7572 KB |
Output is correct |
46 |
Correct |
86 ms |
7520 KB |
Output is correct |
47 |
Correct |
948 ms |
127572 KB |
Output is correct |
48 |
Correct |
1638 ms |
129048 KB |
Output is correct |
49 |
Correct |
925 ms |
127512 KB |
Output is correct |
50 |
Correct |
839 ms |
128544 KB |
Output is correct |
51 |
Correct |
851 ms |
128308 KB |
Output is correct |
52 |
Correct |
866 ms |
128708 KB |
Output is correct |
53 |
Correct |
1248 ms |
130676 KB |
Output is correct |
54 |
Correct |
1270 ms |
129128 KB |
Output is correct |
55 |
Correct |
1265 ms |
128992 KB |
Output is correct |
56 |
Correct |
871 ms |
127104 KB |
Output is correct |
57 |
Correct |
954 ms |
127048 KB |
Output is correct |
58 |
Correct |
1650 ms |
128592 KB |
Output is correct |
59 |
Correct |
1719 ms |
130576 KB |
Output is correct |
60 |
Correct |
1675 ms |
131056 KB |
Output is correct |
61 |
Correct |
1778 ms |
129136 KB |
Output is correct |
62 |
Correct |
1402 ms |
131100 KB |
Output is correct |
63 |
Correct |
1449 ms |
131124 KB |
Output is correct |
64 |
Correct |
1629 ms |
128200 KB |
Output is correct |
65 |
Correct |
960 ms |
116972 KB |
Output is correct |
66 |
Correct |
1467 ms |
198656 KB |
Output is correct |
67 |
Correct |
1537 ms |
228196 KB |
Output is correct |
68 |
Correct |
1427 ms |
195132 KB |
Output is correct |
69 |
Correct |
1104 ms |
153624 KB |
Output is correct |
70 |
Correct |
1504 ms |
212836 KB |
Output is correct |
71 |
Correct |
1510 ms |
217184 KB |
Output is correct |
72 |
Correct |
1528 ms |
215580 KB |
Output is correct |
73 |
Correct |
1412 ms |
197820 KB |
Output is correct |
74 |
Correct |
1391 ms |
197404 KB |
Output is correct |
75 |
Correct |
1448 ms |
195696 KB |
Output is correct |
76 |
Correct |
1125 ms |
158788 KB |
Output is correct |
77 |
Correct |
1142 ms |
159420 KB |
Output is correct |
78 |
Correct |
1140 ms |
157732 KB |
Output is correct |
79 |
Correct |
938 ms |
144840 KB |
Output is correct |
80 |
Correct |
960 ms |
144304 KB |
Output is correct |
81 |
Correct |
931 ms |
141664 KB |
Output is correct |
82 |
Correct |
876 ms |
136368 KB |
Output is correct |
83 |
Correct |
860 ms |
135600 KB |
Output is correct |
84 |
Correct |
835 ms |
136648 KB |
Output is correct |
85 |
Correct |
2072 ms |
197932 KB |
Output is correct |
86 |
Correct |
202 ms |
15920 KB |
Output is correct |
87 |
Correct |
109 ms |
20432 KB |
Output is correct |
88 |
Correct |
1226 ms |
209720 KB |
Output is correct |
89 |
Correct |
2021 ms |
198292 KB |
Output is correct |
90 |
Correct |
1237 ms |
219976 KB |
Output is correct |
91 |
Correct |
1425 ms |
197120 KB |
Output is correct |
92 |
Correct |
1407 ms |
196724 KB |
Output is correct |
93 |
Correct |
1727 ms |
236600 KB |
Output is correct |
94 |
Correct |
1706 ms |
199424 KB |
Output is correct |
95 |
Correct |
1710 ms |
200892 KB |
Output is correct |
96 |
Correct |
1687 ms |
239620 KB |
Output is correct |
97 |
Correct |
1075 ms |
164404 KB |
Output is correct |
98 |
Correct |
1056 ms |
160880 KB |
Output is correct |
99 |
Correct |
2045 ms |
200512 KB |
Output is correct |
100 |
Correct |
2099 ms |
200916 KB |
Output is correct |
101 |
Correct |
2183 ms |
201620 KB |
Output is correct |
102 |
Correct |
2112 ms |
201544 KB |
Output is correct |
103 |
Correct |
1855 ms |
244884 KB |
Output is correct |
104 |
Correct |
1851 ms |
246376 KB |
Output is correct |
105 |
Correct |
1541 ms |
172368 KB |
Output is correct |
106 |
Correct |
1269 ms |
153996 KB |
Output is correct |
107 |
Correct |
1552 ms |
180860 KB |
Output is correct |
108 |
Correct |
1937 ms |
231900 KB |
Output is correct |
109 |
Correct |
1382 ms |
225612 KB |
Output is correct |