# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
834196 |
2023-08-22T11:45:59 Z |
Antekb |
Bridges (APIO19_bridges) |
C++17 |
|
2619 ms |
13700 KB |
#include<bits/stdc++.h>
#define st first
#define nd second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define pp pop_back
#define mp make_pair
using namespace std;
using pii = pair<int, int>;
using ll = long long;
using vi = vector<int>;
using vii = vector<pii>;
void debug(){cerr<<"\n";}
template<typename H, typename... T>
void debug(H h, T... t){
cerr<<h;
if(sizeof...(t)){
cerr<<", ";
}
debug(t...);
}
#define deb(x...) cerr<<#x<<" = ";debug(x);
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const int N=1e5+5;
vii edg;
vii E[N];
int wei[N];
int ans[N];
int spec[N], wei2[N];
int r[N], siz[N], vis[N];
int find(int v){
if(r[v]==v)return v;
return r[v]=find(r[v]);
}
void Union(int a, int b){
a=find(a);
b=find(b);
if(a==b)return;
if(siz[a]<siz[b])swap(a, b);
r[b]=a;
siz[a]+=siz[b];
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin>>n>>m;
for(int i=0; i<m; i++){
int u, v, w;
cin>>u>>v>>w;
wei[i]=w;
edg.eb(u, v);
}
int q;
cin>>q;
int K=500;
vector<pair<pii, int> > Q, U;
for(int qq=0; qq<q; qq++){
int qt, qa, qb;
cin>>qt>>qa>>qb;
if(qt==1)U.eb(mp(qb, qa-1), qq);
else Q.eb(mp(qb, qa), qq);
if(qq==q-1 || Q.size()+U.size()==K){
vi waz, waz2;
for(auto i:U){
waz.pb(i.st.nd);
waz2.pb(edg[i.st.nd].st);
waz2.pb(edg[i.st.nd].nd);
spec[i.st.nd]=1;
wei2[i.st.nd]=wei[i.st.nd];
}
sort(all(waz));
waz.resize(unique(all(waz))-waz.begin());
sort(all(waz2));
waz2.resize(unique(all(waz2))-waz2.begin());
vector<pair<int, pii> > edg2;
for(int i=0; i<m ;i++){
if(!spec[i])edg2.eb(wei[i], edg[i]);
}
for(int i=1; i<=n; i++)r[i]=i, siz[i]=1;
sort(all(edg2));
reverse(all(edg2));
sort(all(Q));
reverse(all(Q));
int wsk=0;
for(int j=0; j<Q.size(); j++){
while(wsk<edg2.size() && edg2[wsk].st>=Q[j].st.st){
Union(edg2[wsk].nd.st, edg2[wsk].nd.nd);
wsk++;
}
int t=Q[j].nd;
for(auto i:U){
if(i.nd>t)break;
wei2[i.st.nd]=i.st.st;
}
for(int i:waz){
E[find(edg[i].st)].eb(find(edg[i].nd), i);
E[find(edg[i].nd)].eb(find(edg[i].st), i);
}
//deb(Q[j].st.nd, Q[j].st.nd, Q[j].nd);
//for(int i=0; i<m; i++){deb(find(edg[i].st), find(edg[i].nd), spec[i], wei[i], wei2[i]);}
vi V;
int s=0;
V.pb(find(Q[j].st.nd));
vis[V[0]]=1;
for(int i=0; i<V.size(); i++){
int v=V[i];
//deb(v, siz[v]);
s+=siz[v];
for(auto e:E[v]){
int u=e.st;
//deb(v, u, e.nd);
if(wei2[e.nd]>=Q[j].st.st && !vis[u]){
vis[u]=1;
V.pb(u);
}
}
}
ans[Q[j].nd]=s;
for(int i:V){
vis[i]=0;
}
for(auto i:waz){wei2[i]=wei[i];}
for(auto i:waz2){
E[find(i)].clear();
}
}
for(auto i:U){
spec[i.st.nd]=0;
wei[i.st.nd]=i.st.st;
wei2[i.st.nd]=0;
}
Q.clear();
U.clear();
}
}
for(int i=0; i<q; i++){
if(ans[i]){
cout<<ans[i]<<"\n";
}
}
}
Compilation message
bridges.cpp: In function 'int main()':
bridges.cpp:65:34: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
65 | if(qq==q-1 || Q.size()+U.size()==K){
| ~~~~~~~~~~~~~~~~~^~~
bridges.cpp:88:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | for(int j=0; j<Q.size(); j++){
| ~^~~~~~~~~
bridges.cpp:89:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
89 | while(wsk<edg2.size() && edg2[wsk].st>=Q[j].st.st){
| ~~~^~~~~~~~~~~~
bridges.cpp:108:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
108 | for(int i=0; i<V.size(); i++){
| ~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
Output is correct |
2 |
Correct |
1 ms |
2644 KB |
Output is correct |
3 |
Correct |
30 ms |
2900 KB |
Output is correct |
4 |
Correct |
4 ms |
2644 KB |
Output is correct |
5 |
Correct |
11 ms |
2772 KB |
Output is correct |
6 |
Correct |
10 ms |
2772 KB |
Output is correct |
7 |
Correct |
11 ms |
2772 KB |
Output is correct |
8 |
Correct |
11 ms |
2772 KB |
Output is correct |
9 |
Correct |
12 ms |
2772 KB |
Output is correct |
10 |
Correct |
10 ms |
2772 KB |
Output is correct |
11 |
Correct |
9 ms |
2780 KB |
Output is correct |
12 |
Correct |
10 ms |
2772 KB |
Output is correct |
13 |
Correct |
13 ms |
2772 KB |
Output is correct |
14 |
Correct |
12 ms |
2772 KB |
Output is correct |
15 |
Correct |
12 ms |
2772 KB |
Output is correct |
16 |
Correct |
11 ms |
2776 KB |
Output is correct |
17 |
Correct |
14 ms |
2772 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1342 ms |
7496 KB |
Output is correct |
2 |
Correct |
1196 ms |
7552 KB |
Output is correct |
3 |
Correct |
1194 ms |
7492 KB |
Output is correct |
4 |
Correct |
1187 ms |
7492 KB |
Output is correct |
5 |
Correct |
1156 ms |
7560 KB |
Output is correct |
6 |
Correct |
1283 ms |
6384 KB |
Output is correct |
7 |
Correct |
1238 ms |
6416 KB |
Output is correct |
8 |
Correct |
1214 ms |
6460 KB |
Output is correct |
9 |
Correct |
31 ms |
3276 KB |
Output is correct |
10 |
Correct |
1212 ms |
7340 KB |
Output is correct |
11 |
Correct |
1207 ms |
7360 KB |
Output is correct |
12 |
Correct |
1029 ms |
6112 KB |
Output is correct |
13 |
Correct |
1025 ms |
6664 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
830 ms |
5812 KB |
Output is correct |
2 |
Correct |
415 ms |
3984 KB |
Output is correct |
3 |
Correct |
874 ms |
5804 KB |
Output is correct |
4 |
Correct |
847 ms |
6192 KB |
Output is correct |
5 |
Correct |
27 ms |
3276 KB |
Output is correct |
6 |
Correct |
826 ms |
5880 KB |
Output is correct |
7 |
Correct |
818 ms |
5856 KB |
Output is correct |
8 |
Correct |
812 ms |
5820 KB |
Output is correct |
9 |
Correct |
653 ms |
5316 KB |
Output is correct |
10 |
Correct |
654 ms |
5356 KB |
Output is correct |
11 |
Correct |
677 ms |
5936 KB |
Output is correct |
12 |
Correct |
676 ms |
6032 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1852 ms |
7616 KB |
Output is correct |
2 |
Correct |
27 ms |
3276 KB |
Output is correct |
3 |
Correct |
180 ms |
6636 KB |
Output is correct |
4 |
Correct |
239 ms |
6616 KB |
Output is correct |
5 |
Correct |
2248 ms |
7556 KB |
Output is correct |
6 |
Correct |
1868 ms |
7700 KB |
Output is correct |
7 |
Correct |
2296 ms |
7628 KB |
Output is correct |
8 |
Correct |
936 ms |
5636 KB |
Output is correct |
9 |
Correct |
934 ms |
5636 KB |
Output is correct |
10 |
Correct |
940 ms |
5676 KB |
Output is correct |
11 |
Correct |
1535 ms |
7028 KB |
Output is correct |
12 |
Correct |
1459 ms |
6980 KB |
Output is correct |
13 |
Correct |
1523 ms |
6988 KB |
Output is correct |
14 |
Correct |
2228 ms |
7820 KB |
Output is correct |
15 |
Correct |
2305 ms |
7680 KB |
Output is correct |
16 |
Correct |
1928 ms |
7580 KB |
Output is correct |
17 |
Correct |
1954 ms |
7552 KB |
Output is correct |
18 |
Correct |
1893 ms |
7564 KB |
Output is correct |
19 |
Correct |
1912 ms |
7544 KB |
Output is correct |
20 |
Correct |
1663 ms |
7328 KB |
Output is correct |
21 |
Correct |
1660 ms |
7192 KB |
Output is correct |
22 |
Correct |
1871 ms |
7444 KB |
Output is correct |
23 |
Correct |
1896 ms |
7044 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1342 ms |
7496 KB |
Output is correct |
2 |
Correct |
1196 ms |
7552 KB |
Output is correct |
3 |
Correct |
1194 ms |
7492 KB |
Output is correct |
4 |
Correct |
1187 ms |
7492 KB |
Output is correct |
5 |
Correct |
1156 ms |
7560 KB |
Output is correct |
6 |
Correct |
1283 ms |
6384 KB |
Output is correct |
7 |
Correct |
1238 ms |
6416 KB |
Output is correct |
8 |
Correct |
1214 ms |
6460 KB |
Output is correct |
9 |
Correct |
31 ms |
3276 KB |
Output is correct |
10 |
Correct |
1212 ms |
7340 KB |
Output is correct |
11 |
Correct |
1207 ms |
7360 KB |
Output is correct |
12 |
Correct |
1029 ms |
6112 KB |
Output is correct |
13 |
Correct |
1025 ms |
6664 KB |
Output is correct |
14 |
Correct |
830 ms |
5812 KB |
Output is correct |
15 |
Correct |
415 ms |
3984 KB |
Output is correct |
16 |
Correct |
874 ms |
5804 KB |
Output is correct |
17 |
Correct |
847 ms |
6192 KB |
Output is correct |
18 |
Correct |
27 ms |
3276 KB |
Output is correct |
19 |
Correct |
826 ms |
5880 KB |
Output is correct |
20 |
Correct |
818 ms |
5856 KB |
Output is correct |
21 |
Correct |
812 ms |
5820 KB |
Output is correct |
22 |
Correct |
653 ms |
5316 KB |
Output is correct |
23 |
Correct |
654 ms |
5356 KB |
Output is correct |
24 |
Correct |
677 ms |
5936 KB |
Output is correct |
25 |
Correct |
676 ms |
6032 KB |
Output is correct |
26 |
Correct |
1179 ms |
7292 KB |
Output is correct |
27 |
Correct |
1286 ms |
7356 KB |
Output is correct |
28 |
Correct |
1254 ms |
7412 KB |
Output is correct |
29 |
Correct |
1239 ms |
7416 KB |
Output is correct |
30 |
Correct |
1294 ms |
7468 KB |
Output is correct |
31 |
Correct |
1282 ms |
7472 KB |
Output is correct |
32 |
Correct |
1282 ms |
7440 KB |
Output is correct |
33 |
Correct |
1218 ms |
7464 KB |
Output is correct |
34 |
Correct |
1240 ms |
7436 KB |
Output is correct |
35 |
Correct |
1246 ms |
7476 KB |
Output is correct |
36 |
Correct |
1231 ms |
7476 KB |
Output is correct |
37 |
Correct |
1220 ms |
7436 KB |
Output is correct |
38 |
Correct |
1232 ms |
7468 KB |
Output is correct |
39 |
Correct |
1048 ms |
6752 KB |
Output is correct |
40 |
Correct |
1029 ms |
6712 KB |
Output is correct |
41 |
Correct |
1029 ms |
6700 KB |
Output is correct |
42 |
Correct |
1056 ms |
7576 KB |
Output is correct |
43 |
Correct |
1046 ms |
7580 KB |
Output is correct |
44 |
Correct |
1044 ms |
7576 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
Output is correct |
2 |
Correct |
1 ms |
2644 KB |
Output is correct |
3 |
Correct |
30 ms |
2900 KB |
Output is correct |
4 |
Correct |
4 ms |
2644 KB |
Output is correct |
5 |
Correct |
11 ms |
2772 KB |
Output is correct |
6 |
Correct |
10 ms |
2772 KB |
Output is correct |
7 |
Correct |
11 ms |
2772 KB |
Output is correct |
8 |
Correct |
11 ms |
2772 KB |
Output is correct |
9 |
Correct |
12 ms |
2772 KB |
Output is correct |
10 |
Correct |
10 ms |
2772 KB |
Output is correct |
11 |
Correct |
9 ms |
2780 KB |
Output is correct |
12 |
Correct |
10 ms |
2772 KB |
Output is correct |
13 |
Correct |
13 ms |
2772 KB |
Output is correct |
14 |
Correct |
12 ms |
2772 KB |
Output is correct |
15 |
Correct |
12 ms |
2772 KB |
Output is correct |
16 |
Correct |
11 ms |
2776 KB |
Output is correct |
17 |
Correct |
14 ms |
2772 KB |
Output is correct |
18 |
Correct |
1342 ms |
7496 KB |
Output is correct |
19 |
Correct |
1196 ms |
7552 KB |
Output is correct |
20 |
Correct |
1194 ms |
7492 KB |
Output is correct |
21 |
Correct |
1187 ms |
7492 KB |
Output is correct |
22 |
Correct |
1156 ms |
7560 KB |
Output is correct |
23 |
Correct |
1283 ms |
6384 KB |
Output is correct |
24 |
Correct |
1238 ms |
6416 KB |
Output is correct |
25 |
Correct |
1214 ms |
6460 KB |
Output is correct |
26 |
Correct |
31 ms |
3276 KB |
Output is correct |
27 |
Correct |
1212 ms |
7340 KB |
Output is correct |
28 |
Correct |
1207 ms |
7360 KB |
Output is correct |
29 |
Correct |
1029 ms |
6112 KB |
Output is correct |
30 |
Correct |
1025 ms |
6664 KB |
Output is correct |
31 |
Correct |
830 ms |
5812 KB |
Output is correct |
32 |
Correct |
415 ms |
3984 KB |
Output is correct |
33 |
Correct |
874 ms |
5804 KB |
Output is correct |
34 |
Correct |
847 ms |
6192 KB |
Output is correct |
35 |
Correct |
27 ms |
3276 KB |
Output is correct |
36 |
Correct |
826 ms |
5880 KB |
Output is correct |
37 |
Correct |
818 ms |
5856 KB |
Output is correct |
38 |
Correct |
812 ms |
5820 KB |
Output is correct |
39 |
Correct |
653 ms |
5316 KB |
Output is correct |
40 |
Correct |
654 ms |
5356 KB |
Output is correct |
41 |
Correct |
677 ms |
5936 KB |
Output is correct |
42 |
Correct |
676 ms |
6032 KB |
Output is correct |
43 |
Correct |
1852 ms |
7616 KB |
Output is correct |
44 |
Correct |
27 ms |
3276 KB |
Output is correct |
45 |
Correct |
180 ms |
6636 KB |
Output is correct |
46 |
Correct |
239 ms |
6616 KB |
Output is correct |
47 |
Correct |
2248 ms |
7556 KB |
Output is correct |
48 |
Correct |
1868 ms |
7700 KB |
Output is correct |
49 |
Correct |
2296 ms |
7628 KB |
Output is correct |
50 |
Correct |
936 ms |
5636 KB |
Output is correct |
51 |
Correct |
934 ms |
5636 KB |
Output is correct |
52 |
Correct |
940 ms |
5676 KB |
Output is correct |
53 |
Correct |
1535 ms |
7028 KB |
Output is correct |
54 |
Correct |
1459 ms |
6980 KB |
Output is correct |
55 |
Correct |
1523 ms |
6988 KB |
Output is correct |
56 |
Correct |
2228 ms |
7820 KB |
Output is correct |
57 |
Correct |
2305 ms |
7680 KB |
Output is correct |
58 |
Correct |
1928 ms |
7580 KB |
Output is correct |
59 |
Correct |
1954 ms |
7552 KB |
Output is correct |
60 |
Correct |
1893 ms |
7564 KB |
Output is correct |
61 |
Correct |
1912 ms |
7544 KB |
Output is correct |
62 |
Correct |
1663 ms |
7328 KB |
Output is correct |
63 |
Correct |
1660 ms |
7192 KB |
Output is correct |
64 |
Correct |
1871 ms |
7444 KB |
Output is correct |
65 |
Correct |
1896 ms |
7044 KB |
Output is correct |
66 |
Correct |
1179 ms |
7292 KB |
Output is correct |
67 |
Correct |
1286 ms |
7356 KB |
Output is correct |
68 |
Correct |
1254 ms |
7412 KB |
Output is correct |
69 |
Correct |
1239 ms |
7416 KB |
Output is correct |
70 |
Correct |
1294 ms |
7468 KB |
Output is correct |
71 |
Correct |
1282 ms |
7472 KB |
Output is correct |
72 |
Correct |
1282 ms |
7440 KB |
Output is correct |
73 |
Correct |
1218 ms |
7464 KB |
Output is correct |
74 |
Correct |
1240 ms |
7436 KB |
Output is correct |
75 |
Correct |
1246 ms |
7476 KB |
Output is correct |
76 |
Correct |
1231 ms |
7476 KB |
Output is correct |
77 |
Correct |
1220 ms |
7436 KB |
Output is correct |
78 |
Correct |
1232 ms |
7468 KB |
Output is correct |
79 |
Correct |
1048 ms |
6752 KB |
Output is correct |
80 |
Correct |
1029 ms |
6712 KB |
Output is correct |
81 |
Correct |
1029 ms |
6700 KB |
Output is correct |
82 |
Correct |
1056 ms |
7576 KB |
Output is correct |
83 |
Correct |
1046 ms |
7580 KB |
Output is correct |
84 |
Correct |
1044 ms |
7576 KB |
Output is correct |
85 |
Correct |
2318 ms |
9824 KB |
Output is correct |
86 |
Correct |
205 ms |
7460 KB |
Output is correct |
87 |
Correct |
326 ms |
7444 KB |
Output is correct |
88 |
Correct |
2614 ms |
9780 KB |
Output is correct |
89 |
Correct |
2203 ms |
13648 KB |
Output is correct |
90 |
Correct |
2619 ms |
11168 KB |
Output is correct |
91 |
Correct |
1247 ms |
10156 KB |
Output is correct |
92 |
Correct |
1346 ms |
10272 KB |
Output is correct |
93 |
Correct |
1230 ms |
9168 KB |
Output is correct |
94 |
Correct |
1846 ms |
12720 KB |
Output is correct |
95 |
Correct |
1809 ms |
12656 KB |
Output is correct |
96 |
Correct |
1746 ms |
11148 KB |
Output is correct |
97 |
Correct |
2490 ms |
10532 KB |
Output is correct |
98 |
Correct |
2398 ms |
11328 KB |
Output is correct |
99 |
Correct |
2285 ms |
13640 KB |
Output is correct |
100 |
Correct |
2303 ms |
13640 KB |
Output is correct |
101 |
Correct |
2323 ms |
13700 KB |
Output is correct |
102 |
Correct |
2334 ms |
13664 KB |
Output is correct |
103 |
Correct |
1923 ms |
11156 KB |
Output is correct |
104 |
Correct |
1934 ms |
11236 KB |
Output is correct |
105 |
Correct |
1772 ms |
11820 KB |
Output is correct |
106 |
Correct |
1546 ms |
11928 KB |
Output is correct |
107 |
Correct |
1751 ms |
10836 KB |
Output is correct |
108 |
Correct |
2165 ms |
11712 KB |
Output is correct |
109 |
Correct |
2187 ms |
9692 KB |
Output is correct |