# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
633016 |
2022-08-21T12:06:39 Z |
erto |
Bridges (APIO19_bridges) |
C++17 |
|
2463 ms |
149172 KB |
#include <bits/stdc++.h>
typedef long long int ll;
#define INF 1000000007
#define INF2 998244353
#define N (int)(1e5+ 5)
using namespace std;
//#define int ll
#define lsb(x) (x & (-x))
const int K = 1000;
int n, m, cur=0, g, h, q;
int u[N], v[N], d[N];
int t[N], x[N], y[N], ans[N];
bool used[N];
vector<int> lis[N];
int p[N], sz[N];
vector<int> tb;
int get(int x){
while(x != p[x])x = p[x];
return x;
}
void unite(int x, int y){
int a = get(x), b = get(y);
if(a == b)return;
if(sz[a] < sz[b]){
swap(a, b);
}
p[b] = a;
sz[a] += sz[b];
tb.push_back(b);
}
void revert(int x){
while(tb.size() > x){
int t = tb.back();
sz[p[t]] -= sz[t];
p[t] = t;
tb.pop_back();
}
}
bool c1(int x, int y){
return d[x] > d[y];
}
bool c2(int a, int b){
return y[a] > y[b];
}
void solve(){
cin >> n >> m;
for(int i=1; i<=m; i++){
cin >> u[i] >> v[i] >> d[i];
}
cin >> q;
for(int i=1; i<=q; i++){
cin >> t[i] >> x[i] >> y[i];
}
for(int i=0; i<= q / K; i++){
int l = max(1, i * K), r = min((i + 1) * K, q + 1);
memset(used, 0, m + 1);
fill(sz + 1, sz + n + 1, 1);
iota(p + 1, p + n + 1, 1);
vector<int> ch, ask, uch;
for(int j=l; j<r; j++){
if(t[j] == 1){
used[x[j]] = 1;
ch.push_back(j);
}
else{
ask.push_back(j);
}
}
for(int j=l; j<r; j++){
if(t[j] == 2){
for(int u : ch){
if(d[x[u]] >= y[j]){
lis[j].push_back(x[u]);
}
}
}
else{
d[x[j]] = y[j];
}
}
for(int j=1; j<=m; j++){
if(!used[j])uch.push_back(j);
}
sort(uch.begin(), uch.end(), c1);
sort(ask.begin(), ask.end(), c2);
int p1 = 0;
for(int j : ask){
while(p1 < uch.size() && y[j] <= d[uch[p1]]){
unite(u[uch[p1]], v[uch[p1]]);
p1++;
}
int prev = tb.size();
for(int l : lis[j]){
unite(u[l], v[l]);
}
ans[j] = sz[get(x[j])];
revert(prev);
}
}
for(int i=1; i<=q; i++){
if(t[i] == 2)cout << ans[i] << '\n';
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int T = 1;
//cin>>T;
while (T--){
solve();
}
}
Compilation message
bridges.cpp: In function 'void revert(int)':
bridges.cpp:37:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
37 | while(tb.size() > x){
| ~~~~~~~~~~^~~
bridges.cpp: In function 'void solve()':
bridges.cpp:102:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
102 | while(p1 < uch.size() && y[j] <= d[uch[p1]]){
| ~~~^~~~~~~~~~~~
# |
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 |
38 ms |
9468 KB |
Output is correct |
4 |
Correct |
5 ms |
2772 KB |
Output is correct |
5 |
Correct |
38 ms |
10200 KB |
Output is correct |
6 |
Correct |
30 ms |
10424 KB |
Output is correct |
7 |
Correct |
35 ms |
10960 KB |
Output is correct |
8 |
Correct |
38 ms |
8908 KB |
Output is correct |
9 |
Correct |
47 ms |
14828 KB |
Output is correct |
10 |
Correct |
39 ms |
9676 KB |
Output is correct |
11 |
Correct |
39 ms |
9496 KB |
Output is correct |
12 |
Correct |
47 ms |
11980 KB |
Output is correct |
13 |
Correct |
45 ms |
10076 KB |
Output is correct |
14 |
Correct |
41 ms |
9332 KB |
Output is correct |
15 |
Correct |
47 ms |
10116 KB |
Output is correct |
16 |
Correct |
43 ms |
12940 KB |
Output is correct |
17 |
Correct |
42 ms |
12064 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1388 ms |
95556 KB |
Output is correct |
2 |
Correct |
1424 ms |
95268 KB |
Output is correct |
3 |
Correct |
1475 ms |
95508 KB |
Output is correct |
4 |
Correct |
1464 ms |
95264 KB |
Output is correct |
5 |
Correct |
1457 ms |
95688 KB |
Output is correct |
6 |
Correct |
2078 ms |
149172 KB |
Output is correct |
7 |
Correct |
2106 ms |
147092 KB |
Output is correct |
8 |
Correct |
2107 ms |
147196 KB |
Output is correct |
9 |
Correct |
35 ms |
4436 KB |
Output is correct |
10 |
Correct |
1180 ms |
118428 KB |
Output is correct |
11 |
Correct |
1140 ms |
117412 KB |
Output is correct |
12 |
Correct |
1345 ms |
78056 KB |
Output is correct |
13 |
Correct |
1464 ms |
72872 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1155 ms |
85332 KB |
Output is correct |
2 |
Correct |
792 ms |
101220 KB |
Output is correct |
3 |
Correct |
1345 ms |
113440 KB |
Output is correct |
4 |
Correct |
1113 ms |
84924 KB |
Output is correct |
5 |
Correct |
35 ms |
4396 KB |
Output is correct |
6 |
Correct |
1217 ms |
104632 KB |
Output is correct |
7 |
Correct |
1022 ms |
76792 KB |
Output is correct |
8 |
Correct |
943 ms |
60968 KB |
Output is correct |
9 |
Correct |
774 ms |
53076 KB |
Output is correct |
10 |
Correct |
691 ms |
41440 KB |
Output is correct |
11 |
Correct |
792 ms |
50140 KB |
Output is correct |
12 |
Correct |
717 ms |
40024 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1794 ms |
39496 KB |
Output is correct |
2 |
Correct |
38 ms |
5704 KB |
Output is correct |
3 |
Correct |
211 ms |
6844 KB |
Output is correct |
4 |
Correct |
88 ms |
7048 KB |
Output is correct |
5 |
Correct |
930 ms |
41824 KB |
Output is correct |
6 |
Correct |
1755 ms |
43328 KB |
Output is correct |
7 |
Correct |
907 ms |
41800 KB |
Output is correct |
8 |
Correct |
1048 ms |
41108 KB |
Output is correct |
9 |
Correct |
925 ms |
41256 KB |
Output is correct |
10 |
Correct |
845 ms |
41012 KB |
Output is correct |
11 |
Correct |
1399 ms |
42356 KB |
Output is correct |
12 |
Correct |
1255 ms |
42468 KB |
Output is correct |
13 |
Correct |
1269 ms |
42172 KB |
Output is correct |
14 |
Correct |
934 ms |
41868 KB |
Output is correct |
15 |
Correct |
878 ms |
41864 KB |
Output is correct |
16 |
Correct |
1865 ms |
43228 KB |
Output is correct |
17 |
Correct |
1760 ms |
43420 KB |
Output is correct |
18 |
Correct |
1756 ms |
43356 KB |
Output is correct |
19 |
Correct |
1696 ms |
43428 KB |
Output is correct |
20 |
Correct |
1479 ms |
42500 KB |
Output is correct |
21 |
Correct |
1815 ms |
42376 KB |
Output is correct |
22 |
Correct |
1860 ms |
43084 KB |
Output is correct |
23 |
Correct |
952 ms |
41240 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1388 ms |
95556 KB |
Output is correct |
2 |
Correct |
1424 ms |
95268 KB |
Output is correct |
3 |
Correct |
1475 ms |
95508 KB |
Output is correct |
4 |
Correct |
1464 ms |
95264 KB |
Output is correct |
5 |
Correct |
1457 ms |
95688 KB |
Output is correct |
6 |
Correct |
2078 ms |
149172 KB |
Output is correct |
7 |
Correct |
2106 ms |
147092 KB |
Output is correct |
8 |
Correct |
2107 ms |
147196 KB |
Output is correct |
9 |
Correct |
35 ms |
4436 KB |
Output is correct |
10 |
Correct |
1180 ms |
118428 KB |
Output is correct |
11 |
Correct |
1140 ms |
117412 KB |
Output is correct |
12 |
Correct |
1345 ms |
78056 KB |
Output is correct |
13 |
Correct |
1464 ms |
72872 KB |
Output is correct |
14 |
Correct |
1155 ms |
85332 KB |
Output is correct |
15 |
Correct |
792 ms |
101220 KB |
Output is correct |
16 |
Correct |
1345 ms |
113440 KB |
Output is correct |
17 |
Correct |
1113 ms |
84924 KB |
Output is correct |
18 |
Correct |
35 ms |
4396 KB |
Output is correct |
19 |
Correct |
1217 ms |
104632 KB |
Output is correct |
20 |
Correct |
1022 ms |
76792 KB |
Output is correct |
21 |
Correct |
943 ms |
60968 KB |
Output is correct |
22 |
Correct |
774 ms |
53076 KB |
Output is correct |
23 |
Correct |
691 ms |
41440 KB |
Output is correct |
24 |
Correct |
792 ms |
50140 KB |
Output is correct |
25 |
Correct |
717 ms |
40024 KB |
Output is correct |
26 |
Correct |
1471 ms |
95316 KB |
Output is correct |
27 |
Correct |
1766 ms |
120120 KB |
Output is correct |
28 |
Correct |
1474 ms |
93784 KB |
Output is correct |
29 |
Correct |
1086 ms |
57748 KB |
Output is correct |
30 |
Correct |
1744 ms |
108268 KB |
Output is correct |
31 |
Correct |
1888 ms |
109932 KB |
Output is correct |
32 |
Correct |
1732 ms |
110384 KB |
Output is correct |
33 |
Correct |
1482 ms |
94252 KB |
Output is correct |
34 |
Correct |
1605 ms |
94296 KB |
Output is correct |
35 |
Correct |
1517 ms |
94656 KB |
Output is correct |
36 |
Correct |
1198 ms |
63672 KB |
Output is correct |
37 |
Correct |
1159 ms |
62664 KB |
Output is correct |
38 |
Correct |
1125 ms |
61328 KB |
Output is correct |
39 |
Correct |
997 ms |
49056 KB |
Output is correct |
40 |
Correct |
967 ms |
48476 KB |
Output is correct |
41 |
Correct |
970 ms |
47960 KB |
Output is correct |
42 |
Correct |
1164 ms |
48204 KB |
Output is correct |
43 |
Correct |
934 ms |
47636 KB |
Output is correct |
44 |
Correct |
941 ms |
47108 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 |
38 ms |
9468 KB |
Output is correct |
4 |
Correct |
5 ms |
2772 KB |
Output is correct |
5 |
Correct |
38 ms |
10200 KB |
Output is correct |
6 |
Correct |
30 ms |
10424 KB |
Output is correct |
7 |
Correct |
35 ms |
10960 KB |
Output is correct |
8 |
Correct |
38 ms |
8908 KB |
Output is correct |
9 |
Correct |
47 ms |
14828 KB |
Output is correct |
10 |
Correct |
39 ms |
9676 KB |
Output is correct |
11 |
Correct |
39 ms |
9496 KB |
Output is correct |
12 |
Correct |
47 ms |
11980 KB |
Output is correct |
13 |
Correct |
45 ms |
10076 KB |
Output is correct |
14 |
Correct |
41 ms |
9332 KB |
Output is correct |
15 |
Correct |
47 ms |
10116 KB |
Output is correct |
16 |
Correct |
43 ms |
12940 KB |
Output is correct |
17 |
Correct |
42 ms |
12064 KB |
Output is correct |
18 |
Correct |
1388 ms |
95556 KB |
Output is correct |
19 |
Correct |
1424 ms |
95268 KB |
Output is correct |
20 |
Correct |
1475 ms |
95508 KB |
Output is correct |
21 |
Correct |
1464 ms |
95264 KB |
Output is correct |
22 |
Correct |
1457 ms |
95688 KB |
Output is correct |
23 |
Correct |
2078 ms |
149172 KB |
Output is correct |
24 |
Correct |
2106 ms |
147092 KB |
Output is correct |
25 |
Correct |
2107 ms |
147196 KB |
Output is correct |
26 |
Correct |
35 ms |
4436 KB |
Output is correct |
27 |
Correct |
1180 ms |
118428 KB |
Output is correct |
28 |
Correct |
1140 ms |
117412 KB |
Output is correct |
29 |
Correct |
1345 ms |
78056 KB |
Output is correct |
30 |
Correct |
1464 ms |
72872 KB |
Output is correct |
31 |
Correct |
1155 ms |
85332 KB |
Output is correct |
32 |
Correct |
792 ms |
101220 KB |
Output is correct |
33 |
Correct |
1345 ms |
113440 KB |
Output is correct |
34 |
Correct |
1113 ms |
84924 KB |
Output is correct |
35 |
Correct |
35 ms |
4396 KB |
Output is correct |
36 |
Correct |
1217 ms |
104632 KB |
Output is correct |
37 |
Correct |
1022 ms |
76792 KB |
Output is correct |
38 |
Correct |
943 ms |
60968 KB |
Output is correct |
39 |
Correct |
774 ms |
53076 KB |
Output is correct |
40 |
Correct |
691 ms |
41440 KB |
Output is correct |
41 |
Correct |
792 ms |
50140 KB |
Output is correct |
42 |
Correct |
717 ms |
40024 KB |
Output is correct |
43 |
Correct |
1794 ms |
39496 KB |
Output is correct |
44 |
Correct |
38 ms |
5704 KB |
Output is correct |
45 |
Correct |
211 ms |
6844 KB |
Output is correct |
46 |
Correct |
88 ms |
7048 KB |
Output is correct |
47 |
Correct |
930 ms |
41824 KB |
Output is correct |
48 |
Correct |
1755 ms |
43328 KB |
Output is correct |
49 |
Correct |
907 ms |
41800 KB |
Output is correct |
50 |
Correct |
1048 ms |
41108 KB |
Output is correct |
51 |
Correct |
925 ms |
41256 KB |
Output is correct |
52 |
Correct |
845 ms |
41012 KB |
Output is correct |
53 |
Correct |
1399 ms |
42356 KB |
Output is correct |
54 |
Correct |
1255 ms |
42468 KB |
Output is correct |
55 |
Correct |
1269 ms |
42172 KB |
Output is correct |
56 |
Correct |
934 ms |
41868 KB |
Output is correct |
57 |
Correct |
878 ms |
41864 KB |
Output is correct |
58 |
Correct |
1865 ms |
43228 KB |
Output is correct |
59 |
Correct |
1760 ms |
43420 KB |
Output is correct |
60 |
Correct |
1756 ms |
43356 KB |
Output is correct |
61 |
Correct |
1696 ms |
43428 KB |
Output is correct |
62 |
Correct |
1479 ms |
42500 KB |
Output is correct |
63 |
Correct |
1815 ms |
42376 KB |
Output is correct |
64 |
Correct |
1860 ms |
43084 KB |
Output is correct |
65 |
Correct |
952 ms |
41240 KB |
Output is correct |
66 |
Correct |
1471 ms |
95316 KB |
Output is correct |
67 |
Correct |
1766 ms |
120120 KB |
Output is correct |
68 |
Correct |
1474 ms |
93784 KB |
Output is correct |
69 |
Correct |
1086 ms |
57748 KB |
Output is correct |
70 |
Correct |
1744 ms |
108268 KB |
Output is correct |
71 |
Correct |
1888 ms |
109932 KB |
Output is correct |
72 |
Correct |
1732 ms |
110384 KB |
Output is correct |
73 |
Correct |
1482 ms |
94252 KB |
Output is correct |
74 |
Correct |
1605 ms |
94296 KB |
Output is correct |
75 |
Correct |
1517 ms |
94656 KB |
Output is correct |
76 |
Correct |
1198 ms |
63672 KB |
Output is correct |
77 |
Correct |
1159 ms |
62664 KB |
Output is correct |
78 |
Correct |
1125 ms |
61328 KB |
Output is correct |
79 |
Correct |
997 ms |
49056 KB |
Output is correct |
80 |
Correct |
967 ms |
48476 KB |
Output is correct |
81 |
Correct |
970 ms |
47960 KB |
Output is correct |
82 |
Correct |
1164 ms |
48204 KB |
Output is correct |
83 |
Correct |
934 ms |
47636 KB |
Output is correct |
84 |
Correct |
941 ms |
47108 KB |
Output is correct |
85 |
Correct |
2352 ms |
101004 KB |
Output is correct |
86 |
Correct |
222 ms |
13612 KB |
Output is correct |
87 |
Correct |
135 ms |
17964 KB |
Output is correct |
88 |
Correct |
1403 ms |
110716 KB |
Output is correct |
89 |
Correct |
2260 ms |
100072 KB |
Output is correct |
90 |
Correct |
1403 ms |
118736 KB |
Output is correct |
91 |
Correct |
1564 ms |
98108 KB |
Output is correct |
92 |
Correct |
1567 ms |
98152 KB |
Output is correct |
93 |
Correct |
2099 ms |
132748 KB |
Output is correct |
94 |
Correct |
1881 ms |
98688 KB |
Output is correct |
95 |
Correct |
1905 ms |
98668 KB |
Output is correct |
96 |
Correct |
2093 ms |
137404 KB |
Output is correct |
97 |
Correct |
1084 ms |
70292 KB |
Output is correct |
98 |
Correct |
1143 ms |
67776 KB |
Output is correct |
99 |
Correct |
2221 ms |
101296 KB |
Output is correct |
100 |
Correct |
2238 ms |
100212 KB |
Output is correct |
101 |
Correct |
2463 ms |
99472 KB |
Output is correct |
102 |
Correct |
2287 ms |
99592 KB |
Output is correct |
103 |
Correct |
2279 ms |
142800 KB |
Output is correct |
104 |
Correct |
2359 ms |
141992 KB |
Output is correct |
105 |
Correct |
1817 ms |
76496 KB |
Output is correct |
106 |
Correct |
1383 ms |
59752 KB |
Output is correct |
107 |
Correct |
1582 ms |
81748 KB |
Output is correct |
108 |
Correct |
2099 ms |
132300 KB |
Output is correct |
109 |
Correct |
1499 ms |
142832 KB |
Output is correct |