#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;
struct Node{
int u, sz_u, v, sz_v;
};
struct Query{
int type, a, b, idx;
};
const int sq = 750;
int n, m, q;
int p[50010], sz[50010];
Node st[100010];
int cz;
pii edges[100010];
vector<int> eg;
int w[100010];
Query qry[100010];
int ans[100010];
void init(){
iota(p, p + n + 1, 0);
fill(sz, sz + n + 1, 1);
cz = 0;
}
int findR(int x){
return p[x] == x ? x : findR(p[x]);
}
void join(int a, int b){
a = findR(a), b = findR(b);
st[cz++] = Node({a, sz[a], b, sz[b]});
if(a == b) return;
if(sz[a] > sz[b]) swap(a, b);
p[a] = b;
sz[b] += sz[a];
}
void rollback(){
Node x = st[--cz];
p[x.u] = x.u;
p[x.v] = x.v;
sz[x.u] = x.sz_u;
sz[x.v] = x.sz_v;
}
bool cmp(Query a, Query b){
return a.b > b.b;
}
bool egCmp(int a, int b){
return w[a] > w[b];
}
bitset<100010> dead, vis;
void Process(int l, int r){
vector<Query> updates, queries;
for(int i = l; i <= r; i++){
if(qry[i].type == 1) updates.emplace_back(qry[i]);
else queries.emplace_back(qry[i]);
}
sort(queries.begin(), queries.end(), cmp);
sort(eg.begin(), eg.end(), egCmp);
//We process from rightmost to leftmost, getting the most updated weight of edge
reverse(updates.begin(), updates.end());
for(auto &k : updates) dead[k.a] = true;
int id = 0;
init();
for(auto &k : queries){
while(id < m && w[eg[id]] >= k.b){
if(!dead[eg[id]]) join(edges[eg[id]].fi, edges[eg[id]].se);
id++;
}
int cur_size = cz;
for(auto &ed : updates){
if(ed.idx < k.idx){
if(vis[ed.a]) continue;
vis[ed.a] = true;
if(ed.b >= k.b) join(edges[ed.a].fi, edges[ed.a].se);
}
}
for(auto &ed : updates){
if(ed.idx < k.idx) break;
if(!vis[ed.a] && w[ed.a] >= k.b) join(edges[ed.a].fi, edges[ed.a].se);
}
ans[k.idx] = sz[findR(k.a)];
for(auto &ed : updates){
vis[ed.a] = false;
}
while(cz > cur_size) rollback();
}
for(auto &k : updates){
if(!dead[k.a]) continue;
dead[k.a] = false;
w[k.a] = k.b;
}
}
int main(){
// cerr << sq << "\n";
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; i++){
scanf("%d%d%d", &edges[i].fi, &edges[i].se, &w[i]);
}
scanf("%d", &q);
for(int i = 1; i <= q; i++){
scanf("%d%d%d", &qry[i].type, &qry[i].a, &qry[i].b);
qry[i].idx = i;
}
memset(ans, -1, sizeof(ans));
eg.resize(m);
iota(eg.begin(), eg.end(), 1);
for(int i = 0; i * sq + 1 <= q; i++){
Process(i * sq + 1, min(q, (i + 1) * sq));
}
for(int i = 1; i <= q; i++){
if(ans[i] == -1) continue;
printf("%d\n", ans[i]);
}
return 0;
}
Compilation message
bridges.cpp: In function 'int main()':
bridges.cpp:137:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~
bridges.cpp:140:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &edges[i].fi, &edges[i].se, &w[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:143:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &q);
~~~~~^~~~~~~~~~
bridges.cpp:146:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &qry[i].type, &qry[i].a, &qry[i].b);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
768 KB |
Output is correct |
2 |
Correct |
1 ms |
768 KB |
Output is correct |
3 |
Correct |
35 ms |
1024 KB |
Output is correct |
4 |
Correct |
6 ms |
1024 KB |
Output is correct |
5 |
Correct |
30 ms |
1024 KB |
Output is correct |
6 |
Correct |
28 ms |
1024 KB |
Output is correct |
7 |
Correct |
28 ms |
1044 KB |
Output is correct |
8 |
Correct |
28 ms |
1024 KB |
Output is correct |
9 |
Correct |
30 ms |
1024 KB |
Output is correct |
10 |
Correct |
29 ms |
1024 KB |
Output is correct |
11 |
Correct |
29 ms |
1024 KB |
Output is correct |
12 |
Correct |
30 ms |
1024 KB |
Output is correct |
13 |
Correct |
35 ms |
1024 KB |
Output is correct |
14 |
Correct |
33 ms |
1152 KB |
Output is correct |
15 |
Correct |
31 ms |
1024 KB |
Output is correct |
16 |
Correct |
30 ms |
1024 KB |
Output is correct |
17 |
Correct |
29 ms |
1024 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1384 ms |
4356 KB |
Output is correct |
2 |
Correct |
1372 ms |
4600 KB |
Output is correct |
3 |
Correct |
1372 ms |
4600 KB |
Output is correct |
4 |
Correct |
1453 ms |
4728 KB |
Output is correct |
5 |
Correct |
1462 ms |
4540 KB |
Output is correct |
6 |
Correct |
1962 ms |
4856 KB |
Output is correct |
7 |
Correct |
1987 ms |
4728 KB |
Output is correct |
8 |
Correct |
1942 ms |
4856 KB |
Output is correct |
9 |
Correct |
48 ms |
2684 KB |
Output is correct |
10 |
Correct |
1188 ms |
4672 KB |
Output is correct |
11 |
Correct |
1111 ms |
4728 KB |
Output is correct |
12 |
Correct |
1280 ms |
5112 KB |
Output is correct |
13 |
Correct |
1222 ms |
4656 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1030 ms |
3696 KB |
Output is correct |
2 |
Correct |
658 ms |
2936 KB |
Output is correct |
3 |
Correct |
1146 ms |
4004 KB |
Output is correct |
4 |
Correct |
997 ms |
4008 KB |
Output is correct |
5 |
Correct |
47 ms |
2552 KB |
Output is correct |
6 |
Correct |
1074 ms |
3996 KB |
Output is correct |
7 |
Correct |
942 ms |
4088 KB |
Output is correct |
8 |
Correct |
879 ms |
3960 KB |
Output is correct |
9 |
Correct |
736 ms |
4128 KB |
Output is correct |
10 |
Correct |
733 ms |
4088 KB |
Output is correct |
11 |
Correct |
742 ms |
3960 KB |
Output is correct |
12 |
Correct |
672 ms |
3960 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1440 ms |
6392 KB |
Output is correct |
2 |
Correct |
49 ms |
2552 KB |
Output is correct |
3 |
Correct |
170 ms |
4380 KB |
Output is correct |
4 |
Correct |
120 ms |
4216 KB |
Output is correct |
5 |
Correct |
1087 ms |
6592 KB |
Output is correct |
6 |
Correct |
1410 ms |
6524 KB |
Output is correct |
7 |
Correct |
1111 ms |
6648 KB |
Output is correct |
8 |
Correct |
710 ms |
4656 KB |
Output is correct |
9 |
Correct |
715 ms |
4768 KB |
Output is correct |
10 |
Correct |
700 ms |
4856 KB |
Output is correct |
11 |
Correct |
1082 ms |
5624 KB |
Output is correct |
12 |
Correct |
1062 ms |
5624 KB |
Output is correct |
13 |
Correct |
1104 ms |
5696 KB |
Output is correct |
14 |
Correct |
1100 ms |
6648 KB |
Output is correct |
15 |
Correct |
1087 ms |
6628 KB |
Output is correct |
16 |
Correct |
1453 ms |
6520 KB |
Output is correct |
17 |
Correct |
1437 ms |
6520 KB |
Output is correct |
18 |
Correct |
1484 ms |
6456 KB |
Output is correct |
19 |
Correct |
1453 ms |
6520 KB |
Output is correct |
20 |
Correct |
1236 ms |
6092 KB |
Output is correct |
21 |
Correct |
1233 ms |
6136 KB |
Output is correct |
22 |
Correct |
1400 ms |
6520 KB |
Output is correct |
23 |
Correct |
1038 ms |
6136 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1384 ms |
4356 KB |
Output is correct |
2 |
Correct |
1372 ms |
4600 KB |
Output is correct |
3 |
Correct |
1372 ms |
4600 KB |
Output is correct |
4 |
Correct |
1453 ms |
4728 KB |
Output is correct |
5 |
Correct |
1462 ms |
4540 KB |
Output is correct |
6 |
Correct |
1962 ms |
4856 KB |
Output is correct |
7 |
Correct |
1987 ms |
4728 KB |
Output is correct |
8 |
Correct |
1942 ms |
4856 KB |
Output is correct |
9 |
Correct |
48 ms |
2684 KB |
Output is correct |
10 |
Correct |
1188 ms |
4672 KB |
Output is correct |
11 |
Correct |
1111 ms |
4728 KB |
Output is correct |
12 |
Correct |
1280 ms |
5112 KB |
Output is correct |
13 |
Correct |
1222 ms |
4656 KB |
Output is correct |
14 |
Correct |
1030 ms |
3696 KB |
Output is correct |
15 |
Correct |
658 ms |
2936 KB |
Output is correct |
16 |
Correct |
1146 ms |
4004 KB |
Output is correct |
17 |
Correct |
997 ms |
4008 KB |
Output is correct |
18 |
Correct |
47 ms |
2552 KB |
Output is correct |
19 |
Correct |
1074 ms |
3996 KB |
Output is correct |
20 |
Correct |
942 ms |
4088 KB |
Output is correct |
21 |
Correct |
879 ms |
3960 KB |
Output is correct |
22 |
Correct |
736 ms |
4128 KB |
Output is correct |
23 |
Correct |
733 ms |
4088 KB |
Output is correct |
24 |
Correct |
742 ms |
3960 KB |
Output is correct |
25 |
Correct |
672 ms |
3960 KB |
Output is correct |
26 |
Correct |
1460 ms |
4728 KB |
Output is correct |
27 |
Correct |
1659 ms |
4680 KB |
Output is correct |
28 |
Correct |
1466 ms |
4728 KB |
Output is correct |
29 |
Correct |
1225 ms |
4660 KB |
Output is correct |
30 |
Correct |
1647 ms |
4704 KB |
Output is correct |
31 |
Correct |
1657 ms |
4472 KB |
Output is correct |
32 |
Correct |
1654 ms |
4728 KB |
Output is correct |
33 |
Correct |
1441 ms |
4476 KB |
Output is correct |
34 |
Correct |
1486 ms |
4472 KB |
Output is correct |
35 |
Correct |
1466 ms |
4356 KB |
Output is correct |
36 |
Correct |
1251 ms |
4472 KB |
Output is correct |
37 |
Correct |
1238 ms |
4472 KB |
Output is correct |
38 |
Correct |
1233 ms |
4356 KB |
Output is correct |
39 |
Correct |
1096 ms |
4600 KB |
Output is correct |
40 |
Correct |
1118 ms |
4488 KB |
Output is correct |
41 |
Correct |
1092 ms |
4484 KB |
Output is correct |
42 |
Correct |
991 ms |
4472 KB |
Output is correct |
43 |
Correct |
996 ms |
4360 KB |
Output is correct |
44 |
Correct |
974 ms |
4608 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
768 KB |
Output is correct |
2 |
Correct |
1 ms |
768 KB |
Output is correct |
3 |
Correct |
35 ms |
1024 KB |
Output is correct |
4 |
Correct |
6 ms |
1024 KB |
Output is correct |
5 |
Correct |
30 ms |
1024 KB |
Output is correct |
6 |
Correct |
28 ms |
1024 KB |
Output is correct |
7 |
Correct |
28 ms |
1044 KB |
Output is correct |
8 |
Correct |
28 ms |
1024 KB |
Output is correct |
9 |
Correct |
30 ms |
1024 KB |
Output is correct |
10 |
Correct |
29 ms |
1024 KB |
Output is correct |
11 |
Correct |
29 ms |
1024 KB |
Output is correct |
12 |
Correct |
30 ms |
1024 KB |
Output is correct |
13 |
Correct |
35 ms |
1024 KB |
Output is correct |
14 |
Correct |
33 ms |
1152 KB |
Output is correct |
15 |
Correct |
31 ms |
1024 KB |
Output is correct |
16 |
Correct |
30 ms |
1024 KB |
Output is correct |
17 |
Correct |
29 ms |
1024 KB |
Output is correct |
18 |
Correct |
1384 ms |
4356 KB |
Output is correct |
19 |
Correct |
1372 ms |
4600 KB |
Output is correct |
20 |
Correct |
1372 ms |
4600 KB |
Output is correct |
21 |
Correct |
1453 ms |
4728 KB |
Output is correct |
22 |
Correct |
1462 ms |
4540 KB |
Output is correct |
23 |
Correct |
1962 ms |
4856 KB |
Output is correct |
24 |
Correct |
1987 ms |
4728 KB |
Output is correct |
25 |
Correct |
1942 ms |
4856 KB |
Output is correct |
26 |
Correct |
48 ms |
2684 KB |
Output is correct |
27 |
Correct |
1188 ms |
4672 KB |
Output is correct |
28 |
Correct |
1111 ms |
4728 KB |
Output is correct |
29 |
Correct |
1280 ms |
5112 KB |
Output is correct |
30 |
Correct |
1222 ms |
4656 KB |
Output is correct |
31 |
Correct |
1030 ms |
3696 KB |
Output is correct |
32 |
Correct |
658 ms |
2936 KB |
Output is correct |
33 |
Correct |
1146 ms |
4004 KB |
Output is correct |
34 |
Correct |
997 ms |
4008 KB |
Output is correct |
35 |
Correct |
47 ms |
2552 KB |
Output is correct |
36 |
Correct |
1074 ms |
3996 KB |
Output is correct |
37 |
Correct |
942 ms |
4088 KB |
Output is correct |
38 |
Correct |
879 ms |
3960 KB |
Output is correct |
39 |
Correct |
736 ms |
4128 KB |
Output is correct |
40 |
Correct |
733 ms |
4088 KB |
Output is correct |
41 |
Correct |
742 ms |
3960 KB |
Output is correct |
42 |
Correct |
672 ms |
3960 KB |
Output is correct |
43 |
Correct |
1440 ms |
6392 KB |
Output is correct |
44 |
Correct |
49 ms |
2552 KB |
Output is correct |
45 |
Correct |
170 ms |
4380 KB |
Output is correct |
46 |
Correct |
120 ms |
4216 KB |
Output is correct |
47 |
Correct |
1087 ms |
6592 KB |
Output is correct |
48 |
Correct |
1410 ms |
6524 KB |
Output is correct |
49 |
Correct |
1111 ms |
6648 KB |
Output is correct |
50 |
Correct |
710 ms |
4656 KB |
Output is correct |
51 |
Correct |
715 ms |
4768 KB |
Output is correct |
52 |
Correct |
700 ms |
4856 KB |
Output is correct |
53 |
Correct |
1082 ms |
5624 KB |
Output is correct |
54 |
Correct |
1062 ms |
5624 KB |
Output is correct |
55 |
Correct |
1104 ms |
5696 KB |
Output is correct |
56 |
Correct |
1100 ms |
6648 KB |
Output is correct |
57 |
Correct |
1087 ms |
6628 KB |
Output is correct |
58 |
Correct |
1453 ms |
6520 KB |
Output is correct |
59 |
Correct |
1437 ms |
6520 KB |
Output is correct |
60 |
Correct |
1484 ms |
6456 KB |
Output is correct |
61 |
Correct |
1453 ms |
6520 KB |
Output is correct |
62 |
Correct |
1236 ms |
6092 KB |
Output is correct |
63 |
Correct |
1233 ms |
6136 KB |
Output is correct |
64 |
Correct |
1400 ms |
6520 KB |
Output is correct |
65 |
Correct |
1038 ms |
6136 KB |
Output is correct |
66 |
Correct |
1460 ms |
4728 KB |
Output is correct |
67 |
Correct |
1659 ms |
4680 KB |
Output is correct |
68 |
Correct |
1466 ms |
4728 KB |
Output is correct |
69 |
Correct |
1225 ms |
4660 KB |
Output is correct |
70 |
Correct |
1647 ms |
4704 KB |
Output is correct |
71 |
Correct |
1657 ms |
4472 KB |
Output is correct |
72 |
Correct |
1654 ms |
4728 KB |
Output is correct |
73 |
Correct |
1441 ms |
4476 KB |
Output is correct |
74 |
Correct |
1486 ms |
4472 KB |
Output is correct |
75 |
Correct |
1466 ms |
4356 KB |
Output is correct |
76 |
Correct |
1251 ms |
4472 KB |
Output is correct |
77 |
Correct |
1238 ms |
4472 KB |
Output is correct |
78 |
Correct |
1233 ms |
4356 KB |
Output is correct |
79 |
Correct |
1096 ms |
4600 KB |
Output is correct |
80 |
Correct |
1118 ms |
4488 KB |
Output is correct |
81 |
Correct |
1092 ms |
4484 KB |
Output is correct |
82 |
Correct |
991 ms |
4472 KB |
Output is correct |
83 |
Correct |
996 ms |
4360 KB |
Output is correct |
84 |
Correct |
974 ms |
4608 KB |
Output is correct |
85 |
Correct |
2540 ms |
6136 KB |
Output is correct |
86 |
Correct |
256 ms |
4216 KB |
Output is correct |
87 |
Correct |
164 ms |
4216 KB |
Output is correct |
88 |
Correct |
1722 ms |
6136 KB |
Output is correct |
89 |
Correct |
2510 ms |
6136 KB |
Output is correct |
90 |
Correct |
1562 ms |
6136 KB |
Output is correct |
91 |
Correct |
1480 ms |
4472 KB |
Output is correct |
92 |
Correct |
1458 ms |
4472 KB |
Output is correct |
93 |
Correct |
2005 ms |
4600 KB |
Output is correct |
94 |
Correct |
2060 ms |
5368 KB |
Output is correct |
95 |
Correct |
2056 ms |
5368 KB |
Output is correct |
96 |
Correct |
2362 ms |
5272 KB |
Output is correct |
97 |
Correct |
1333 ms |
6288 KB |
Output is correct |
98 |
Correct |
1447 ms |
5908 KB |
Output is correct |
99 |
Correct |
2616 ms |
6136 KB |
Output is correct |
100 |
Correct |
2514 ms |
6264 KB |
Output is correct |
101 |
Correct |
2586 ms |
6168 KB |
Output is correct |
102 |
Correct |
2640 ms |
6136 KB |
Output is correct |
103 |
Correct |
2523 ms |
5652 KB |
Output is correct |
104 |
Correct |
2551 ms |
5784 KB |
Output is correct |
105 |
Correct |
2015 ms |
5496 KB |
Output is correct |
106 |
Correct |
1629 ms |
5148 KB |
Output is correct |
107 |
Correct |
1956 ms |
5880 KB |
Output is correct |
108 |
Correct |
2575 ms |
6136 KB |
Output is correct |
109 |
Correct |
1630 ms |
5528 KB |
Output is correct |