# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
204420 | 2020-02-25T17:40:08 Z | dolphingarlic | Bridges (APIO19_bridges) | C++14 | 2451 ms | 29456 KB |
#include<bits/stdc++.h> #define FOR(i,x,y) for(int i=x;i<y;i++) using namespace std;const int B=1000,N=1e5+1;int n,m,q;stack<int>s;int z[N],c[N];void rs(){iota(c+1,c+1+n,1);fill(z+1,z+n+1,1);}inline int f(int a){while(c[a]!=a)a=c[a];return a;}void o(int a,int b){a=f(a),b=f(b);if(a == b)return;if(z[a]>z[b])swap(a,b);s.push(a);z[b]+=z[a];c[a]=c[b];}void rb(int x){while(s.size()>x){int k=s.top();s.pop();z[c[k]] -= z[k];c[k]=k;}}int u[N],v[N],w[N];int t[N],x[N],y[N];bool h[N];vector<int>to_join[B];int ans[N];int main(){ios_base::sync_with_stdio(0);cin.tie(0);cin>>n>>m;FOR(i,1,m+1)cin>>u[i]>>v[i]>>w[i];cin>>q;FOR(i,1,q+1)cin>>t[i]>>x[i]>>y[i];for(int l=1;l<=q;l+=B){int r=min(q+1,l+B);rs();fill(h+1,h+m+1,false);vector<int>ask,upd,unh;FOR(i,l,r){if(t[i] == 1){h[x[i]]=true;upd.push_back(i);} else ask.push_back(i);}FOR(i,1,m+1)if(!h[i])unh.push_back(i);FOR(i,l,r){if(t[i] == 1)w[x[i]]=y[i];else {to_join[i - l].clear();for(int j:upd)if(w[x[j]] >= y[i])to_join[i - l].push_back(x[j]);}}sort(ask.begin(),ask.end(),[&](int a,int b){ return y[a]>y[b];});sort(unh.begin(),unh.end(),[&](int a,int b){ return w[a]>w[b];});int ptr=0;for(int i:ask){while(ptr<unh.size()&& w[unh[ptr]] >= y[i]){o(u[unh[ptr]],v[unh[ptr]]);ptr++;}int p=s.size();for(int j:to_join[i - l])o(u[j],v[j]);ans[i]=z[f(x[i])];rb(p);}}FOR(i,1,q+1)if(t[i] == 2)cout<<ans[i]<<'\n';return 0;}
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 376 KB | Output is correct |
2 | Correct | 5 ms | 376 KB | Output is correct |
3 | Correct | 45 ms | 2808 KB | Output is correct |
4 | Correct | 8 ms | 508 KB | Output is correct |
5 | Correct | 45 ms | 2936 KB | Output is correct |
6 | Correct | 34 ms | 2684 KB | Output is correct |
7 | Correct | 40 ms | 3576 KB | Output is correct |
8 | Correct | 45 ms | 2680 KB | Output is correct |
9 | Correct | 50 ms | 4344 KB | Output is correct |
10 | Correct | 45 ms | 2808 KB | Output is correct |
11 | Correct | 44 ms | 2680 KB | Output is correct |
12 | Correct | 54 ms | 2808 KB | Output is correct |
13 | Correct | 53 ms | 2784 KB | Output is correct |
14 | Correct | 49 ms | 2680 KB | Output is correct |
15 | Correct | 53 ms | 2680 KB | Output is correct |
16 | Correct | 48 ms | 3964 KB | Output is correct |
17 | Correct | 47 ms | 3448 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1468 ms | 26344 KB | Output is correct |
2 | Correct | 1491 ms | 26308 KB | Output is correct |
3 | Correct | 1503 ms | 26200 KB | Output is correct |
4 | Correct | 1519 ms | 26208 KB | Output is correct |
5 | Correct | 1530 ms | 26324 KB | Output is correct |
6 | Correct | 2254 ms | 28152 KB | Output is correct |
7 | Correct | 2233 ms | 28132 KB | Output is correct |
8 | Correct | 2283 ms | 27992 KB | Output is correct |
9 | Correct | 47 ms | 2168 KB | Output is correct |
10 | Correct | 1270 ms | 28052 KB | Output is correct |
11 | Correct | 1160 ms | 28116 KB | Output is correct |
12 | Correct | 1292 ms | 24840 KB | Output is correct |
13 | Correct | 1331 ms | 27464 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1190 ms | 18704 KB | Output is correct |
2 | Correct | 925 ms | 9848 KB | Output is correct |
3 | Correct | 1448 ms | 20636 KB | Output is correct |
4 | Correct | 1177 ms | 19048 KB | Output is correct |
5 | Correct | 45 ms | 2296 KB | Output is correct |
6 | Correct | 1350 ms | 18784 KB | Output is correct |
7 | Correct | 1079 ms | 18428 KB | Output is correct |
8 | Correct | 923 ms | 18432 KB | Output is correct |
9 | Correct | 773 ms | 17288 KB | Output is correct |
10 | Correct | 696 ms | 17232 KB | Output is correct |
11 | Correct | 829 ms | 20092 KB | Output is correct |
12 | Correct | 725 ms | 19956 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1710 ms | 25228 KB | Output is correct |
2 | Correct | 47 ms | 2168 KB | Output is correct |
3 | Correct | 188 ms | 2760 KB | Output is correct |
4 | Correct | 92 ms | 2764 KB | Output is correct |
5 | Correct | 832 ms | 24976 KB | Output is correct |
6 | Correct | 1689 ms | 24956 KB | Output is correct |
7 | Correct | 831 ms | 24980 KB | Output is correct |
8 | Correct | 820 ms | 24272 KB | Output is correct |
9 | Correct | 824 ms | 24012 KB | Output is correct |
10 | Correct | 827 ms | 24276 KB | Output is correct |
11 | Correct | 1260 ms | 24772 KB | Output is correct |
12 | Correct | 1253 ms | 24912 KB | Output is correct |
13 | Correct | 1267 ms | 25152 KB | Output is correct |
14 | Correct | 748 ms | 25116 KB | Output is correct |
15 | Correct | 809 ms | 24948 KB | Output is correct |
16 | Correct | 1703 ms | 25408 KB | Output is correct |
17 | Correct | 1719 ms | 25248 KB | Output is correct |
18 | Correct | 1687 ms | 25312 KB | Output is correct |
19 | Correct | 1698 ms | 25316 KB | Output is correct |
20 | Correct | 1418 ms | 25348 KB | Output is correct |
21 | Correct | 1412 ms | 25376 KB | Output is correct |
22 | Correct | 1629 ms | 24952 KB | Output is correct |
23 | Correct | 947 ms | 22920 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1468 ms | 26344 KB | Output is correct |
2 | Correct | 1491 ms | 26308 KB | Output is correct |
3 | Correct | 1503 ms | 26200 KB | Output is correct |
4 | Correct | 1519 ms | 26208 KB | Output is correct |
5 | Correct | 1530 ms | 26324 KB | Output is correct |
6 | Correct | 2254 ms | 28152 KB | Output is correct |
7 | Correct | 2233 ms | 28132 KB | Output is correct |
8 | Correct | 2283 ms | 27992 KB | Output is correct |
9 | Correct | 47 ms | 2168 KB | Output is correct |
10 | Correct | 1270 ms | 28052 KB | Output is correct |
11 | Correct | 1160 ms | 28116 KB | Output is correct |
12 | Correct | 1292 ms | 24840 KB | Output is correct |
13 | Correct | 1331 ms | 27464 KB | Output is correct |
14 | Correct | 1190 ms | 18704 KB | Output is correct |
15 | Correct | 925 ms | 9848 KB | Output is correct |
16 | Correct | 1448 ms | 20636 KB | Output is correct |
17 | Correct | 1177 ms | 19048 KB | Output is correct |
18 | Correct | 45 ms | 2296 KB | Output is correct |
19 | Correct | 1350 ms | 18784 KB | Output is correct |
20 | Correct | 1079 ms | 18428 KB | Output is correct |
21 | Correct | 923 ms | 18432 KB | Output is correct |
22 | Correct | 773 ms | 17288 KB | Output is correct |
23 | Correct | 696 ms | 17232 KB | Output is correct |
24 | Correct | 829 ms | 20092 KB | Output is correct |
25 | Correct | 725 ms | 19956 KB | Output is correct |
26 | Correct | 1594 ms | 26452 KB | Output is correct |
27 | Correct | 1920 ms | 28232 KB | Output is correct |
28 | Correct | 1555 ms | 26324 KB | Output is correct |
29 | Correct | 1091 ms | 25808 KB | Output is correct |
30 | Correct | 1792 ms | 28020 KB | Output is correct |
31 | Correct | 1845 ms | 27968 KB | Output is correct |
32 | Correct | 1855 ms | 28232 KB | Output is correct |
33 | Correct | 1548 ms | 26308 KB | Output is correct |
34 | Correct | 1551 ms | 26204 KB | Output is correct |
35 | Correct | 1561 ms | 26412 KB | Output is correct |
36 | Correct | 1158 ms | 25808 KB | Output is correct |
37 | Correct | 1153 ms | 25936 KB | Output is correct |
38 | Correct | 1129 ms | 25976 KB | Output is correct |
39 | Correct | 939 ms | 24624 KB | Output is correct |
40 | Correct | 935 ms | 24592 KB | Output is correct |
41 | Correct | 927 ms | 24504 KB | Output is correct |
42 | Correct | 927 ms | 26584 KB | Output is correct |
43 | Correct | 924 ms | 26568 KB | Output is correct |
44 | Correct | 917 ms | 26464 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 376 KB | Output is correct |
2 | Correct | 5 ms | 376 KB | Output is correct |
3 | Correct | 45 ms | 2808 KB | Output is correct |
4 | Correct | 8 ms | 508 KB | Output is correct |
5 | Correct | 45 ms | 2936 KB | Output is correct |
6 | Correct | 34 ms | 2684 KB | Output is correct |
7 | Correct | 40 ms | 3576 KB | Output is correct |
8 | Correct | 45 ms | 2680 KB | Output is correct |
9 | Correct | 50 ms | 4344 KB | Output is correct |
10 | Correct | 45 ms | 2808 KB | Output is correct |
11 | Correct | 44 ms | 2680 KB | Output is correct |
12 | Correct | 54 ms | 2808 KB | Output is correct |
13 | Correct | 53 ms | 2784 KB | Output is correct |
14 | Correct | 49 ms | 2680 KB | Output is correct |
15 | Correct | 53 ms | 2680 KB | Output is correct |
16 | Correct | 48 ms | 3964 KB | Output is correct |
17 | Correct | 47 ms | 3448 KB | Output is correct |
18 | Correct | 1468 ms | 26344 KB | Output is correct |
19 | Correct | 1491 ms | 26308 KB | Output is correct |
20 | Correct | 1503 ms | 26200 KB | Output is correct |
21 | Correct | 1519 ms | 26208 KB | Output is correct |
22 | Correct | 1530 ms | 26324 KB | Output is correct |
23 | Correct | 2254 ms | 28152 KB | Output is correct |
24 | Correct | 2233 ms | 28132 KB | Output is correct |
25 | Correct | 2283 ms | 27992 KB | Output is correct |
26 | Correct | 47 ms | 2168 KB | Output is correct |
27 | Correct | 1270 ms | 28052 KB | Output is correct |
28 | Correct | 1160 ms | 28116 KB | Output is correct |
29 | Correct | 1292 ms | 24840 KB | Output is correct |
30 | Correct | 1331 ms | 27464 KB | Output is correct |
31 | Correct | 1190 ms | 18704 KB | Output is correct |
32 | Correct | 925 ms | 9848 KB | Output is correct |
33 | Correct | 1448 ms | 20636 KB | Output is correct |
34 | Correct | 1177 ms | 19048 KB | Output is correct |
35 | Correct | 45 ms | 2296 KB | Output is correct |
36 | Correct | 1350 ms | 18784 KB | Output is correct |
37 | Correct | 1079 ms | 18428 KB | Output is correct |
38 | Correct | 923 ms | 18432 KB | Output is correct |
39 | Correct | 773 ms | 17288 KB | Output is correct |
40 | Correct | 696 ms | 17232 KB | Output is correct |
41 | Correct | 829 ms | 20092 KB | Output is correct |
42 | Correct | 725 ms | 19956 KB | Output is correct |
43 | Correct | 1710 ms | 25228 KB | Output is correct |
44 | Correct | 47 ms | 2168 KB | Output is correct |
45 | Correct | 188 ms | 2760 KB | Output is correct |
46 | Correct | 92 ms | 2764 KB | Output is correct |
47 | Correct | 832 ms | 24976 KB | Output is correct |
48 | Correct | 1689 ms | 24956 KB | Output is correct |
49 | Correct | 831 ms | 24980 KB | Output is correct |
50 | Correct | 820 ms | 24272 KB | Output is correct |
51 | Correct | 824 ms | 24012 KB | Output is correct |
52 | Correct | 827 ms | 24276 KB | Output is correct |
53 | Correct | 1260 ms | 24772 KB | Output is correct |
54 | Correct | 1253 ms | 24912 KB | Output is correct |
55 | Correct | 1267 ms | 25152 KB | Output is correct |
56 | Correct | 748 ms | 25116 KB | Output is correct |
57 | Correct | 809 ms | 24948 KB | Output is correct |
58 | Correct | 1703 ms | 25408 KB | Output is correct |
59 | Correct | 1719 ms | 25248 KB | Output is correct |
60 | Correct | 1687 ms | 25312 KB | Output is correct |
61 | Correct | 1698 ms | 25316 KB | Output is correct |
62 | Correct | 1418 ms | 25348 KB | Output is correct |
63 | Correct | 1412 ms | 25376 KB | Output is correct |
64 | Correct | 1629 ms | 24952 KB | Output is correct |
65 | Correct | 947 ms | 22920 KB | Output is correct |
66 | Correct | 1594 ms | 26452 KB | Output is correct |
67 | Correct | 1920 ms | 28232 KB | Output is correct |
68 | Correct | 1555 ms | 26324 KB | Output is correct |
69 | Correct | 1091 ms | 25808 KB | Output is correct |
70 | Correct | 1792 ms | 28020 KB | Output is correct |
71 | Correct | 1845 ms | 27968 KB | Output is correct |
72 | Correct | 1855 ms | 28232 KB | Output is correct |
73 | Correct | 1548 ms | 26308 KB | Output is correct |
74 | Correct | 1551 ms | 26204 KB | Output is correct |
75 | Correct | 1561 ms | 26412 KB | Output is correct |
76 | Correct | 1158 ms | 25808 KB | Output is correct |
77 | Correct | 1153 ms | 25936 KB | Output is correct |
78 | Correct | 1129 ms | 25976 KB | Output is correct |
79 | Correct | 939 ms | 24624 KB | Output is correct |
80 | Correct | 935 ms | 24592 KB | Output is correct |
81 | Correct | 927 ms | 24504 KB | Output is correct |
82 | Correct | 927 ms | 26584 KB | Output is correct |
83 | Correct | 924 ms | 26568 KB | Output is correct |
84 | Correct | 917 ms | 26464 KB | Output is correct |
85 | Correct | 2210 ms | 27268 KB | Output is correct |
86 | Correct | 223 ms | 4832 KB | Output is correct |
87 | Correct | 137 ms | 6076 KB | Output is correct |
88 | Correct | 1340 ms | 29140 KB | Output is correct |
89 | Correct | 2219 ms | 27508 KB | Output is correct |
90 | Correct | 1320 ms | 28972 KB | Output is correct |
91 | Correct | 1615 ms | 26168 KB | Output is correct |
92 | Correct | 1620 ms | 26196 KB | Output is correct |
93 | Correct | 2326 ms | 27716 KB | Output is correct |
94 | Correct | 1875 ms | 27392 KB | Output is correct |
95 | Correct | 1856 ms | 27216 KB | Output is correct |
96 | Correct | 2213 ms | 29044 KB | Output is correct |
97 | Correct | 985 ms | 25736 KB | Output is correct |
98 | Correct | 1065 ms | 28824 KB | Output is correct |
99 | Correct | 2244 ms | 27732 KB | Output is correct |
100 | Correct | 2189 ms | 27668 KB | Output is correct |
101 | Correct | 2294 ms | 27812 KB | Output is correct |
102 | Correct | 2246 ms | 27936 KB | Output is correct |
103 | Correct | 2451 ms | 29344 KB | Output is correct |
104 | Correct | 2435 ms | 29456 KB | Output is correct |
105 | Correct | 1792 ms | 28832 KB | Output is correct |
106 | Correct | 1472 ms | 28800 KB | Output is correct |
107 | Correct | 1672 ms | 25816 KB | Output is correct |
108 | Correct | 2259 ms | 28068 KB | Output is correct |
109 | Correct | 1616 ms | 27156 KB | Output is correct |