# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
552775 |
2022-04-23T21:45:47 Z |
jjaewon |
Bridges (APIO19_bridges) |
C++14 |
|
2378 ms |
12304 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
#define fi first
#define se second
#define endl '\n'
#define y1 holyshit
#define all(x) x.begin(),x.end()
const int inf=0x3f3f3f3f;
#define SZ 700
struct DATA{
//type 0: edge, type 1: query 1, type 2: query 2
int type,idx,u,v,d;
bool operator<(const DATA& p) const{ return d==p.d?type>p.type:d<p.d; }
}edge[100010];
vector<DATA> query;
int N,M,Q,ans[100010];
int p[50010],sz[50010];
stack<pii> st;
int find(int x){ return x==p[x]?x:find(p[x]); }
void merge(int x,int y,bool undo){
x=find(x); y=find(y);
if(x==y) return;
if(sz[x]<sz[y]) swap(x,y);
sz[x]+=sz[y];
p[y]=x;
if(undo) st.push({x,y});
}
void solve(){
vector<DATA> v;
vector<int> md;
bool used[100010]={0};
int w[100010];
for(auto i:query){
if(i.type==1) used[i.u]=1;
else if(i.type==2) v.push_back(i);
}
for(int i=1;i<=M;i++){
if(!used[i]) v.push_back(edge[i]);
else{
md.push_back(i);
w[i]=edge[i].d;
}
}
sort(all(v));
reverse(all(v));
for(int i=1;i<=N;i++) p[i]=i, sz[i]=1;
for(auto i:v){
if(i.type==0){
merge(i.u,i.v,0);
//cout<<"set "<<i.u<<' '<<i.v<<' '<<i.d<<endl;
}
else{
//cout<<'#'<<' '<<i.idx<<endl;
for(auto j:query){
if(i.idx==j.idx) break;
if(j.type==1) w[j.u]=j.d;
}
for(auto j:md) if(w[j]>=i.d){
merge(edge[j].u,edge[j].v,1);
//cout<<"add "<<edge[j].u<<' '<<edge[j].v<<' '<<w[j]<<endl;
}
ans[i.idx]=sz[find(i.u)];
//cout<<"ans: "<<ans[i.idx]<<endl;
for(auto j:md) w[j]=edge[j].d;
while(!st.empty()){
auto [x,y]=st.top();
sz[x]-=sz[y];
p[y]=y;
st.pop();
}
}
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
cin>>N>>M;
for(int i=1;i<=M;i++){
int u,v,d; cin>>u>>v>>d;
edge[i]={0,i,u,v,d};
}
cin>>Q;
for(int i=1;i<=Q;i++){
int t,a,b; cin>>t>>a>>b;
query.push_back({t,i,a,0,b});
if(i%SZ==0){
solve();
for(auto j:query) if(j.type==1) edge[j.u].d=j.d;
query.clear();
}
}
solve();
for(int i=1;i<=Q;i++) if(ans[i]>0) cout<<ans[i]<<endl;
return 0;
}
Compilation message
bridges.cpp: In function 'void solve()':
bridges.cpp:73:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
73 | auto [x,y]=st.top();
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
724 KB |
Output is correct |
2 |
Correct |
1 ms |
724 KB |
Output is correct |
3 |
Correct |
27 ms |
1128 KB |
Output is correct |
4 |
Correct |
7 ms |
980 KB |
Output is correct |
5 |
Correct |
14 ms |
1004 KB |
Output is correct |
6 |
Correct |
14 ms |
980 KB |
Output is correct |
7 |
Correct |
14 ms |
984 KB |
Output is correct |
8 |
Correct |
14 ms |
1068 KB |
Output is correct |
9 |
Correct |
18 ms |
988 KB |
Output is correct |
10 |
Correct |
15 ms |
1056 KB |
Output is correct |
11 |
Correct |
15 ms |
1056 KB |
Output is correct |
12 |
Correct |
18 ms |
1052 KB |
Output is correct |
13 |
Correct |
19 ms |
1048 KB |
Output is correct |
14 |
Correct |
22 ms |
1060 KB |
Output is correct |
15 |
Correct |
17 ms |
1108 KB |
Output is correct |
16 |
Correct |
16 ms |
968 KB |
Output is correct |
17 |
Correct |
16 ms |
988 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1417 ms |
5408 KB |
Output is correct |
2 |
Correct |
1408 ms |
7696 KB |
Output is correct |
3 |
Correct |
1411 ms |
7784 KB |
Output is correct |
4 |
Correct |
1440 ms |
7728 KB |
Output is correct |
5 |
Correct |
1381 ms |
7952 KB |
Output is correct |
6 |
Correct |
1817 ms |
7520 KB |
Output is correct |
7 |
Correct |
1799 ms |
7552 KB |
Output is correct |
8 |
Correct |
1799 ms |
7540 KB |
Output is correct |
9 |
Correct |
58 ms |
2764 KB |
Output is correct |
10 |
Correct |
1118 ms |
6564 KB |
Output is correct |
11 |
Correct |
1103 ms |
6508 KB |
Output is correct |
12 |
Correct |
1338 ms |
7328 KB |
Output is correct |
13 |
Correct |
1244 ms |
7668 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1067 ms |
4440 KB |
Output is correct |
2 |
Correct |
653 ms |
3472 KB |
Output is correct |
3 |
Correct |
1170 ms |
6088 KB |
Output is correct |
4 |
Correct |
1055 ms |
6492 KB |
Output is correct |
5 |
Correct |
80 ms |
2768 KB |
Output is correct |
6 |
Correct |
1127 ms |
6376 KB |
Output is correct |
7 |
Correct |
998 ms |
6420 KB |
Output is correct |
8 |
Correct |
928 ms |
6328 KB |
Output is correct |
9 |
Correct |
846 ms |
6312 KB |
Output is correct |
10 |
Correct |
806 ms |
6488 KB |
Output is correct |
11 |
Correct |
770 ms |
5744 KB |
Output is correct |
12 |
Correct |
737 ms |
5692 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2029 ms |
9032 KB |
Output is correct |
2 |
Correct |
65 ms |
1740 KB |
Output is correct |
3 |
Correct |
239 ms |
8052 KB |
Output is correct |
4 |
Correct |
143 ms |
8056 KB |
Output is correct |
5 |
Correct |
1472 ms |
8940 KB |
Output is correct |
6 |
Correct |
2072 ms |
8872 KB |
Output is correct |
7 |
Correct |
1442 ms |
8788 KB |
Output is correct |
8 |
Correct |
992 ms |
5692 KB |
Output is correct |
9 |
Correct |
1000 ms |
5684 KB |
Output is correct |
10 |
Correct |
1030 ms |
5532 KB |
Output is correct |
11 |
Correct |
1569 ms |
7764 KB |
Output is correct |
12 |
Correct |
1567 ms |
7824 KB |
Output is correct |
13 |
Correct |
1548 ms |
7832 KB |
Output is correct |
14 |
Correct |
1239 ms |
8792 KB |
Output is correct |
15 |
Correct |
1317 ms |
8784 KB |
Output is correct |
16 |
Correct |
2063 ms |
8744 KB |
Output is correct |
17 |
Correct |
2036 ms |
8852 KB |
Output is correct |
18 |
Correct |
2000 ms |
8820 KB |
Output is correct |
19 |
Correct |
2028 ms |
8944 KB |
Output is correct |
20 |
Correct |
1762 ms |
8172 KB |
Output is correct |
21 |
Correct |
1687 ms |
8360 KB |
Output is correct |
22 |
Correct |
1946 ms |
8520 KB |
Output is correct |
23 |
Correct |
1412 ms |
8104 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1417 ms |
5408 KB |
Output is correct |
2 |
Correct |
1408 ms |
7696 KB |
Output is correct |
3 |
Correct |
1411 ms |
7784 KB |
Output is correct |
4 |
Correct |
1440 ms |
7728 KB |
Output is correct |
5 |
Correct |
1381 ms |
7952 KB |
Output is correct |
6 |
Correct |
1817 ms |
7520 KB |
Output is correct |
7 |
Correct |
1799 ms |
7552 KB |
Output is correct |
8 |
Correct |
1799 ms |
7540 KB |
Output is correct |
9 |
Correct |
58 ms |
2764 KB |
Output is correct |
10 |
Correct |
1118 ms |
6564 KB |
Output is correct |
11 |
Correct |
1103 ms |
6508 KB |
Output is correct |
12 |
Correct |
1338 ms |
7328 KB |
Output is correct |
13 |
Correct |
1244 ms |
7668 KB |
Output is correct |
14 |
Correct |
1067 ms |
4440 KB |
Output is correct |
15 |
Correct |
653 ms |
3472 KB |
Output is correct |
16 |
Correct |
1170 ms |
6088 KB |
Output is correct |
17 |
Correct |
1055 ms |
6492 KB |
Output is correct |
18 |
Correct |
80 ms |
2768 KB |
Output is correct |
19 |
Correct |
1127 ms |
6376 KB |
Output is correct |
20 |
Correct |
998 ms |
6420 KB |
Output is correct |
21 |
Correct |
928 ms |
6328 KB |
Output is correct |
22 |
Correct |
846 ms |
6312 KB |
Output is correct |
23 |
Correct |
806 ms |
6488 KB |
Output is correct |
24 |
Correct |
770 ms |
5744 KB |
Output is correct |
25 |
Correct |
737 ms |
5692 KB |
Output is correct |
26 |
Correct |
1378 ms |
7640 KB |
Output is correct |
27 |
Correct |
1581 ms |
7472 KB |
Output is correct |
28 |
Correct |
1412 ms |
7828 KB |
Output is correct |
29 |
Correct |
1161 ms |
7780 KB |
Output is correct |
30 |
Correct |
1553 ms |
7496 KB |
Output is correct |
31 |
Correct |
1584 ms |
7684 KB |
Output is correct |
32 |
Correct |
1544 ms |
7556 KB |
Output is correct |
33 |
Correct |
1414 ms |
7816 KB |
Output is correct |
34 |
Correct |
1429 ms |
7680 KB |
Output is correct |
35 |
Correct |
1433 ms |
7676 KB |
Output is correct |
36 |
Correct |
1215 ms |
7632 KB |
Output is correct |
37 |
Correct |
1217 ms |
7616 KB |
Output is correct |
38 |
Correct |
1199 ms |
7768 KB |
Output is correct |
39 |
Correct |
1076 ms |
7684 KB |
Output is correct |
40 |
Correct |
1057 ms |
7744 KB |
Output is correct |
41 |
Correct |
1060 ms |
7704 KB |
Output is correct |
42 |
Correct |
1045 ms |
7656 KB |
Output is correct |
43 |
Correct |
1025 ms |
7588 KB |
Output is correct |
44 |
Correct |
1014 ms |
7696 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
724 KB |
Output is correct |
2 |
Correct |
1 ms |
724 KB |
Output is correct |
3 |
Correct |
27 ms |
1128 KB |
Output is correct |
4 |
Correct |
7 ms |
980 KB |
Output is correct |
5 |
Correct |
14 ms |
1004 KB |
Output is correct |
6 |
Correct |
14 ms |
980 KB |
Output is correct |
7 |
Correct |
14 ms |
984 KB |
Output is correct |
8 |
Correct |
14 ms |
1068 KB |
Output is correct |
9 |
Correct |
18 ms |
988 KB |
Output is correct |
10 |
Correct |
15 ms |
1056 KB |
Output is correct |
11 |
Correct |
15 ms |
1056 KB |
Output is correct |
12 |
Correct |
18 ms |
1052 KB |
Output is correct |
13 |
Correct |
19 ms |
1048 KB |
Output is correct |
14 |
Correct |
22 ms |
1060 KB |
Output is correct |
15 |
Correct |
17 ms |
1108 KB |
Output is correct |
16 |
Correct |
16 ms |
968 KB |
Output is correct |
17 |
Correct |
16 ms |
988 KB |
Output is correct |
18 |
Correct |
1417 ms |
5408 KB |
Output is correct |
19 |
Correct |
1408 ms |
7696 KB |
Output is correct |
20 |
Correct |
1411 ms |
7784 KB |
Output is correct |
21 |
Correct |
1440 ms |
7728 KB |
Output is correct |
22 |
Correct |
1381 ms |
7952 KB |
Output is correct |
23 |
Correct |
1817 ms |
7520 KB |
Output is correct |
24 |
Correct |
1799 ms |
7552 KB |
Output is correct |
25 |
Correct |
1799 ms |
7540 KB |
Output is correct |
26 |
Correct |
58 ms |
2764 KB |
Output is correct |
27 |
Correct |
1118 ms |
6564 KB |
Output is correct |
28 |
Correct |
1103 ms |
6508 KB |
Output is correct |
29 |
Correct |
1338 ms |
7328 KB |
Output is correct |
30 |
Correct |
1244 ms |
7668 KB |
Output is correct |
31 |
Correct |
1067 ms |
4440 KB |
Output is correct |
32 |
Correct |
653 ms |
3472 KB |
Output is correct |
33 |
Correct |
1170 ms |
6088 KB |
Output is correct |
34 |
Correct |
1055 ms |
6492 KB |
Output is correct |
35 |
Correct |
80 ms |
2768 KB |
Output is correct |
36 |
Correct |
1127 ms |
6376 KB |
Output is correct |
37 |
Correct |
998 ms |
6420 KB |
Output is correct |
38 |
Correct |
928 ms |
6328 KB |
Output is correct |
39 |
Correct |
846 ms |
6312 KB |
Output is correct |
40 |
Correct |
806 ms |
6488 KB |
Output is correct |
41 |
Correct |
770 ms |
5744 KB |
Output is correct |
42 |
Correct |
737 ms |
5692 KB |
Output is correct |
43 |
Correct |
2029 ms |
9032 KB |
Output is correct |
44 |
Correct |
65 ms |
1740 KB |
Output is correct |
45 |
Correct |
239 ms |
8052 KB |
Output is correct |
46 |
Correct |
143 ms |
8056 KB |
Output is correct |
47 |
Correct |
1472 ms |
8940 KB |
Output is correct |
48 |
Correct |
2072 ms |
8872 KB |
Output is correct |
49 |
Correct |
1442 ms |
8788 KB |
Output is correct |
50 |
Correct |
992 ms |
5692 KB |
Output is correct |
51 |
Correct |
1000 ms |
5684 KB |
Output is correct |
52 |
Correct |
1030 ms |
5532 KB |
Output is correct |
53 |
Correct |
1569 ms |
7764 KB |
Output is correct |
54 |
Correct |
1567 ms |
7824 KB |
Output is correct |
55 |
Correct |
1548 ms |
7832 KB |
Output is correct |
56 |
Correct |
1239 ms |
8792 KB |
Output is correct |
57 |
Correct |
1317 ms |
8784 KB |
Output is correct |
58 |
Correct |
2063 ms |
8744 KB |
Output is correct |
59 |
Correct |
2036 ms |
8852 KB |
Output is correct |
60 |
Correct |
2000 ms |
8820 KB |
Output is correct |
61 |
Correct |
2028 ms |
8944 KB |
Output is correct |
62 |
Correct |
1762 ms |
8172 KB |
Output is correct |
63 |
Correct |
1687 ms |
8360 KB |
Output is correct |
64 |
Correct |
1946 ms |
8520 KB |
Output is correct |
65 |
Correct |
1412 ms |
8104 KB |
Output is correct |
66 |
Correct |
1378 ms |
7640 KB |
Output is correct |
67 |
Correct |
1581 ms |
7472 KB |
Output is correct |
68 |
Correct |
1412 ms |
7828 KB |
Output is correct |
69 |
Correct |
1161 ms |
7780 KB |
Output is correct |
70 |
Correct |
1553 ms |
7496 KB |
Output is correct |
71 |
Correct |
1584 ms |
7684 KB |
Output is correct |
72 |
Correct |
1544 ms |
7556 KB |
Output is correct |
73 |
Correct |
1414 ms |
7816 KB |
Output is correct |
74 |
Correct |
1429 ms |
7680 KB |
Output is correct |
75 |
Correct |
1433 ms |
7676 KB |
Output is correct |
76 |
Correct |
1215 ms |
7632 KB |
Output is correct |
77 |
Correct |
1217 ms |
7616 KB |
Output is correct |
78 |
Correct |
1199 ms |
7768 KB |
Output is correct |
79 |
Correct |
1076 ms |
7684 KB |
Output is correct |
80 |
Correct |
1057 ms |
7744 KB |
Output is correct |
81 |
Correct |
1060 ms |
7704 KB |
Output is correct |
82 |
Correct |
1045 ms |
7656 KB |
Output is correct |
83 |
Correct |
1025 ms |
7588 KB |
Output is correct |
84 |
Correct |
1014 ms |
7696 KB |
Output is correct |
85 |
Correct |
2378 ms |
12184 KB |
Output is correct |
86 |
Correct |
240 ms |
9220 KB |
Output is correct |
87 |
Correct |
166 ms |
9356 KB |
Output is correct |
88 |
Correct |
1698 ms |
10416 KB |
Output is correct |
89 |
Correct |
2352 ms |
11968 KB |
Output is correct |
90 |
Correct |
1705 ms |
10520 KB |
Output is correct |
91 |
Correct |
1448 ms |
7592 KB |
Output is correct |
92 |
Correct |
1434 ms |
7804 KB |
Output is correct |
93 |
Correct |
1742 ms |
7596 KB |
Output is correct |
94 |
Correct |
1882 ms |
10444 KB |
Output is correct |
95 |
Correct |
1920 ms |
10648 KB |
Output is correct |
96 |
Correct |
1984 ms |
10224 KB |
Output is correct |
97 |
Correct |
1468 ms |
10408 KB |
Output is correct |
98 |
Correct |
1439 ms |
10652 KB |
Output is correct |
99 |
Correct |
2341 ms |
12112 KB |
Output is correct |
100 |
Correct |
2308 ms |
12004 KB |
Output is correct |
101 |
Correct |
2377 ms |
12132 KB |
Output is correct |
102 |
Correct |
2362 ms |
12304 KB |
Output is correct |
103 |
Correct |
2197 ms |
11124 KB |
Output is correct |
104 |
Correct |
2196 ms |
10980 KB |
Output is correct |
105 |
Correct |
1840 ms |
10992 KB |
Output is correct |
106 |
Correct |
1583 ms |
10476 KB |
Output is correct |
107 |
Correct |
1801 ms |
11100 KB |
Output is correct |
108 |
Correct |
2258 ms |
11496 KB |
Output is correct |
109 |
Correct |
1682 ms |
9460 KB |
Output is correct |