# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
834197 |
2023-08-22T11:47:15 Z |
Antekb |
Bridges (APIO19_bridges) |
C++17 |
|
1909 ms |
10224 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=800;
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 |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
1 ms |
2644 KB |
Output is correct |
3 |
Correct |
28 ms |
2900 KB |
Output is correct |
4 |
Correct |
4 ms |
2772 KB |
Output is correct |
5 |
Correct |
11 ms |
2772 KB |
Output is correct |
6 |
Correct |
11 ms |
2764 KB |
Output is correct |
7 |
Correct |
11 ms |
2772 KB |
Output is correct |
8 |
Correct |
12 ms |
2772 KB |
Output is correct |
9 |
Correct |
18 ms |
2772 KB |
Output is correct |
10 |
Correct |
10 ms |
2772 KB |
Output is correct |
11 |
Correct |
12 ms |
2772 KB |
Output is correct |
12 |
Correct |
10 ms |
2772 KB |
Output is correct |
13 |
Correct |
14 ms |
2764 KB |
Output is correct |
14 |
Correct |
13 ms |
2772 KB |
Output is correct |
15 |
Correct |
12 ms |
2772 KB |
Output is correct |
16 |
Correct |
12 ms |
2772 KB |
Output is correct |
17 |
Correct |
11 ms |
2772 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1022 ms |
7460 KB |
Output is correct |
2 |
Correct |
1040 ms |
7524 KB |
Output is correct |
3 |
Correct |
1053 ms |
7528 KB |
Output is correct |
4 |
Correct |
1012 ms |
7452 KB |
Output is correct |
5 |
Correct |
1060 ms |
7452 KB |
Output is correct |
6 |
Correct |
1202 ms |
6436 KB |
Output is correct |
7 |
Correct |
1117 ms |
6392 KB |
Output is correct |
8 |
Correct |
1077 ms |
6476 KB |
Output is correct |
9 |
Correct |
28 ms |
3284 KB |
Output is correct |
10 |
Correct |
1116 ms |
7356 KB |
Output is correct |
11 |
Correct |
1088 ms |
7368 KB |
Output is correct |
12 |
Correct |
756 ms |
6096 KB |
Output is correct |
13 |
Correct |
763 ms |
6604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
837 ms |
5952 KB |
Output is correct |
2 |
Correct |
560 ms |
4032 KB |
Output is correct |
3 |
Correct |
836 ms |
5868 KB |
Output is correct |
4 |
Correct |
811 ms |
5888 KB |
Output is correct |
5 |
Correct |
28 ms |
3276 KB |
Output is correct |
6 |
Correct |
786 ms |
5788 KB |
Output is correct |
7 |
Correct |
777 ms |
5976 KB |
Output is correct |
8 |
Correct |
801 ms |
6112 KB |
Output is correct |
9 |
Correct |
532 ms |
5376 KB |
Output is correct |
10 |
Correct |
507 ms |
5264 KB |
Output is correct |
11 |
Correct |
553 ms |
5968 KB |
Output is correct |
12 |
Correct |
538 ms |
6072 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1274 ms |
7584 KB |
Output is correct |
2 |
Correct |
28 ms |
3288 KB |
Output is correct |
3 |
Correct |
126 ms |
6704 KB |
Output is correct |
4 |
Correct |
163 ms |
6640 KB |
Output is correct |
5 |
Correct |
1503 ms |
7576 KB |
Output is correct |
6 |
Correct |
1186 ms |
7688 KB |
Output is correct |
7 |
Correct |
1446 ms |
7852 KB |
Output is correct |
8 |
Correct |
615 ms |
5604 KB |
Output is correct |
9 |
Correct |
607 ms |
5628 KB |
Output is correct |
10 |
Correct |
617 ms |
5652 KB |
Output is correct |
11 |
Correct |
987 ms |
7008 KB |
Output is correct |
12 |
Correct |
946 ms |
7060 KB |
Output is correct |
13 |
Correct |
978 ms |
6988 KB |
Output is correct |
14 |
Correct |
1523 ms |
7692 KB |
Output is correct |
15 |
Correct |
1456 ms |
7564 KB |
Output is correct |
16 |
Correct |
1270 ms |
7600 KB |
Output is correct |
17 |
Correct |
1242 ms |
7584 KB |
Output is correct |
18 |
Correct |
1221 ms |
7568 KB |
Output is correct |
19 |
Correct |
1281 ms |
7700 KB |
Output is correct |
20 |
Correct |
1067 ms |
7208 KB |
Output is correct |
21 |
Correct |
1054 ms |
7164 KB |
Output is correct |
22 |
Correct |
1173 ms |
7436 KB |
Output is correct |
23 |
Correct |
1206 ms |
7068 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1022 ms |
7460 KB |
Output is correct |
2 |
Correct |
1040 ms |
7524 KB |
Output is correct |
3 |
Correct |
1053 ms |
7528 KB |
Output is correct |
4 |
Correct |
1012 ms |
7452 KB |
Output is correct |
5 |
Correct |
1060 ms |
7452 KB |
Output is correct |
6 |
Correct |
1202 ms |
6436 KB |
Output is correct |
7 |
Correct |
1117 ms |
6392 KB |
Output is correct |
8 |
Correct |
1077 ms |
6476 KB |
Output is correct |
9 |
Correct |
28 ms |
3284 KB |
Output is correct |
10 |
Correct |
1116 ms |
7356 KB |
Output is correct |
11 |
Correct |
1088 ms |
7368 KB |
Output is correct |
12 |
Correct |
756 ms |
6096 KB |
Output is correct |
13 |
Correct |
763 ms |
6604 KB |
Output is correct |
14 |
Correct |
837 ms |
5952 KB |
Output is correct |
15 |
Correct |
560 ms |
4032 KB |
Output is correct |
16 |
Correct |
836 ms |
5868 KB |
Output is correct |
17 |
Correct |
811 ms |
5888 KB |
Output is correct |
18 |
Correct |
28 ms |
3276 KB |
Output is correct |
19 |
Correct |
786 ms |
5788 KB |
Output is correct |
20 |
Correct |
777 ms |
5976 KB |
Output is correct |
21 |
Correct |
801 ms |
6112 KB |
Output is correct |
22 |
Correct |
532 ms |
5376 KB |
Output is correct |
23 |
Correct |
507 ms |
5264 KB |
Output is correct |
24 |
Correct |
553 ms |
5968 KB |
Output is correct |
25 |
Correct |
538 ms |
6072 KB |
Output is correct |
26 |
Correct |
1056 ms |
7476 KB |
Output is correct |
27 |
Correct |
1146 ms |
7444 KB |
Output is correct |
28 |
Correct |
1112 ms |
7436 KB |
Output is correct |
29 |
Correct |
1084 ms |
7400 KB |
Output is correct |
30 |
Correct |
1170 ms |
7540 KB |
Output is correct |
31 |
Correct |
1265 ms |
7476 KB |
Output is correct |
32 |
Correct |
1212 ms |
7600 KB |
Output is correct |
33 |
Correct |
1096 ms |
7456 KB |
Output is correct |
34 |
Correct |
1097 ms |
7500 KB |
Output is correct |
35 |
Correct |
1107 ms |
7488 KB |
Output is correct |
36 |
Correct |
1063 ms |
7428 KB |
Output is correct |
37 |
Correct |
1033 ms |
7480 KB |
Output is correct |
38 |
Correct |
1063 ms |
7500 KB |
Output is correct |
39 |
Correct |
753 ms |
6736 KB |
Output is correct |
40 |
Correct |
733 ms |
6704 KB |
Output is correct |
41 |
Correct |
747 ms |
6708 KB |
Output is correct |
42 |
Correct |
802 ms |
7596 KB |
Output is correct |
43 |
Correct |
827 ms |
7620 KB |
Output is correct |
44 |
Correct |
803 ms |
7656 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
1 ms |
2644 KB |
Output is correct |
3 |
Correct |
28 ms |
2900 KB |
Output is correct |
4 |
Correct |
4 ms |
2772 KB |
Output is correct |
5 |
Correct |
11 ms |
2772 KB |
Output is correct |
6 |
Correct |
11 ms |
2764 KB |
Output is correct |
7 |
Correct |
11 ms |
2772 KB |
Output is correct |
8 |
Correct |
12 ms |
2772 KB |
Output is correct |
9 |
Correct |
18 ms |
2772 KB |
Output is correct |
10 |
Correct |
10 ms |
2772 KB |
Output is correct |
11 |
Correct |
12 ms |
2772 KB |
Output is correct |
12 |
Correct |
10 ms |
2772 KB |
Output is correct |
13 |
Correct |
14 ms |
2764 KB |
Output is correct |
14 |
Correct |
13 ms |
2772 KB |
Output is correct |
15 |
Correct |
12 ms |
2772 KB |
Output is correct |
16 |
Correct |
12 ms |
2772 KB |
Output is correct |
17 |
Correct |
11 ms |
2772 KB |
Output is correct |
18 |
Correct |
1022 ms |
7460 KB |
Output is correct |
19 |
Correct |
1040 ms |
7524 KB |
Output is correct |
20 |
Correct |
1053 ms |
7528 KB |
Output is correct |
21 |
Correct |
1012 ms |
7452 KB |
Output is correct |
22 |
Correct |
1060 ms |
7452 KB |
Output is correct |
23 |
Correct |
1202 ms |
6436 KB |
Output is correct |
24 |
Correct |
1117 ms |
6392 KB |
Output is correct |
25 |
Correct |
1077 ms |
6476 KB |
Output is correct |
26 |
Correct |
28 ms |
3284 KB |
Output is correct |
27 |
Correct |
1116 ms |
7356 KB |
Output is correct |
28 |
Correct |
1088 ms |
7368 KB |
Output is correct |
29 |
Correct |
756 ms |
6096 KB |
Output is correct |
30 |
Correct |
763 ms |
6604 KB |
Output is correct |
31 |
Correct |
837 ms |
5952 KB |
Output is correct |
32 |
Correct |
560 ms |
4032 KB |
Output is correct |
33 |
Correct |
836 ms |
5868 KB |
Output is correct |
34 |
Correct |
811 ms |
5888 KB |
Output is correct |
35 |
Correct |
28 ms |
3276 KB |
Output is correct |
36 |
Correct |
786 ms |
5788 KB |
Output is correct |
37 |
Correct |
777 ms |
5976 KB |
Output is correct |
38 |
Correct |
801 ms |
6112 KB |
Output is correct |
39 |
Correct |
532 ms |
5376 KB |
Output is correct |
40 |
Correct |
507 ms |
5264 KB |
Output is correct |
41 |
Correct |
553 ms |
5968 KB |
Output is correct |
42 |
Correct |
538 ms |
6072 KB |
Output is correct |
43 |
Correct |
1274 ms |
7584 KB |
Output is correct |
44 |
Correct |
28 ms |
3288 KB |
Output is correct |
45 |
Correct |
126 ms |
6704 KB |
Output is correct |
46 |
Correct |
163 ms |
6640 KB |
Output is correct |
47 |
Correct |
1503 ms |
7576 KB |
Output is correct |
48 |
Correct |
1186 ms |
7688 KB |
Output is correct |
49 |
Correct |
1446 ms |
7852 KB |
Output is correct |
50 |
Correct |
615 ms |
5604 KB |
Output is correct |
51 |
Correct |
607 ms |
5628 KB |
Output is correct |
52 |
Correct |
617 ms |
5652 KB |
Output is correct |
53 |
Correct |
987 ms |
7008 KB |
Output is correct |
54 |
Correct |
946 ms |
7060 KB |
Output is correct |
55 |
Correct |
978 ms |
6988 KB |
Output is correct |
56 |
Correct |
1523 ms |
7692 KB |
Output is correct |
57 |
Correct |
1456 ms |
7564 KB |
Output is correct |
58 |
Correct |
1270 ms |
7600 KB |
Output is correct |
59 |
Correct |
1242 ms |
7584 KB |
Output is correct |
60 |
Correct |
1221 ms |
7568 KB |
Output is correct |
61 |
Correct |
1281 ms |
7700 KB |
Output is correct |
62 |
Correct |
1067 ms |
7208 KB |
Output is correct |
63 |
Correct |
1054 ms |
7164 KB |
Output is correct |
64 |
Correct |
1173 ms |
7436 KB |
Output is correct |
65 |
Correct |
1206 ms |
7068 KB |
Output is correct |
66 |
Correct |
1056 ms |
7476 KB |
Output is correct |
67 |
Correct |
1146 ms |
7444 KB |
Output is correct |
68 |
Correct |
1112 ms |
7436 KB |
Output is correct |
69 |
Correct |
1084 ms |
7400 KB |
Output is correct |
70 |
Correct |
1170 ms |
7540 KB |
Output is correct |
71 |
Correct |
1265 ms |
7476 KB |
Output is correct |
72 |
Correct |
1212 ms |
7600 KB |
Output is correct |
73 |
Correct |
1096 ms |
7456 KB |
Output is correct |
74 |
Correct |
1097 ms |
7500 KB |
Output is correct |
75 |
Correct |
1107 ms |
7488 KB |
Output is correct |
76 |
Correct |
1063 ms |
7428 KB |
Output is correct |
77 |
Correct |
1033 ms |
7480 KB |
Output is correct |
78 |
Correct |
1063 ms |
7500 KB |
Output is correct |
79 |
Correct |
753 ms |
6736 KB |
Output is correct |
80 |
Correct |
733 ms |
6704 KB |
Output is correct |
81 |
Correct |
747 ms |
6708 KB |
Output is correct |
82 |
Correct |
802 ms |
7596 KB |
Output is correct |
83 |
Correct |
827 ms |
7620 KB |
Output is correct |
84 |
Correct |
803 ms |
7656 KB |
Output is correct |
85 |
Correct |
1743 ms |
9840 KB |
Output is correct |
86 |
Correct |
160 ms |
7472 KB |
Output is correct |
87 |
Correct |
195 ms |
7432 KB |
Output is correct |
88 |
Correct |
1909 ms |
9796 KB |
Output is correct |
89 |
Correct |
1723 ms |
9848 KB |
Output is correct |
90 |
Correct |
1859 ms |
8828 KB |
Output is correct |
91 |
Correct |
1050 ms |
7512 KB |
Output is correct |
92 |
Correct |
1050 ms |
7656 KB |
Output is correct |
93 |
Correct |
1053 ms |
6592 KB |
Output is correct |
94 |
Correct |
1431 ms |
9872 KB |
Output is correct |
95 |
Correct |
1493 ms |
9580 KB |
Output is correct |
96 |
Correct |
1378 ms |
8200 KB |
Output is correct |
97 |
Correct |
1593 ms |
8288 KB |
Output is correct |
98 |
Correct |
1671 ms |
9224 KB |
Output is correct |
99 |
Correct |
1767 ms |
9920 KB |
Output is correct |
100 |
Correct |
1907 ms |
9980 KB |
Output is correct |
101 |
Correct |
1757 ms |
10224 KB |
Output is correct |
102 |
Correct |
1747 ms |
10100 KB |
Output is correct |
103 |
Correct |
1483 ms |
8016 KB |
Output is correct |
104 |
Correct |
1477 ms |
8152 KB |
Output is correct |
105 |
Correct |
1202 ms |
8980 KB |
Output is correct |
106 |
Correct |
1066 ms |
9304 KB |
Output is correct |
107 |
Correct |
1168 ms |
7604 KB |
Output is correct |
108 |
Correct |
1623 ms |
8128 KB |
Output is correct |
109 |
Correct |
1646 ms |
7612 KB |
Output is correct |