#pragma GCC optimize("O4")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
void setIO(string s) {
freopen((s + ".in").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
}
struct edge{
int a,b,w;
};
struct query{
int t,a,b,ind;
};
const int mxn=5e4+5;
const int mxm=1e5+5;
edge E[mxm];
query qs[mxm];
bool in[mxm];
bool visited[mxm];
int ans[mxm];
int W[mxm];
int K=333;
struct DSU{
vector<int> e;
stack<pair<int,int>> st;
DSU(int n){
e=vector<int>(n,-1);
}
void init(){
for(auto &v:e) v=-1;
while(!st.empty()) st.pop();
}
int find(int x){
return (e[x]<0?x:find(e[x]));
}
int sz(int x){
return -e[find(x)];
}
bool unite(int a,int b){
a=find(a);
b=find(b);
if(a==b) return false;
if(e[a]>e[b]) swap(a,b);
st.push({a,e[a]});
st.push({b,e[b]});
e[a]+=e[b];
e[b]=a;
return true;
}
void roll_back(int sz){
while(st.size()>sz){
pair<int,int> tmp=st.top();
st.pop();
e[tmp.f]=tmp.s;
}
}
};
bool comp(query x,query y){
return x.b>y.b;
}
bool comp2(edge x,edge y){
return x.w>y.w;
}
int main() {_
int n,m,q;
cin>>n>>m;
for(int i=0;i<m;i++){
int a,b,w;
cin>>a>>b>>w;
a--;
b--;
E[i]={a,b,w};
}
cin>>q;
K=500;
for(int i=0;i<q;i++){
int t,a,b;
cin>>t>>a>>b;
a--;
qs[i]={t,a,b,i};
}
DSU dsu(n);
for(int k=0;k<q;k+=K){
vector<query> tmp;
vector<int> ein;
for(int i=k;i<min(k+K,q);i++){
if(qs[i].t==1){
in[qs[i].a]=true;
ein.push_back(qs[i].a);
}
else{
tmp.push_back(qs[i]);
}
}
sort(all(tmp),comp);
vector<edge> ok;
for(int i=0;i<m;i++){
if(!in[i]) ok.push_back(E[i]);
}
sort(all(ok),comp2);
int pos=0;
for(int i=0;i<tmp.size();i++){
while(pos<ok.size() and ok[pos].w>=tmp[i].b){
dsu.unite(ok[pos].a,ok[pos].b);
pos++;
}
int prev_sz=dsu.st.size();
for(auto v:ein){
W[v]=E[v].w;
}
for(int j=k;j<tmp[i].ind;j++){
if(qs[j].t==1){
W[qs[j].a]=qs[j].b;
}
}
for(auto v:ein){
if(W[v]>=tmp[i].b){
dsu.unite(E[v].a,E[v].b);
}
}
ans[tmp[i].ind]=dsu.sz(tmp[i].a);
dsu.roll_back(prev_sz);
}
for(int i=k;i<min(k+K,q);i++){
if(qs[i].t==1){
E[qs[i].a].w=qs[i].b;
in[qs[i].a]=false;
}
}
dsu.roll_back(0);
}
for(int i=0;i<q;i++){
if(qs[i].t==2){
cout<<ans[i]<<'\n';
}
}
return 0;
}
//maybe its multiset not set
Compilation message
bridges.cpp: In member function 'void DSU::roll_back(int)':
bridges.cpp:62:24: warning: comparison of integer expressions of different signedness: 'std::stack<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
62 | while(st.size()>sz){
| ~~~~~~~~~^~~
bridges.cpp: In function 'int main()':
bridges.cpp:116:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
116 | for(int i=0;i<tmp.size();i++){
| ~^~~~~~~~~~~
bridges.cpp:117:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
117 | while(pos<ok.size() and ok[pos].w>=tmp[i].b){
| ~~~^~~~~~~~~~
bridges.cpp: In function 'void setIO(std::string)':
bridges.cpp:12:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
12 | freopen((s + ".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:13:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
13 | freopen((s + ".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
23 ms |
576 KB |
Output is correct |
4 |
Correct |
8 ms |
544 KB |
Output is correct |
5 |
Correct |
23 ms |
564 KB |
Output is correct |
6 |
Correct |
18 ms |
540 KB |
Output is correct |
7 |
Correct |
23 ms |
552 KB |
Output is correct |
8 |
Correct |
27 ms |
552 KB |
Output is correct |
9 |
Correct |
29 ms |
552 KB |
Output is correct |
10 |
Correct |
25 ms |
536 KB |
Output is correct |
11 |
Correct |
25 ms |
552 KB |
Output is correct |
12 |
Correct |
29 ms |
552 KB |
Output is correct |
13 |
Correct |
34 ms |
536 KB |
Output is correct |
14 |
Correct |
30 ms |
532 KB |
Output is correct |
15 |
Correct |
29 ms |
540 KB |
Output is correct |
16 |
Correct |
25 ms |
524 KB |
Output is correct |
17 |
Correct |
26 ms |
532 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1596 ms |
5088 KB |
Output is correct |
2 |
Correct |
1625 ms |
5064 KB |
Output is correct |
3 |
Correct |
1607 ms |
5080 KB |
Output is correct |
4 |
Correct |
1670 ms |
5092 KB |
Output is correct |
5 |
Correct |
1527 ms |
5096 KB |
Output is correct |
6 |
Correct |
2041 ms |
5440 KB |
Output is correct |
7 |
Correct |
1812 ms |
5668 KB |
Output is correct |
8 |
Correct |
1951 ms |
5496 KB |
Output is correct |
9 |
Correct |
47 ms |
2380 KB |
Output is correct |
10 |
Correct |
1077 ms |
5604 KB |
Output is correct |
11 |
Correct |
1108 ms |
5324 KB |
Output is correct |
12 |
Correct |
1426 ms |
5108 KB |
Output is correct |
13 |
Correct |
1557 ms |
5084 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1166 ms |
4240 KB |
Output is correct |
2 |
Correct |
588 ms |
2956 KB |
Output is correct |
3 |
Correct |
1195 ms |
4036 KB |
Output is correct |
4 |
Correct |
1120 ms |
4012 KB |
Output is correct |
5 |
Correct |
71 ms |
2368 KB |
Output is correct |
6 |
Correct |
1197 ms |
4028 KB |
Output is correct |
7 |
Correct |
1109 ms |
3924 KB |
Output is correct |
8 |
Correct |
945 ms |
4120 KB |
Output is correct |
9 |
Correct |
833 ms |
4192 KB |
Output is correct |
10 |
Correct |
831 ms |
4128 KB |
Output is correct |
11 |
Correct |
819 ms |
3952 KB |
Output is correct |
12 |
Correct |
804 ms |
3908 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2529 ms |
7496 KB |
Output is correct |
2 |
Correct |
65 ms |
2612 KB |
Output is correct |
3 |
Correct |
251 ms |
4768 KB |
Output is correct |
4 |
Correct |
125 ms |
4560 KB |
Output is correct |
5 |
Correct |
1467 ms |
7328 KB |
Output is correct |
6 |
Correct |
2561 ms |
7328 KB |
Output is correct |
7 |
Correct |
1489 ms |
7492 KB |
Output is correct |
8 |
Correct |
1188 ms |
5076 KB |
Output is correct |
9 |
Correct |
1253 ms |
5332 KB |
Output is correct |
10 |
Correct |
1169 ms |
5112 KB |
Output is correct |
11 |
Correct |
1750 ms |
6748 KB |
Output is correct |
12 |
Correct |
1720 ms |
6920 KB |
Output is correct |
13 |
Correct |
1761 ms |
6792 KB |
Output is correct |
14 |
Correct |
1251 ms |
7376 KB |
Output is correct |
15 |
Correct |
1286 ms |
7500 KB |
Output is correct |
16 |
Correct |
2310 ms |
7564 KB |
Output is correct |
17 |
Correct |
2392 ms |
7644 KB |
Output is correct |
18 |
Correct |
2308 ms |
7360 KB |
Output is correct |
19 |
Correct |
2313 ms |
7508 KB |
Output is correct |
20 |
Correct |
2024 ms |
7132 KB |
Output is correct |
21 |
Correct |
1939 ms |
7368 KB |
Output is correct |
22 |
Correct |
2268 ms |
7444 KB |
Output is correct |
23 |
Correct |
1336 ms |
7412 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1596 ms |
5088 KB |
Output is correct |
2 |
Correct |
1625 ms |
5064 KB |
Output is correct |
3 |
Correct |
1607 ms |
5080 KB |
Output is correct |
4 |
Correct |
1670 ms |
5092 KB |
Output is correct |
5 |
Correct |
1527 ms |
5096 KB |
Output is correct |
6 |
Correct |
2041 ms |
5440 KB |
Output is correct |
7 |
Correct |
1812 ms |
5668 KB |
Output is correct |
8 |
Correct |
1951 ms |
5496 KB |
Output is correct |
9 |
Correct |
47 ms |
2380 KB |
Output is correct |
10 |
Correct |
1077 ms |
5604 KB |
Output is correct |
11 |
Correct |
1108 ms |
5324 KB |
Output is correct |
12 |
Correct |
1426 ms |
5108 KB |
Output is correct |
13 |
Correct |
1557 ms |
5084 KB |
Output is correct |
14 |
Correct |
1166 ms |
4240 KB |
Output is correct |
15 |
Correct |
588 ms |
2956 KB |
Output is correct |
16 |
Correct |
1195 ms |
4036 KB |
Output is correct |
17 |
Correct |
1120 ms |
4012 KB |
Output is correct |
18 |
Correct |
71 ms |
2368 KB |
Output is correct |
19 |
Correct |
1197 ms |
4028 KB |
Output is correct |
20 |
Correct |
1109 ms |
3924 KB |
Output is correct |
21 |
Correct |
945 ms |
4120 KB |
Output is correct |
22 |
Correct |
833 ms |
4192 KB |
Output is correct |
23 |
Correct |
831 ms |
4128 KB |
Output is correct |
24 |
Correct |
819 ms |
3952 KB |
Output is correct |
25 |
Correct |
804 ms |
3908 KB |
Output is correct |
26 |
Correct |
1371 ms |
5404 KB |
Output is correct |
27 |
Correct |
1555 ms |
5612 KB |
Output is correct |
28 |
Correct |
1443 ms |
5296 KB |
Output is correct |
29 |
Correct |
1252 ms |
5212 KB |
Output is correct |
30 |
Correct |
1488 ms |
5932 KB |
Output is correct |
31 |
Correct |
1493 ms |
5176 KB |
Output is correct |
32 |
Correct |
1512 ms |
5108 KB |
Output is correct |
33 |
Correct |
1421 ms |
5096 KB |
Output is correct |
34 |
Correct |
1432 ms |
5092 KB |
Output is correct |
35 |
Correct |
1392 ms |
5392 KB |
Output is correct |
36 |
Correct |
1329 ms |
5192 KB |
Output is correct |
37 |
Correct |
1272 ms |
5284 KB |
Output is correct |
38 |
Correct |
1278 ms |
5204 KB |
Output is correct |
39 |
Correct |
1163 ms |
5084 KB |
Output is correct |
40 |
Correct |
1200 ms |
5112 KB |
Output is correct |
41 |
Correct |
1158 ms |
5192 KB |
Output is correct |
42 |
Correct |
1093 ms |
5604 KB |
Output is correct |
43 |
Correct |
1096 ms |
5324 KB |
Output is correct |
44 |
Correct |
1091 ms |
5432 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
23 ms |
576 KB |
Output is correct |
4 |
Correct |
8 ms |
544 KB |
Output is correct |
5 |
Correct |
23 ms |
564 KB |
Output is correct |
6 |
Correct |
18 ms |
540 KB |
Output is correct |
7 |
Correct |
23 ms |
552 KB |
Output is correct |
8 |
Correct |
27 ms |
552 KB |
Output is correct |
9 |
Correct |
29 ms |
552 KB |
Output is correct |
10 |
Correct |
25 ms |
536 KB |
Output is correct |
11 |
Correct |
25 ms |
552 KB |
Output is correct |
12 |
Correct |
29 ms |
552 KB |
Output is correct |
13 |
Correct |
34 ms |
536 KB |
Output is correct |
14 |
Correct |
30 ms |
532 KB |
Output is correct |
15 |
Correct |
29 ms |
540 KB |
Output is correct |
16 |
Correct |
25 ms |
524 KB |
Output is correct |
17 |
Correct |
26 ms |
532 KB |
Output is correct |
18 |
Correct |
1596 ms |
5088 KB |
Output is correct |
19 |
Correct |
1625 ms |
5064 KB |
Output is correct |
20 |
Correct |
1607 ms |
5080 KB |
Output is correct |
21 |
Correct |
1670 ms |
5092 KB |
Output is correct |
22 |
Correct |
1527 ms |
5096 KB |
Output is correct |
23 |
Correct |
2041 ms |
5440 KB |
Output is correct |
24 |
Correct |
1812 ms |
5668 KB |
Output is correct |
25 |
Correct |
1951 ms |
5496 KB |
Output is correct |
26 |
Correct |
47 ms |
2380 KB |
Output is correct |
27 |
Correct |
1077 ms |
5604 KB |
Output is correct |
28 |
Correct |
1108 ms |
5324 KB |
Output is correct |
29 |
Correct |
1426 ms |
5108 KB |
Output is correct |
30 |
Correct |
1557 ms |
5084 KB |
Output is correct |
31 |
Correct |
1166 ms |
4240 KB |
Output is correct |
32 |
Correct |
588 ms |
2956 KB |
Output is correct |
33 |
Correct |
1195 ms |
4036 KB |
Output is correct |
34 |
Correct |
1120 ms |
4012 KB |
Output is correct |
35 |
Correct |
71 ms |
2368 KB |
Output is correct |
36 |
Correct |
1197 ms |
4028 KB |
Output is correct |
37 |
Correct |
1109 ms |
3924 KB |
Output is correct |
38 |
Correct |
945 ms |
4120 KB |
Output is correct |
39 |
Correct |
833 ms |
4192 KB |
Output is correct |
40 |
Correct |
831 ms |
4128 KB |
Output is correct |
41 |
Correct |
819 ms |
3952 KB |
Output is correct |
42 |
Correct |
804 ms |
3908 KB |
Output is correct |
43 |
Correct |
2529 ms |
7496 KB |
Output is correct |
44 |
Correct |
65 ms |
2612 KB |
Output is correct |
45 |
Correct |
251 ms |
4768 KB |
Output is correct |
46 |
Correct |
125 ms |
4560 KB |
Output is correct |
47 |
Correct |
1467 ms |
7328 KB |
Output is correct |
48 |
Correct |
2561 ms |
7328 KB |
Output is correct |
49 |
Correct |
1489 ms |
7492 KB |
Output is correct |
50 |
Correct |
1188 ms |
5076 KB |
Output is correct |
51 |
Correct |
1253 ms |
5332 KB |
Output is correct |
52 |
Correct |
1169 ms |
5112 KB |
Output is correct |
53 |
Correct |
1750 ms |
6748 KB |
Output is correct |
54 |
Correct |
1720 ms |
6920 KB |
Output is correct |
55 |
Correct |
1761 ms |
6792 KB |
Output is correct |
56 |
Correct |
1251 ms |
7376 KB |
Output is correct |
57 |
Correct |
1286 ms |
7500 KB |
Output is correct |
58 |
Correct |
2310 ms |
7564 KB |
Output is correct |
59 |
Correct |
2392 ms |
7644 KB |
Output is correct |
60 |
Correct |
2308 ms |
7360 KB |
Output is correct |
61 |
Correct |
2313 ms |
7508 KB |
Output is correct |
62 |
Correct |
2024 ms |
7132 KB |
Output is correct |
63 |
Correct |
1939 ms |
7368 KB |
Output is correct |
64 |
Correct |
2268 ms |
7444 KB |
Output is correct |
65 |
Correct |
1336 ms |
7412 KB |
Output is correct |
66 |
Correct |
1371 ms |
5404 KB |
Output is correct |
67 |
Correct |
1555 ms |
5612 KB |
Output is correct |
68 |
Correct |
1443 ms |
5296 KB |
Output is correct |
69 |
Correct |
1252 ms |
5212 KB |
Output is correct |
70 |
Correct |
1488 ms |
5932 KB |
Output is correct |
71 |
Correct |
1493 ms |
5176 KB |
Output is correct |
72 |
Correct |
1512 ms |
5108 KB |
Output is correct |
73 |
Correct |
1421 ms |
5096 KB |
Output is correct |
74 |
Correct |
1432 ms |
5092 KB |
Output is correct |
75 |
Correct |
1392 ms |
5392 KB |
Output is correct |
76 |
Correct |
1329 ms |
5192 KB |
Output is correct |
77 |
Correct |
1272 ms |
5284 KB |
Output is correct |
78 |
Correct |
1278 ms |
5204 KB |
Output is correct |
79 |
Correct |
1163 ms |
5084 KB |
Output is correct |
80 |
Correct |
1200 ms |
5112 KB |
Output is correct |
81 |
Correct |
1158 ms |
5192 KB |
Output is correct |
82 |
Correct |
1093 ms |
5604 KB |
Output is correct |
83 |
Correct |
1096 ms |
5324 KB |
Output is correct |
84 |
Correct |
1091 ms |
5432 KB |
Output is correct |
85 |
Correct |
2509 ms |
8064 KB |
Output is correct |
86 |
Correct |
254 ms |
5036 KB |
Output is correct |
87 |
Correct |
142 ms |
5032 KB |
Output is correct |
88 |
Correct |
1544 ms |
7944 KB |
Output is correct |
89 |
Correct |
2531 ms |
8240 KB |
Output is correct |
90 |
Correct |
1508 ms |
7756 KB |
Output is correct |
91 |
Correct |
1445 ms |
5208 KB |
Output is correct |
92 |
Correct |
1456 ms |
5212 KB |
Output is correct |
93 |
Correct |
1691 ms |
5448 KB |
Output is correct |
94 |
Correct |
2016 ms |
7228 KB |
Output is correct |
95 |
Correct |
2009 ms |
7432 KB |
Output is correct |
96 |
Correct |
2162 ms |
7464 KB |
Output is correct |
97 |
Correct |
1403 ms |
7908 KB |
Output is correct |
98 |
Correct |
1401 ms |
7836 KB |
Output is correct |
99 |
Correct |
2587 ms |
8164 KB |
Output is correct |
100 |
Correct |
2583 ms |
7980 KB |
Output is correct |
101 |
Correct |
2581 ms |
8116 KB |
Output is correct |
102 |
Correct |
2577 ms |
8112 KB |
Output is correct |
103 |
Correct |
2365 ms |
7464 KB |
Output is correct |
104 |
Correct |
2379 ms |
7396 KB |
Output is correct |
105 |
Correct |
2128 ms |
7444 KB |
Output is correct |
106 |
Correct |
1797 ms |
7092 KB |
Output is correct |
107 |
Correct |
2123 ms |
7192 KB |
Output is correct |
108 |
Correct |
2567 ms |
7516 KB |
Output is correct |
109 |
Correct |
1623 ms |
7596 KB |
Output is correct |