# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
561820 |
2022-05-13T15:37:59 Z |
Je_O |
Bridges (APIO19_bridges) |
C++17 |
|
2047 ms |
29248 KB |
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("avx2")
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
const int N = 5e4 + 5;
const int M = 1e5 + 5;
const int BLOCK = 1050;
int u[M], v[M], w[M];
int t[M], x[M], y[M];
bool cek[M];
vector<int> join[BLOCK + 5];
int par[N], sz[N];
int ans[M];
stack<int> stk;
int find(int x){
while(par[x] != x)x = par[x];
return x;
}
void merge(int x, int y){
x = find(x); y = find(y);
if(x == y)return;
if(sz[x] > sz[y])swap(x, y);
stk.push(x);
par[x] = y;
sz[y] += sz[x];
return;
}
void rollback(int s){
while(stk.size() > s){
int x = stk.top(); stk.pop();
sz[par[x]] -= sz[x];
par[x] = x;
}
return;
}
int main(){
ios::sync_with_stdio(false); cin.tie(0); cout.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 i = 1; i <= q; i += BLOCK){
iota(par + 1, par + n + 1, 1);
fill(sz + 1, sz + n + 1, 1);
fill(cek + 1, cek + m + 1, false);
int l = i, r = min(i + BLOCK - 1, q);
vector<int> pending, ask;
for(int j = l; j <= r; ++j){
if(t[j] == 1){
cek[x[j]] = true;
pending.pb(j);
}else{
ask.pb(j);
}
}
vector<int> lst;
for(int j = 1; j <= m; ++j){
if(!cek[j])lst.pb(j);
}
for(int j = l; j <= r; ++j){
if(t[j] == 1){
w[x[j]] = y[j];
}else{
join[j - l].clear();
for(int k: pending){
if(w[x[k]] >= y[j]){
join[j - l].pb(x[k]);
}
}
}
}
sort(ask.begin(), ask.end(), [&](int a, int b) { return y[a] > y[b]; });
sort(lst.begin(), lst.end(), [&](int a, int b) { return w[a] > w[b]; });
int pt = 0;
for(int j: ask){
while(pt < lst.size() && w[lst[pt]] >= y[j]){
merge(u[lst[pt]], v[lst[pt]]);
++pt;
}
int s = stk.size();
for(int k: join[j - l])merge(u[k], v[k]);
ans[j] = sz[find(x[j])];
rollback(s);
}
}
for(int i = 1; i <= q; ++i){
if(t[i] == 2)cout << ans[i] << '\n';
}
return 0;
}
Compilation message
bridges.cpp: In function 'void rollback(int)':
bridges.cpp:41:22: warning: comparison of integer expressions of different signedness: 'std::stack<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
41 | while(stk.size() > s){
| ~~~~~~~~~~~^~~
bridges.cpp: In function 'int main()':
bridges.cpp:93:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | while(pt < lst.size() && w[lst[pt]] >= y[j]){
| ~~~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
37 ms |
3212 KB |
Output is correct |
4 |
Correct |
4 ms |
596 KB |
Output is correct |
5 |
Correct |
37 ms |
4112 KB |
Output is correct |
6 |
Correct |
26 ms |
2928 KB |
Output is correct |
7 |
Correct |
34 ms |
4760 KB |
Output is correct |
8 |
Correct |
37 ms |
3060 KB |
Output is correct |
9 |
Correct |
43 ms |
4816 KB |
Output is correct |
10 |
Correct |
39 ms |
3564 KB |
Output is correct |
11 |
Correct |
40 ms |
3116 KB |
Output is correct |
12 |
Correct |
44 ms |
3244 KB |
Output is correct |
13 |
Correct |
45 ms |
3308 KB |
Output is correct |
14 |
Correct |
40 ms |
2912 KB |
Output is correct |
15 |
Correct |
46 ms |
3096 KB |
Output is correct |
16 |
Correct |
38 ms |
4920 KB |
Output is correct |
17 |
Correct |
40 ms |
4240 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1261 ms |
27516 KB |
Output is correct |
2 |
Correct |
1261 ms |
27536 KB |
Output is correct |
3 |
Correct |
1244 ms |
27556 KB |
Output is correct |
4 |
Correct |
1319 ms |
27452 KB |
Output is correct |
5 |
Correct |
1296 ms |
27600 KB |
Output is correct |
6 |
Correct |
1948 ms |
28084 KB |
Output is correct |
7 |
Correct |
1976 ms |
28160 KB |
Output is correct |
8 |
Correct |
1968 ms |
28112 KB |
Output is correct |
9 |
Correct |
36 ms |
2972 KB |
Output is correct |
10 |
Correct |
1137 ms |
28128 KB |
Output is correct |
11 |
Correct |
1004 ms |
28176 KB |
Output is correct |
12 |
Correct |
1124 ms |
24716 KB |
Output is correct |
13 |
Correct |
1106 ms |
27684 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1041 ms |
20292 KB |
Output is correct |
2 |
Correct |
816 ms |
10660 KB |
Output is correct |
3 |
Correct |
1263 ms |
21060 KB |
Output is correct |
4 |
Correct |
1012 ms |
20420 KB |
Output is correct |
5 |
Correct |
38 ms |
2944 KB |
Output is correct |
6 |
Correct |
1189 ms |
20724 KB |
Output is correct |
7 |
Correct |
931 ms |
20056 KB |
Output is correct |
8 |
Correct |
817 ms |
19676 KB |
Output is correct |
9 |
Correct |
650 ms |
17356 KB |
Output is correct |
10 |
Correct |
575 ms |
17436 KB |
Output is correct |
11 |
Correct |
706 ms |
20304 KB |
Output is correct |
12 |
Correct |
607 ms |
20304 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1416 ms |
24884 KB |
Output is correct |
2 |
Correct |
36 ms |
2892 KB |
Output is correct |
3 |
Correct |
155 ms |
3536 KB |
Output is correct |
4 |
Correct |
74 ms |
3572 KB |
Output is correct |
5 |
Correct |
701 ms |
24956 KB |
Output is correct |
6 |
Correct |
1375 ms |
24952 KB |
Output is correct |
7 |
Correct |
699 ms |
24924 KB |
Output is correct |
8 |
Correct |
671 ms |
23996 KB |
Output is correct |
9 |
Correct |
668 ms |
24108 KB |
Output is correct |
10 |
Correct |
675 ms |
24116 KB |
Output is correct |
11 |
Correct |
1035 ms |
24784 KB |
Output is correct |
12 |
Correct |
1012 ms |
24648 KB |
Output is correct |
13 |
Correct |
1043 ms |
24832 KB |
Output is correct |
14 |
Correct |
641 ms |
24872 KB |
Output is correct |
15 |
Correct |
683 ms |
24932 KB |
Output is correct |
16 |
Correct |
1375 ms |
25272 KB |
Output is correct |
17 |
Correct |
1390 ms |
25132 KB |
Output is correct |
18 |
Correct |
1400 ms |
25240 KB |
Output is correct |
19 |
Correct |
1394 ms |
25408 KB |
Output is correct |
20 |
Correct |
1152 ms |
25188 KB |
Output is correct |
21 |
Correct |
1159 ms |
25036 KB |
Output is correct |
22 |
Correct |
1348 ms |
24988 KB |
Output is correct |
23 |
Correct |
779 ms |
22944 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1261 ms |
27516 KB |
Output is correct |
2 |
Correct |
1261 ms |
27536 KB |
Output is correct |
3 |
Correct |
1244 ms |
27556 KB |
Output is correct |
4 |
Correct |
1319 ms |
27452 KB |
Output is correct |
5 |
Correct |
1296 ms |
27600 KB |
Output is correct |
6 |
Correct |
1948 ms |
28084 KB |
Output is correct |
7 |
Correct |
1976 ms |
28160 KB |
Output is correct |
8 |
Correct |
1968 ms |
28112 KB |
Output is correct |
9 |
Correct |
36 ms |
2972 KB |
Output is correct |
10 |
Correct |
1137 ms |
28128 KB |
Output is correct |
11 |
Correct |
1004 ms |
28176 KB |
Output is correct |
12 |
Correct |
1124 ms |
24716 KB |
Output is correct |
13 |
Correct |
1106 ms |
27684 KB |
Output is correct |
14 |
Correct |
1041 ms |
20292 KB |
Output is correct |
15 |
Correct |
816 ms |
10660 KB |
Output is correct |
16 |
Correct |
1263 ms |
21060 KB |
Output is correct |
17 |
Correct |
1012 ms |
20420 KB |
Output is correct |
18 |
Correct |
38 ms |
2944 KB |
Output is correct |
19 |
Correct |
1189 ms |
20724 KB |
Output is correct |
20 |
Correct |
931 ms |
20056 KB |
Output is correct |
21 |
Correct |
817 ms |
19676 KB |
Output is correct |
22 |
Correct |
650 ms |
17356 KB |
Output is correct |
23 |
Correct |
575 ms |
17436 KB |
Output is correct |
24 |
Correct |
706 ms |
20304 KB |
Output is correct |
25 |
Correct |
607 ms |
20304 KB |
Output is correct |
26 |
Correct |
1385 ms |
27568 KB |
Output is correct |
27 |
Correct |
1619 ms |
28316 KB |
Output is correct |
28 |
Correct |
1336 ms |
27720 KB |
Output is correct |
29 |
Correct |
934 ms |
26564 KB |
Output is correct |
30 |
Correct |
1549 ms |
28316 KB |
Output is correct |
31 |
Correct |
1589 ms |
28268 KB |
Output is correct |
32 |
Correct |
1576 ms |
28072 KB |
Output is correct |
33 |
Correct |
1311 ms |
27408 KB |
Output is correct |
34 |
Correct |
1329 ms |
27396 KB |
Output is correct |
35 |
Correct |
1327 ms |
27516 KB |
Output is correct |
36 |
Correct |
989 ms |
26632 KB |
Output is correct |
37 |
Correct |
986 ms |
26500 KB |
Output is correct |
38 |
Correct |
952 ms |
26672 KB |
Output is correct |
39 |
Correct |
772 ms |
24496 KB |
Output is correct |
40 |
Correct |
802 ms |
24564 KB |
Output is correct |
41 |
Correct |
798 ms |
24380 KB |
Output is correct |
42 |
Correct |
839 ms |
26556 KB |
Output is correct |
43 |
Correct |
782 ms |
26676 KB |
Output is correct |
44 |
Correct |
763 ms |
26444 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
37 ms |
3212 KB |
Output is correct |
4 |
Correct |
4 ms |
596 KB |
Output is correct |
5 |
Correct |
37 ms |
4112 KB |
Output is correct |
6 |
Correct |
26 ms |
2928 KB |
Output is correct |
7 |
Correct |
34 ms |
4760 KB |
Output is correct |
8 |
Correct |
37 ms |
3060 KB |
Output is correct |
9 |
Correct |
43 ms |
4816 KB |
Output is correct |
10 |
Correct |
39 ms |
3564 KB |
Output is correct |
11 |
Correct |
40 ms |
3116 KB |
Output is correct |
12 |
Correct |
44 ms |
3244 KB |
Output is correct |
13 |
Correct |
45 ms |
3308 KB |
Output is correct |
14 |
Correct |
40 ms |
2912 KB |
Output is correct |
15 |
Correct |
46 ms |
3096 KB |
Output is correct |
16 |
Correct |
38 ms |
4920 KB |
Output is correct |
17 |
Correct |
40 ms |
4240 KB |
Output is correct |
18 |
Correct |
1261 ms |
27516 KB |
Output is correct |
19 |
Correct |
1261 ms |
27536 KB |
Output is correct |
20 |
Correct |
1244 ms |
27556 KB |
Output is correct |
21 |
Correct |
1319 ms |
27452 KB |
Output is correct |
22 |
Correct |
1296 ms |
27600 KB |
Output is correct |
23 |
Correct |
1948 ms |
28084 KB |
Output is correct |
24 |
Correct |
1976 ms |
28160 KB |
Output is correct |
25 |
Correct |
1968 ms |
28112 KB |
Output is correct |
26 |
Correct |
36 ms |
2972 KB |
Output is correct |
27 |
Correct |
1137 ms |
28128 KB |
Output is correct |
28 |
Correct |
1004 ms |
28176 KB |
Output is correct |
29 |
Correct |
1124 ms |
24716 KB |
Output is correct |
30 |
Correct |
1106 ms |
27684 KB |
Output is correct |
31 |
Correct |
1041 ms |
20292 KB |
Output is correct |
32 |
Correct |
816 ms |
10660 KB |
Output is correct |
33 |
Correct |
1263 ms |
21060 KB |
Output is correct |
34 |
Correct |
1012 ms |
20420 KB |
Output is correct |
35 |
Correct |
38 ms |
2944 KB |
Output is correct |
36 |
Correct |
1189 ms |
20724 KB |
Output is correct |
37 |
Correct |
931 ms |
20056 KB |
Output is correct |
38 |
Correct |
817 ms |
19676 KB |
Output is correct |
39 |
Correct |
650 ms |
17356 KB |
Output is correct |
40 |
Correct |
575 ms |
17436 KB |
Output is correct |
41 |
Correct |
706 ms |
20304 KB |
Output is correct |
42 |
Correct |
607 ms |
20304 KB |
Output is correct |
43 |
Correct |
1416 ms |
24884 KB |
Output is correct |
44 |
Correct |
36 ms |
2892 KB |
Output is correct |
45 |
Correct |
155 ms |
3536 KB |
Output is correct |
46 |
Correct |
74 ms |
3572 KB |
Output is correct |
47 |
Correct |
701 ms |
24956 KB |
Output is correct |
48 |
Correct |
1375 ms |
24952 KB |
Output is correct |
49 |
Correct |
699 ms |
24924 KB |
Output is correct |
50 |
Correct |
671 ms |
23996 KB |
Output is correct |
51 |
Correct |
668 ms |
24108 KB |
Output is correct |
52 |
Correct |
675 ms |
24116 KB |
Output is correct |
53 |
Correct |
1035 ms |
24784 KB |
Output is correct |
54 |
Correct |
1012 ms |
24648 KB |
Output is correct |
55 |
Correct |
1043 ms |
24832 KB |
Output is correct |
56 |
Correct |
641 ms |
24872 KB |
Output is correct |
57 |
Correct |
683 ms |
24932 KB |
Output is correct |
58 |
Correct |
1375 ms |
25272 KB |
Output is correct |
59 |
Correct |
1390 ms |
25132 KB |
Output is correct |
60 |
Correct |
1400 ms |
25240 KB |
Output is correct |
61 |
Correct |
1394 ms |
25408 KB |
Output is correct |
62 |
Correct |
1152 ms |
25188 KB |
Output is correct |
63 |
Correct |
1159 ms |
25036 KB |
Output is correct |
64 |
Correct |
1348 ms |
24988 KB |
Output is correct |
65 |
Correct |
779 ms |
22944 KB |
Output is correct |
66 |
Correct |
1385 ms |
27568 KB |
Output is correct |
67 |
Correct |
1619 ms |
28316 KB |
Output is correct |
68 |
Correct |
1336 ms |
27720 KB |
Output is correct |
69 |
Correct |
934 ms |
26564 KB |
Output is correct |
70 |
Correct |
1549 ms |
28316 KB |
Output is correct |
71 |
Correct |
1589 ms |
28268 KB |
Output is correct |
72 |
Correct |
1576 ms |
28072 KB |
Output is correct |
73 |
Correct |
1311 ms |
27408 KB |
Output is correct |
74 |
Correct |
1329 ms |
27396 KB |
Output is correct |
75 |
Correct |
1327 ms |
27516 KB |
Output is correct |
76 |
Correct |
989 ms |
26632 KB |
Output is correct |
77 |
Correct |
986 ms |
26500 KB |
Output is correct |
78 |
Correct |
952 ms |
26672 KB |
Output is correct |
79 |
Correct |
772 ms |
24496 KB |
Output is correct |
80 |
Correct |
802 ms |
24564 KB |
Output is correct |
81 |
Correct |
798 ms |
24380 KB |
Output is correct |
82 |
Correct |
839 ms |
26556 KB |
Output is correct |
83 |
Correct |
782 ms |
26676 KB |
Output is correct |
84 |
Correct |
763 ms |
26444 KB |
Output is correct |
85 |
Correct |
1830 ms |
28480 KB |
Output is correct |
86 |
Correct |
180 ms |
5916 KB |
Output is correct |
87 |
Correct |
127 ms |
7868 KB |
Output is correct |
88 |
Correct |
1132 ms |
29204 KB |
Output is correct |
89 |
Correct |
1859 ms |
28576 KB |
Output is correct |
90 |
Correct |
1127 ms |
29248 KB |
Output is correct |
91 |
Correct |
1352 ms |
27532 KB |
Output is correct |
92 |
Correct |
1351 ms |
27572 KB |
Output is correct |
93 |
Correct |
2008 ms |
28204 KB |
Output is correct |
94 |
Correct |
1568 ms |
28500 KB |
Output is correct |
95 |
Correct |
1568 ms |
28472 KB |
Output is correct |
96 |
Correct |
1880 ms |
28876 KB |
Output is correct |
97 |
Correct |
817 ms |
25696 KB |
Output is correct |
98 |
Correct |
913 ms |
28780 KB |
Output is correct |
99 |
Correct |
1864 ms |
28880 KB |
Output is correct |
100 |
Correct |
1837 ms |
28580 KB |
Output is correct |
101 |
Correct |
1899 ms |
28780 KB |
Output is correct |
102 |
Correct |
1865 ms |
28792 KB |
Output is correct |
103 |
Correct |
2047 ms |
29016 KB |
Output is correct |
104 |
Correct |
2033 ms |
29048 KB |
Output is correct |
105 |
Correct |
1492 ms |
28692 KB |
Output is correct |
106 |
Correct |
1201 ms |
28580 KB |
Output is correct |
107 |
Correct |
1386 ms |
26080 KB |
Output is correct |
108 |
Correct |
1908 ms |
28880 KB |
Output is correct |
109 |
Correct |
1431 ms |
26860 KB |
Output is correct |