# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
906513 |
2024-01-14T11:22:49 Z |
imarn |
Bridges (APIO19_bridges) |
C++14 |
|
1818 ms |
94592 KB |
#include<bits/stdc++.h>
#define ll long long
#define pii pair<ll,ll>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
const int N=1e5+5,B=1000;
int pr[N],u[N],v[N],w[N],t[N],x[N],y[N],sz[N];
stack<pii>st;
bool vis[100001]{0};
int ans[100001]{0};
int get(int r){
return pr[r]==r?r:get(pr[r]);
}
void uni(int a,int b){
a=get(a),b=get(b);
if(a==b)return;
if(sz[a]<sz[b])swap(a,b);
pr[b]=a;sz[a]+=sz[b];
st.push({a,b});
}
void rollback(int x){
while(st.size()>x){
pii u=st.top();st.pop();
sz[u.f]-=sz[u.s];pr[u.s]=u.s;
}
}
vector<int>block[1001];
bool cmp1(int a,int b){
return y[a]>y[b];
}
bool cmp2(int a,int b){
return w[a]>w[b];
}
int main() {
ios_base::sync_with_stdio(0);cin.tie(0);
int n,m;cin>>n>>m;
for(int i=1;i<=m;i++)cin>>u[i]>>v[i]>>w[i];
int q;cin>>q;
for(int i=1;i<=q;i++)cin>>t[i]>>x[i]>>y[i];
for(int l=1;l<=q;l+=B){
int r=min(q,l+B-1);
iota(pr,pr+n+1,0);
memset(vis,0,sizeof vis);
vector<int>up,un,qr;
for(int j=1;j<=n;j++)sz[j]=1;
for(int j=l;j<=r;j++){
if(t[j]==1)vis[x[j]]=1,up.pb(j);
else qr.pb(j);
}
for(int j=1;j<=m;j++)if(!vis[j])un.pb(j);
for(int j=l;j<=r;j++){
if(t[j]==1)w[x[j]]=y[j];
else {
block[j-l].clear();
for(auto it : up)if(w[x[it]]>=y[j])block[j-l].pb(x[it]);
}
}
sort(qr.begin(),qr.end(),cmp1);
sort(un.begin(),un.end(),cmp2);
int cur=0;
for(int j=0;j<qr.size();j++){
while(cur<un.size()&&w[un[cur]]>=y[qr[j]])uni(u[un[cur]],v[un[cur]]),cur++;
int prev=st.size();
for(auto it : block[qr[j]-l])uni(u[it],v[it]);
ans[qr[j]] = sz[get(x[qr[j]])];
rollback(prev);
}
}
for(int i=1;i<=q;i++)if(t[i]==2)cout<<ans[i]<<'\n';
}
Compilation message
bridges.cpp: In function 'void rollback(int)':
bridges.cpp:25:20: warning: comparison of integer expressions of different signedness: 'std::stack<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
25 | while(st.size()>x){
| ~~~~~~~~~^~
bridges.cpp: In function 'int main()':
bridges.cpp:64:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | for(int j=0;j<qr.size();j++){
| ~^~~~~~~~~~
bridges.cpp:65:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | while(cur<un.size()&&w[un[cur]]>=y[qr[j]])uni(u[un[cur]],v[un[cur]]),cur++;
| ~~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
Output is correct |
2 |
Correct |
1 ms |
2392 KB |
Output is correct |
3 |
Correct |
24 ms |
4752 KB |
Output is correct |
4 |
Correct |
4 ms |
2648 KB |
Output is correct |
5 |
Correct |
25 ms |
4916 KB |
Output is correct |
6 |
Correct |
17 ms |
4444 KB |
Output is correct |
7 |
Correct |
21 ms |
5468 KB |
Output is correct |
8 |
Correct |
31 ms |
4684 KB |
Output is correct |
9 |
Correct |
24 ms |
6236 KB |
Output is correct |
10 |
Correct |
27 ms |
4700 KB |
Output is correct |
11 |
Correct |
27 ms |
4516 KB |
Output is correct |
12 |
Correct |
32 ms |
4700 KB |
Output is correct |
13 |
Correct |
31 ms |
4692 KB |
Output is correct |
14 |
Correct |
29 ms |
4692 KB |
Output is correct |
15 |
Correct |
33 ms |
4888 KB |
Output is correct |
16 |
Correct |
24 ms |
5876 KB |
Output is correct |
17 |
Correct |
25 ms |
5468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1033 ms |
87996 KB |
Output is correct |
2 |
Correct |
1063 ms |
87260 KB |
Output is correct |
3 |
Correct |
1061 ms |
87204 KB |
Output is correct |
4 |
Correct |
1069 ms |
88124 KB |
Output is correct |
5 |
Correct |
1060 ms |
87156 KB |
Output is correct |
6 |
Correct |
1182 ms |
90008 KB |
Output is correct |
7 |
Correct |
1163 ms |
89776 KB |
Output is correct |
8 |
Correct |
1190 ms |
89112 KB |
Output is correct |
9 |
Correct |
27 ms |
3040 KB |
Output is correct |
10 |
Correct |
604 ms |
89308 KB |
Output is correct |
11 |
Correct |
600 ms |
88916 KB |
Output is correct |
12 |
Correct |
970 ms |
86204 KB |
Output is correct |
13 |
Correct |
920 ms |
88168 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
745 ms |
58592 KB |
Output is correct |
2 |
Correct |
442 ms |
21456 KB |
Output is correct |
3 |
Correct |
768 ms |
62864 KB |
Output is correct |
4 |
Correct |
759 ms |
61388 KB |
Output is correct |
5 |
Correct |
28 ms |
4044 KB |
Output is correct |
6 |
Correct |
809 ms |
61248 KB |
Output is correct |
7 |
Correct |
723 ms |
60776 KB |
Output is correct |
8 |
Correct |
651 ms |
60548 KB |
Output is correct |
9 |
Correct |
548 ms |
59844 KB |
Output is correct |
10 |
Correct |
526 ms |
59652 KB |
Output is correct |
11 |
Correct |
581 ms |
61564 KB |
Output is correct |
12 |
Correct |
559 ms |
61272 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1470 ms |
85288 KB |
Output is correct |
2 |
Correct |
29 ms |
4176 KB |
Output is correct |
3 |
Correct |
147 ms |
6392 KB |
Output is correct |
4 |
Correct |
71 ms |
6476 KB |
Output is correct |
5 |
Correct |
756 ms |
87528 KB |
Output is correct |
6 |
Correct |
1440 ms |
88896 KB |
Output is correct |
7 |
Correct |
790 ms |
88400 KB |
Output is correct |
8 |
Correct |
726 ms |
88352 KB |
Output is correct |
9 |
Correct |
720 ms |
88664 KB |
Output is correct |
10 |
Correct |
722 ms |
88372 KB |
Output is correct |
11 |
Correct |
1103 ms |
90376 KB |
Output is correct |
12 |
Correct |
1139 ms |
90244 KB |
Output is correct |
13 |
Correct |
1142 ms |
89280 KB |
Output is correct |
14 |
Correct |
746 ms |
87308 KB |
Output is correct |
15 |
Correct |
743 ms |
87352 KB |
Output is correct |
16 |
Correct |
1513 ms |
89980 KB |
Output is correct |
17 |
Correct |
1531 ms |
90676 KB |
Output is correct |
18 |
Correct |
1516 ms |
90428 KB |
Output is correct |
19 |
Correct |
1481 ms |
90328 KB |
Output is correct |
20 |
Correct |
1244 ms |
89576 KB |
Output is correct |
21 |
Correct |
1254 ms |
89644 KB |
Output is correct |
22 |
Correct |
1418 ms |
88260 KB |
Output is correct |
23 |
Correct |
816 ms |
80768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1033 ms |
87996 KB |
Output is correct |
2 |
Correct |
1063 ms |
87260 KB |
Output is correct |
3 |
Correct |
1061 ms |
87204 KB |
Output is correct |
4 |
Correct |
1069 ms |
88124 KB |
Output is correct |
5 |
Correct |
1060 ms |
87156 KB |
Output is correct |
6 |
Correct |
1182 ms |
90008 KB |
Output is correct |
7 |
Correct |
1163 ms |
89776 KB |
Output is correct |
8 |
Correct |
1190 ms |
89112 KB |
Output is correct |
9 |
Correct |
27 ms |
3040 KB |
Output is correct |
10 |
Correct |
604 ms |
89308 KB |
Output is correct |
11 |
Correct |
600 ms |
88916 KB |
Output is correct |
12 |
Correct |
970 ms |
86204 KB |
Output is correct |
13 |
Correct |
920 ms |
88168 KB |
Output is correct |
14 |
Correct |
745 ms |
58592 KB |
Output is correct |
15 |
Correct |
442 ms |
21456 KB |
Output is correct |
16 |
Correct |
768 ms |
62864 KB |
Output is correct |
17 |
Correct |
759 ms |
61388 KB |
Output is correct |
18 |
Correct |
28 ms |
4044 KB |
Output is correct |
19 |
Correct |
809 ms |
61248 KB |
Output is correct |
20 |
Correct |
723 ms |
60776 KB |
Output is correct |
21 |
Correct |
651 ms |
60548 KB |
Output is correct |
22 |
Correct |
548 ms |
59844 KB |
Output is correct |
23 |
Correct |
526 ms |
59652 KB |
Output is correct |
24 |
Correct |
581 ms |
61564 KB |
Output is correct |
25 |
Correct |
559 ms |
61272 KB |
Output is correct |
26 |
Correct |
1034 ms |
90068 KB |
Output is correct |
27 |
Correct |
1134 ms |
92556 KB |
Output is correct |
28 |
Correct |
1076 ms |
89780 KB |
Output is correct |
29 |
Correct |
878 ms |
89020 KB |
Output is correct |
30 |
Correct |
1150 ms |
92456 KB |
Output is correct |
31 |
Correct |
1120 ms |
91592 KB |
Output is correct |
32 |
Correct |
1180 ms |
91724 KB |
Output is correct |
33 |
Correct |
1065 ms |
89848 KB |
Output is correct |
34 |
Correct |
1088 ms |
90664 KB |
Output is correct |
35 |
Correct |
1059 ms |
89924 KB |
Output is correct |
36 |
Correct |
883 ms |
90132 KB |
Output is correct |
37 |
Correct |
880 ms |
89112 KB |
Output is correct |
38 |
Correct |
900 ms |
89348 KB |
Output is correct |
39 |
Correct |
779 ms |
88748 KB |
Output is correct |
40 |
Correct |
762 ms |
88440 KB |
Output is correct |
41 |
Correct |
769 ms |
89184 KB |
Output is correct |
42 |
Correct |
782 ms |
87908 KB |
Output is correct |
43 |
Correct |
756 ms |
87788 KB |
Output is correct |
44 |
Correct |
751 ms |
88344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
Output is correct |
2 |
Correct |
1 ms |
2392 KB |
Output is correct |
3 |
Correct |
24 ms |
4752 KB |
Output is correct |
4 |
Correct |
4 ms |
2648 KB |
Output is correct |
5 |
Correct |
25 ms |
4916 KB |
Output is correct |
6 |
Correct |
17 ms |
4444 KB |
Output is correct |
7 |
Correct |
21 ms |
5468 KB |
Output is correct |
8 |
Correct |
31 ms |
4684 KB |
Output is correct |
9 |
Correct |
24 ms |
6236 KB |
Output is correct |
10 |
Correct |
27 ms |
4700 KB |
Output is correct |
11 |
Correct |
27 ms |
4516 KB |
Output is correct |
12 |
Correct |
32 ms |
4700 KB |
Output is correct |
13 |
Correct |
31 ms |
4692 KB |
Output is correct |
14 |
Correct |
29 ms |
4692 KB |
Output is correct |
15 |
Correct |
33 ms |
4888 KB |
Output is correct |
16 |
Correct |
24 ms |
5876 KB |
Output is correct |
17 |
Correct |
25 ms |
5468 KB |
Output is correct |
18 |
Correct |
1033 ms |
87996 KB |
Output is correct |
19 |
Correct |
1063 ms |
87260 KB |
Output is correct |
20 |
Correct |
1061 ms |
87204 KB |
Output is correct |
21 |
Correct |
1069 ms |
88124 KB |
Output is correct |
22 |
Correct |
1060 ms |
87156 KB |
Output is correct |
23 |
Correct |
1182 ms |
90008 KB |
Output is correct |
24 |
Correct |
1163 ms |
89776 KB |
Output is correct |
25 |
Correct |
1190 ms |
89112 KB |
Output is correct |
26 |
Correct |
27 ms |
3040 KB |
Output is correct |
27 |
Correct |
604 ms |
89308 KB |
Output is correct |
28 |
Correct |
600 ms |
88916 KB |
Output is correct |
29 |
Correct |
970 ms |
86204 KB |
Output is correct |
30 |
Correct |
920 ms |
88168 KB |
Output is correct |
31 |
Correct |
745 ms |
58592 KB |
Output is correct |
32 |
Correct |
442 ms |
21456 KB |
Output is correct |
33 |
Correct |
768 ms |
62864 KB |
Output is correct |
34 |
Correct |
759 ms |
61388 KB |
Output is correct |
35 |
Correct |
28 ms |
4044 KB |
Output is correct |
36 |
Correct |
809 ms |
61248 KB |
Output is correct |
37 |
Correct |
723 ms |
60776 KB |
Output is correct |
38 |
Correct |
651 ms |
60548 KB |
Output is correct |
39 |
Correct |
548 ms |
59844 KB |
Output is correct |
40 |
Correct |
526 ms |
59652 KB |
Output is correct |
41 |
Correct |
581 ms |
61564 KB |
Output is correct |
42 |
Correct |
559 ms |
61272 KB |
Output is correct |
43 |
Correct |
1470 ms |
85288 KB |
Output is correct |
44 |
Correct |
29 ms |
4176 KB |
Output is correct |
45 |
Correct |
147 ms |
6392 KB |
Output is correct |
46 |
Correct |
71 ms |
6476 KB |
Output is correct |
47 |
Correct |
756 ms |
87528 KB |
Output is correct |
48 |
Correct |
1440 ms |
88896 KB |
Output is correct |
49 |
Correct |
790 ms |
88400 KB |
Output is correct |
50 |
Correct |
726 ms |
88352 KB |
Output is correct |
51 |
Correct |
720 ms |
88664 KB |
Output is correct |
52 |
Correct |
722 ms |
88372 KB |
Output is correct |
53 |
Correct |
1103 ms |
90376 KB |
Output is correct |
54 |
Correct |
1139 ms |
90244 KB |
Output is correct |
55 |
Correct |
1142 ms |
89280 KB |
Output is correct |
56 |
Correct |
746 ms |
87308 KB |
Output is correct |
57 |
Correct |
743 ms |
87352 KB |
Output is correct |
58 |
Correct |
1513 ms |
89980 KB |
Output is correct |
59 |
Correct |
1531 ms |
90676 KB |
Output is correct |
60 |
Correct |
1516 ms |
90428 KB |
Output is correct |
61 |
Correct |
1481 ms |
90328 KB |
Output is correct |
62 |
Correct |
1244 ms |
89576 KB |
Output is correct |
63 |
Correct |
1254 ms |
89644 KB |
Output is correct |
64 |
Correct |
1418 ms |
88260 KB |
Output is correct |
65 |
Correct |
816 ms |
80768 KB |
Output is correct |
66 |
Correct |
1034 ms |
90068 KB |
Output is correct |
67 |
Correct |
1134 ms |
92556 KB |
Output is correct |
68 |
Correct |
1076 ms |
89780 KB |
Output is correct |
69 |
Correct |
878 ms |
89020 KB |
Output is correct |
70 |
Correct |
1150 ms |
92456 KB |
Output is correct |
71 |
Correct |
1120 ms |
91592 KB |
Output is correct |
72 |
Correct |
1180 ms |
91724 KB |
Output is correct |
73 |
Correct |
1065 ms |
89848 KB |
Output is correct |
74 |
Correct |
1088 ms |
90664 KB |
Output is correct |
75 |
Correct |
1059 ms |
89924 KB |
Output is correct |
76 |
Correct |
883 ms |
90132 KB |
Output is correct |
77 |
Correct |
880 ms |
89112 KB |
Output is correct |
78 |
Correct |
900 ms |
89348 KB |
Output is correct |
79 |
Correct |
779 ms |
88748 KB |
Output is correct |
80 |
Correct |
762 ms |
88440 KB |
Output is correct |
81 |
Correct |
769 ms |
89184 KB |
Output is correct |
82 |
Correct |
782 ms |
87908 KB |
Output is correct |
83 |
Correct |
756 ms |
87788 KB |
Output is correct |
84 |
Correct |
751 ms |
88344 KB |
Output is correct |
85 |
Correct |
1708 ms |
91260 KB |
Output is correct |
86 |
Correct |
167 ms |
8308 KB |
Output is correct |
87 |
Correct |
90 ms |
9828 KB |
Output is correct |
88 |
Correct |
936 ms |
91424 KB |
Output is correct |
89 |
Correct |
1691 ms |
91256 KB |
Output is correct |
90 |
Correct |
939 ms |
91332 KB |
Output is correct |
91 |
Correct |
1133 ms |
90512 KB |
Output is correct |
92 |
Correct |
1072 ms |
89844 KB |
Output is correct |
93 |
Correct |
1270 ms |
92432 KB |
Output is correct |
94 |
Correct |
1391 ms |
92072 KB |
Output is correct |
95 |
Correct |
1388 ms |
91728 KB |
Output is correct |
96 |
Correct |
1407 ms |
93304 KB |
Output is correct |
97 |
Correct |
854 ms |
88908 KB |
Output is correct |
98 |
Correct |
890 ms |
90932 KB |
Output is correct |
99 |
Correct |
1818 ms |
93344 KB |
Output is correct |
100 |
Correct |
1727 ms |
92200 KB |
Output is correct |
101 |
Correct |
1775 ms |
92780 KB |
Output is correct |
102 |
Correct |
1760 ms |
93544 KB |
Output is correct |
103 |
Correct |
1538 ms |
94500 KB |
Output is correct |
104 |
Correct |
1579 ms |
93704 KB |
Output is correct |
105 |
Correct |
1353 ms |
94592 KB |
Output is correct |
106 |
Correct |
1161 ms |
93208 KB |
Output is correct |
107 |
Correct |
1317 ms |
90184 KB |
Output is correct |
108 |
Correct |
1679 ms |
90932 KB |
Output is correct |
109 |
Correct |
1036 ms |
85112 KB |
Output is correct |