#include <bits/stdc++.h>
using namespace std;
void just_do_it();
int main() {
#ifdef KAMIRULEZ
freopen("kamirulez.inp", "r", stdin);
freopen("kamirulez.out", "w", stdout);
#endif
ios_base::sync_with_stdio(0);
cin.tie(0);
just_do_it();
return 0;
}
struct edge {
int u, v, w;
};
struct query {
int t, x, y, res;
};
const int maxN = 1e5 + 20;
const int block = 1000;
vector<pair<int, int>> adj[maxN];
edge E[maxN];
query Q[maxN];
bool imp_edge[maxN];
bool imp_node[maxN];
int depth[maxN];
int par[maxN];
int sz[maxN];
vector<int> comp[maxN];
vector<pair<int, int>> vals[maxN];
int flag_comp[maxN];
int flag_imp[maxN];
int root(int u) {
if (!par[u]) {
return u;
}
return (par[u] = root(par[u]));
}
void update(int u, int v) {
int ru = root(u);
int rv = root(v);
if (ru == rv) {
return;
}
if (depth[ru] > depth[rv]) {
swap(ru, rv);
}
par[ru] = rv;
sz[rv] += sz[ru];
if (comp[ru].size() > comp[rv].size()) {
swap(comp[ru], comp[rv]);
}
comp[rv].insert(comp[rv].end(), comp[ru].begin(), comp[ru].end());
if (depth[ru] == depth[rv]) {
depth[rv]++;
}
}
void dfs(int u, int w, int query_id) {
if (flag_imp[u] == query_id) {
return;
}
flag_imp[u] = query_id;
int ru = root(u);
if (flag_comp[ru] != query_id) {
Q[query_id].res += sz[ru];
flag_comp[ru] = query_id;
for (auto v: comp[ru]) {
dfs(v, w, query_id);
}
}
for (auto e: adj[u]) {
int v = e.first;
int edge_id = e.second;
int cur = (lower_bound(vals[edge_id].begin(), vals[edge_id].end(), make_pair(query_id, -1)) - 1)->second;
if (w <= cur) {
dfs(v, w, query_id);
}
}
}
void just_do_it() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; i++) {
cin >> E[i].u >> E[i].v >> E[i].w;
}
int q;
cin >> q;
for (int i = 0; i < q; i++) {
cin >> Q[i].t >> Q[i].x >> Q[i].y;
}
for (int i = 1; i <= n; i++) {
flag_comp[i] = -1;
flag_imp[i] = -1;
}
for (int block_id = 0; block_id <= (q - 1) / block; block_id++) {
int lt = block_id * block;
int rt = min((block_id + 1) * block - 1, q - 1);
for (int i = 1; i <= n; i++) {
adj[i].clear();
imp_node[i] = false;
}
for (int i = 1; i <= m; i++) {
imp_edge[i] = false;
}
vector<pair<int, int>> events;
for (int i = lt; i <= rt; i++) {
if (Q[i].t == 1) {
imp_edge[Q[i].x] = true;
}
else {
events.emplace_back(Q[i].y, -i);
}
}
for (int i = 1; i <= m; i++) {
if (imp_edge[i]) {
vals[i].clear();
vals[i].emplace_back(lt - 1, E[i].w);
int u = E[i].u;
int v = E[i].v;
imp_node[u] = true;
imp_node[v] = true;
adj[u].emplace_back(v, i);
adj[v].emplace_back(u, i);
}
else {
events.emplace_back(E[i].w, i);
}
}
for (int i = lt; i <= rt; i++) {
if (Q[i].t == 1) {
vals[Q[i].x].emplace_back(i, Q[i].y);
E[Q[i].x].w = Q[i].y;
}
}
for (int i = 1; i <= n; i++) {
depth[i] = 0;
par[i] = 0;
sz[i] = 1;
comp[i].clear();
if (imp_node[i]) {
comp[i].emplace_back(i);
}
}
sort(events.begin(), events.end(), greater<pair<int, int>>());
for (auto e: events) {
int id = e.second;
if (id > 0) {
int u = E[id].u;
int v = E[id].v;
update(u, v);
}
else {
id = -id;
int u = Q[id].x;
int w = Q[id].y;
Q[id].res = 0;
dfs(u, w, id);
}
}
}
for (int i = 0; i < q; i++) {
if (Q[i].t == 2) {
cout << Q[i].res << '\n';
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7380 KB |
Output is correct |
2 |
Correct |
4 ms |
7380 KB |
Output is correct |
3 |
Correct |
62 ms |
7636 KB |
Output is correct |
4 |
Correct |
7 ms |
7508 KB |
Output is correct |
5 |
Correct |
22 ms |
7596 KB |
Output is correct |
6 |
Correct |
17 ms |
7608 KB |
Output is correct |
7 |
Correct |
14 ms |
7596 KB |
Output is correct |
8 |
Correct |
12 ms |
7508 KB |
Output is correct |
9 |
Correct |
19 ms |
7600 KB |
Output is correct |
10 |
Correct |
13 ms |
7564 KB |
Output is correct |
11 |
Correct |
10 ms |
7508 KB |
Output is correct |
12 |
Correct |
14 ms |
7612 KB |
Output is correct |
13 |
Correct |
17 ms |
7508 KB |
Output is correct |
14 |
Correct |
14 ms |
7508 KB |
Output is correct |
15 |
Correct |
17 ms |
7604 KB |
Output is correct |
16 |
Correct |
14 ms |
7600 KB |
Output is correct |
17 |
Correct |
15 ms |
7508 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
713 ms |
15260 KB |
Output is correct |
2 |
Correct |
707 ms |
15360 KB |
Output is correct |
3 |
Correct |
682 ms |
15232 KB |
Output is correct |
4 |
Correct |
676 ms |
15184 KB |
Output is correct |
5 |
Correct |
692 ms |
15224 KB |
Output is correct |
6 |
Correct |
2234 ms |
15228 KB |
Output is correct |
7 |
Correct |
1599 ms |
15184 KB |
Output is correct |
8 |
Correct |
1256 ms |
15316 KB |
Output is correct |
9 |
Correct |
33 ms |
9064 KB |
Output is correct |
10 |
Correct |
1636 ms |
15436 KB |
Output is correct |
11 |
Correct |
1380 ms |
15408 KB |
Output is correct |
12 |
Correct |
829 ms |
12912 KB |
Output is correct |
13 |
Correct |
1031 ms |
16028 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
548 ms |
13872 KB |
Output is correct |
2 |
Correct |
769 ms |
10644 KB |
Output is correct |
3 |
Correct |
1349 ms |
13940 KB |
Output is correct |
4 |
Correct |
762 ms |
13760 KB |
Output is correct |
5 |
Correct |
34 ms |
9172 KB |
Output is correct |
6 |
Correct |
707 ms |
13976 KB |
Output is correct |
7 |
Correct |
636 ms |
13776 KB |
Output is correct |
8 |
Correct |
573 ms |
13804 KB |
Output is correct |
9 |
Correct |
559 ms |
12292 KB |
Output is correct |
10 |
Correct |
541 ms |
12068 KB |
Output is correct |
11 |
Correct |
582 ms |
14076 KB |
Output is correct |
12 |
Correct |
545 ms |
13972 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1419 ms |
13144 KB |
Output is correct |
2 |
Correct |
35 ms |
9164 KB |
Output is correct |
3 |
Correct |
136 ms |
10648 KB |
Output is correct |
4 |
Correct |
84 ms |
10668 KB |
Output is correct |
5 |
Correct |
1286 ms |
13140 KB |
Output is correct |
6 |
Correct |
1372 ms |
13220 KB |
Output is correct |
7 |
Correct |
1306 ms |
13244 KB |
Output is correct |
8 |
Correct |
743 ms |
11620 KB |
Output is correct |
9 |
Correct |
765 ms |
11544 KB |
Output is correct |
10 |
Correct |
749 ms |
11648 KB |
Output is correct |
11 |
Correct |
1257 ms |
12580 KB |
Output is correct |
12 |
Correct |
1375 ms |
12656 KB |
Output is correct |
13 |
Correct |
1190 ms |
12680 KB |
Output is correct |
14 |
Correct |
1151 ms |
13080 KB |
Output is correct |
15 |
Correct |
1198 ms |
13188 KB |
Output is correct |
16 |
Correct |
1444 ms |
13312 KB |
Output is correct |
17 |
Correct |
1552 ms |
13196 KB |
Output is correct |
18 |
Correct |
1444 ms |
13072 KB |
Output is correct |
19 |
Correct |
1576 ms |
13124 KB |
Output is correct |
20 |
Correct |
1250 ms |
12892 KB |
Output is correct |
21 |
Correct |
1325 ms |
12856 KB |
Output is correct |
22 |
Correct |
1474 ms |
13040 KB |
Output is correct |
23 |
Correct |
1298 ms |
12632 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
713 ms |
15260 KB |
Output is correct |
2 |
Correct |
707 ms |
15360 KB |
Output is correct |
3 |
Correct |
682 ms |
15232 KB |
Output is correct |
4 |
Correct |
676 ms |
15184 KB |
Output is correct |
5 |
Correct |
692 ms |
15224 KB |
Output is correct |
6 |
Correct |
2234 ms |
15228 KB |
Output is correct |
7 |
Correct |
1599 ms |
15184 KB |
Output is correct |
8 |
Correct |
1256 ms |
15316 KB |
Output is correct |
9 |
Correct |
33 ms |
9064 KB |
Output is correct |
10 |
Correct |
1636 ms |
15436 KB |
Output is correct |
11 |
Correct |
1380 ms |
15408 KB |
Output is correct |
12 |
Correct |
829 ms |
12912 KB |
Output is correct |
13 |
Correct |
1031 ms |
16028 KB |
Output is correct |
14 |
Correct |
548 ms |
13872 KB |
Output is correct |
15 |
Correct |
769 ms |
10644 KB |
Output is correct |
16 |
Correct |
1349 ms |
13940 KB |
Output is correct |
17 |
Correct |
762 ms |
13760 KB |
Output is correct |
18 |
Correct |
34 ms |
9172 KB |
Output is correct |
19 |
Correct |
707 ms |
13976 KB |
Output is correct |
20 |
Correct |
636 ms |
13776 KB |
Output is correct |
21 |
Correct |
573 ms |
13804 KB |
Output is correct |
22 |
Correct |
559 ms |
12292 KB |
Output is correct |
23 |
Correct |
541 ms |
12068 KB |
Output is correct |
24 |
Correct |
582 ms |
14076 KB |
Output is correct |
25 |
Correct |
545 ms |
13972 KB |
Output is correct |
26 |
Correct |
913 ms |
15400 KB |
Output is correct |
27 |
Correct |
1832 ms |
15416 KB |
Output is correct |
28 |
Correct |
1078 ms |
15316 KB |
Output is correct |
29 |
Correct |
822 ms |
15272 KB |
Output is correct |
30 |
Correct |
1478 ms |
15164 KB |
Output is correct |
31 |
Correct |
1503 ms |
15064 KB |
Output is correct |
32 |
Correct |
1604 ms |
15144 KB |
Output is correct |
33 |
Correct |
897 ms |
15148 KB |
Output is correct |
34 |
Correct |
927 ms |
15088 KB |
Output is correct |
35 |
Correct |
865 ms |
15048 KB |
Output is correct |
36 |
Correct |
754 ms |
15276 KB |
Output is correct |
37 |
Correct |
770 ms |
15224 KB |
Output is correct |
38 |
Correct |
783 ms |
15224 KB |
Output is correct |
39 |
Correct |
739 ms |
12832 KB |
Output is correct |
40 |
Correct |
771 ms |
12784 KB |
Output is correct |
41 |
Correct |
796 ms |
12792 KB |
Output is correct |
42 |
Correct |
750 ms |
15704 KB |
Output is correct |
43 |
Correct |
722 ms |
15912 KB |
Output is correct |
44 |
Correct |
731 ms |
15932 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
7380 KB |
Output is correct |
2 |
Correct |
4 ms |
7380 KB |
Output is correct |
3 |
Correct |
62 ms |
7636 KB |
Output is correct |
4 |
Correct |
7 ms |
7508 KB |
Output is correct |
5 |
Correct |
22 ms |
7596 KB |
Output is correct |
6 |
Correct |
17 ms |
7608 KB |
Output is correct |
7 |
Correct |
14 ms |
7596 KB |
Output is correct |
8 |
Correct |
12 ms |
7508 KB |
Output is correct |
9 |
Correct |
19 ms |
7600 KB |
Output is correct |
10 |
Correct |
13 ms |
7564 KB |
Output is correct |
11 |
Correct |
10 ms |
7508 KB |
Output is correct |
12 |
Correct |
14 ms |
7612 KB |
Output is correct |
13 |
Correct |
17 ms |
7508 KB |
Output is correct |
14 |
Correct |
14 ms |
7508 KB |
Output is correct |
15 |
Correct |
17 ms |
7604 KB |
Output is correct |
16 |
Correct |
14 ms |
7600 KB |
Output is correct |
17 |
Correct |
15 ms |
7508 KB |
Output is correct |
18 |
Correct |
713 ms |
15260 KB |
Output is correct |
19 |
Correct |
707 ms |
15360 KB |
Output is correct |
20 |
Correct |
682 ms |
15232 KB |
Output is correct |
21 |
Correct |
676 ms |
15184 KB |
Output is correct |
22 |
Correct |
692 ms |
15224 KB |
Output is correct |
23 |
Correct |
2234 ms |
15228 KB |
Output is correct |
24 |
Correct |
1599 ms |
15184 KB |
Output is correct |
25 |
Correct |
1256 ms |
15316 KB |
Output is correct |
26 |
Correct |
33 ms |
9064 KB |
Output is correct |
27 |
Correct |
1636 ms |
15436 KB |
Output is correct |
28 |
Correct |
1380 ms |
15408 KB |
Output is correct |
29 |
Correct |
829 ms |
12912 KB |
Output is correct |
30 |
Correct |
1031 ms |
16028 KB |
Output is correct |
31 |
Correct |
548 ms |
13872 KB |
Output is correct |
32 |
Correct |
769 ms |
10644 KB |
Output is correct |
33 |
Correct |
1349 ms |
13940 KB |
Output is correct |
34 |
Correct |
762 ms |
13760 KB |
Output is correct |
35 |
Correct |
34 ms |
9172 KB |
Output is correct |
36 |
Correct |
707 ms |
13976 KB |
Output is correct |
37 |
Correct |
636 ms |
13776 KB |
Output is correct |
38 |
Correct |
573 ms |
13804 KB |
Output is correct |
39 |
Correct |
559 ms |
12292 KB |
Output is correct |
40 |
Correct |
541 ms |
12068 KB |
Output is correct |
41 |
Correct |
582 ms |
14076 KB |
Output is correct |
42 |
Correct |
545 ms |
13972 KB |
Output is correct |
43 |
Correct |
1419 ms |
13144 KB |
Output is correct |
44 |
Correct |
35 ms |
9164 KB |
Output is correct |
45 |
Correct |
136 ms |
10648 KB |
Output is correct |
46 |
Correct |
84 ms |
10668 KB |
Output is correct |
47 |
Correct |
1286 ms |
13140 KB |
Output is correct |
48 |
Correct |
1372 ms |
13220 KB |
Output is correct |
49 |
Correct |
1306 ms |
13244 KB |
Output is correct |
50 |
Correct |
743 ms |
11620 KB |
Output is correct |
51 |
Correct |
765 ms |
11544 KB |
Output is correct |
52 |
Correct |
749 ms |
11648 KB |
Output is correct |
53 |
Correct |
1257 ms |
12580 KB |
Output is correct |
54 |
Correct |
1375 ms |
12656 KB |
Output is correct |
55 |
Correct |
1190 ms |
12680 KB |
Output is correct |
56 |
Correct |
1151 ms |
13080 KB |
Output is correct |
57 |
Correct |
1198 ms |
13188 KB |
Output is correct |
58 |
Correct |
1444 ms |
13312 KB |
Output is correct |
59 |
Correct |
1552 ms |
13196 KB |
Output is correct |
60 |
Correct |
1444 ms |
13072 KB |
Output is correct |
61 |
Correct |
1576 ms |
13124 KB |
Output is correct |
62 |
Correct |
1250 ms |
12892 KB |
Output is correct |
63 |
Correct |
1325 ms |
12856 KB |
Output is correct |
64 |
Correct |
1474 ms |
13040 KB |
Output is correct |
65 |
Correct |
1298 ms |
12632 KB |
Output is correct |
66 |
Correct |
913 ms |
15400 KB |
Output is correct |
67 |
Correct |
1832 ms |
15416 KB |
Output is correct |
68 |
Correct |
1078 ms |
15316 KB |
Output is correct |
69 |
Correct |
822 ms |
15272 KB |
Output is correct |
70 |
Correct |
1478 ms |
15164 KB |
Output is correct |
71 |
Correct |
1503 ms |
15064 KB |
Output is correct |
72 |
Correct |
1604 ms |
15144 KB |
Output is correct |
73 |
Correct |
897 ms |
15148 KB |
Output is correct |
74 |
Correct |
927 ms |
15088 KB |
Output is correct |
75 |
Correct |
865 ms |
15048 KB |
Output is correct |
76 |
Correct |
754 ms |
15276 KB |
Output is correct |
77 |
Correct |
770 ms |
15224 KB |
Output is correct |
78 |
Correct |
783 ms |
15224 KB |
Output is correct |
79 |
Correct |
739 ms |
12832 KB |
Output is correct |
80 |
Correct |
771 ms |
12784 KB |
Output is correct |
81 |
Correct |
796 ms |
12792 KB |
Output is correct |
82 |
Correct |
750 ms |
15704 KB |
Output is correct |
83 |
Correct |
722 ms |
15912 KB |
Output is correct |
84 |
Correct |
731 ms |
15932 KB |
Output is correct |
85 |
Correct |
2464 ms |
17592 KB |
Output is correct |
86 |
Correct |
234 ms |
10724 KB |
Output is correct |
87 |
Correct |
151 ms |
10792 KB |
Output is correct |
88 |
Correct |
2326 ms |
17468 KB |
Output is correct |
89 |
Correct |
2670 ms |
17516 KB |
Output is correct |
90 |
Correct |
2394 ms |
17212 KB |
Output is correct |
91 |
Correct |
757 ms |
15544 KB |
Output is correct |
92 |
Correct |
737 ms |
15460 KB |
Output is correct |
93 |
Correct |
762 ms |
15408 KB |
Output is correct |
94 |
Correct |
1136 ms |
17796 KB |
Output is correct |
95 |
Correct |
1127 ms |
17688 KB |
Output is correct |
96 |
Correct |
1336 ms |
17588 KB |
Output is correct |
97 |
Correct |
1605 ms |
14616 KB |
Output is correct |
98 |
Correct |
1794 ms |
18216 KB |
Output is correct |
99 |
Correct |
2234 ms |
17768 KB |
Output is correct |
100 |
Correct |
2271 ms |
17732 KB |
Output is correct |
101 |
Correct |
2110 ms |
18032 KB |
Output is correct |
102 |
Correct |
2008 ms |
17892 KB |
Output is correct |
103 |
Correct |
1630 ms |
17616 KB |
Output is correct |
104 |
Correct |
1559 ms |
17660 KB |
Output is correct |
105 |
Correct |
1505 ms |
19572 KB |
Output is correct |
106 |
Correct |
1204 ms |
19124 KB |
Output is correct |
107 |
Correct |
1311 ms |
14440 KB |
Output is correct |
108 |
Correct |
2898 ms |
17448 KB |
Output is correct |
109 |
Correct |
2606 ms |
18688 KB |
Output is correct |