#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
struct Edge
{
unsigned u, v, w;
bool operator<(Edge const &e) const { return w > e.w; }
};
struct Query
{
unsigned t, u, w, i;
bool operator<(Query const &q) const { return w > q.w; }
};
struct DSU
{
vector<int64_t> p, s;
stack<int64_t> operations;
DSU(size_t n) { p = vector<int64_t>(n, -1), s = vector<int64_t>(n, 1); }
int64_t find(int64_t u)
{
while (p[u] >= 0)
u = p[u];
return u;
}
void unite(int64_t u, int64_t v)
{
u = find(u), v = find(v);
if (u == v)
return;
if (s[u] < s[v])
swap(u, v);
operations.push(v);
s[u] += s[v];
p[v] = u;
}
int64_t component_size(int64_t u) { return s[find(u)]; }
void rollback(size_t n)
{
while (n--)
{
s[p[operations.top()]] -= s[operations.top()];
p[operations.top()] = -1;
operations.pop();
}
}
};
Edge e[100000];
Query queries[100000];
unsigned ans[100000];
bool is_changed[100000];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
size_t n, m;
cin >> n >> m;
for (size_t i = 0; i < m; i++)
{
cin >> e[i].u >> e[i].v >> e[i].w;
e[i].u--, e[i].v--;
}
size_t q;
cin >> q;
size_t const k = 17 * sqrt(q) / 10;
for (size_t i = 0; i < q; i++)
{
cin >> queries[i].t >> queries[i].u >> queries[i].w;
queries[i].u--;
queries[i].i = i;
}
for (size_t i = 0; i < q; i += k)
{
DSU y(n);
vector<unsigned> changed;
vector<Edge> unchanged;
vector<vector<unsigned>> join(k);
vector<Query> todo;
memset(is_changed, 0, 100000);
for (size_t j = i; j < min(q, i + k); j++)
{
if (queries[j].t == 1)
changed.push_back(queries[j].u), is_changed[queries[j].u] = 1;
else
todo.push_back(queries[j]);
}
sort(changed.begin(), changed.end());
changed.resize(unique(changed.begin(), changed.end()) - changed.begin());
for (size_t j = 0; j < m; j++)
if (!is_changed[j])
unchanged.push_back(e[j]);
for (size_t j = i; j < min(i + k, q); j++)
{
if (queries[j].t == 1)
e[queries[j].u].w = queries[j].w;
else
{
for (unsigned const &h : changed)
if (e[h].w >= queries[j].w)
join[j - i].push_back(h);
}
}
sort(unchanged.begin(), unchanged.end());
sort(todo.begin(), todo.end());
auto it = unchanged.begin();
for (Query const &x : todo)
{
while (it != unchanged.end() && it->w >= x.w)
y.unite(it->u, it->v), it++;
size_t s = y.operations.size();
for (unsigned const &j : join[x.i - i])
y.unite(e[j].u, e[j].v);
ans[x.i] = y.component_size(x.u);
y.rollback(y.operations.size() - s);
}
}
for (unsigned const &x : ans)
if (x)
cout << x << '\n';
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
328 KB |
Output is correct |
3 |
Correct |
14 ms |
836 KB |
Output is correct |
4 |
Correct |
4 ms |
724 KB |
Output is correct |
5 |
Correct |
8 ms |
796 KB |
Output is correct |
6 |
Correct |
7 ms |
724 KB |
Output is correct |
7 |
Correct |
8 ms |
736 KB |
Output is correct |
8 |
Correct |
9 ms |
724 KB |
Output is correct |
9 |
Correct |
10 ms |
724 KB |
Output is correct |
10 |
Correct |
11 ms |
724 KB |
Output is correct |
11 |
Correct |
11 ms |
852 KB |
Output is correct |
12 |
Correct |
13 ms |
788 KB |
Output is correct |
13 |
Correct |
12 ms |
804 KB |
Output is correct |
14 |
Correct |
11 ms |
724 KB |
Output is correct |
15 |
Correct |
10 ms |
724 KB |
Output is correct |
16 |
Correct |
9 ms |
724 KB |
Output is correct |
17 |
Correct |
9 ms |
724 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1415 ms |
6276 KB |
Output is correct |
2 |
Correct |
1459 ms |
6192 KB |
Output is correct |
3 |
Correct |
1478 ms |
6024 KB |
Output is correct |
4 |
Correct |
1394 ms |
5988 KB |
Output is correct |
5 |
Correct |
1380 ms |
6096 KB |
Output is correct |
6 |
Correct |
1739 ms |
6436 KB |
Output is correct |
7 |
Correct |
1742 ms |
6556 KB |
Output is correct |
8 |
Correct |
1791 ms |
6576 KB |
Output is correct |
9 |
Correct |
31 ms |
2848 KB |
Output is correct |
10 |
Correct |
939 ms |
6232 KB |
Output is correct |
11 |
Correct |
995 ms |
6176 KB |
Output is correct |
12 |
Correct |
1406 ms |
6400 KB |
Output is correct |
13 |
Correct |
1361 ms |
5476 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
987 ms |
4888 KB |
Output is correct |
2 |
Correct |
517 ms |
3712 KB |
Output is correct |
3 |
Correct |
1075 ms |
5312 KB |
Output is correct |
4 |
Correct |
993 ms |
4852 KB |
Output is correct |
5 |
Correct |
31 ms |
2832 KB |
Output is correct |
6 |
Correct |
1038 ms |
5128 KB |
Output is correct |
7 |
Correct |
918 ms |
4796 KB |
Output is correct |
8 |
Correct |
879 ms |
4908 KB |
Output is correct |
9 |
Correct |
813 ms |
5144 KB |
Output is correct |
10 |
Correct |
788 ms |
5064 KB |
Output is correct |
11 |
Correct |
818 ms |
4468 KB |
Output is correct |
12 |
Correct |
796 ms |
4556 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2559 ms |
7648 KB |
Output is correct |
2 |
Correct |
31 ms |
2824 KB |
Output is correct |
3 |
Correct |
721 ms |
4912 KB |
Output is correct |
4 |
Correct |
381 ms |
4804 KB |
Output is correct |
5 |
Correct |
1644 ms |
7324 KB |
Output is correct |
6 |
Correct |
2578 ms |
7564 KB |
Output is correct |
7 |
Correct |
1526 ms |
7604 KB |
Output is correct |
8 |
Correct |
1189 ms |
5384 KB |
Output is correct |
9 |
Correct |
1164 ms |
5464 KB |
Output is correct |
10 |
Correct |
1160 ms |
5428 KB |
Output is correct |
11 |
Correct |
1933 ms |
6752 KB |
Output is correct |
12 |
Correct |
1882 ms |
6748 KB |
Output is correct |
13 |
Correct |
1934 ms |
6856 KB |
Output is correct |
14 |
Correct |
1436 ms |
7488 KB |
Output is correct |
15 |
Correct |
1484 ms |
7476 KB |
Output is correct |
16 |
Correct |
2471 ms |
7412 KB |
Output is correct |
17 |
Correct |
2514 ms |
7428 KB |
Output is correct |
18 |
Correct |
2509 ms |
7444 KB |
Output is correct |
19 |
Correct |
2465 ms |
7492 KB |
Output is correct |
20 |
Correct |
2097 ms |
7228 KB |
Output is correct |
21 |
Correct |
2117 ms |
7080 KB |
Output is correct |
22 |
Correct |
2393 ms |
7188 KB |
Output is correct |
23 |
Correct |
1494 ms |
6992 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1415 ms |
6276 KB |
Output is correct |
2 |
Correct |
1459 ms |
6192 KB |
Output is correct |
3 |
Correct |
1478 ms |
6024 KB |
Output is correct |
4 |
Correct |
1394 ms |
5988 KB |
Output is correct |
5 |
Correct |
1380 ms |
6096 KB |
Output is correct |
6 |
Correct |
1739 ms |
6436 KB |
Output is correct |
7 |
Correct |
1742 ms |
6556 KB |
Output is correct |
8 |
Correct |
1791 ms |
6576 KB |
Output is correct |
9 |
Correct |
31 ms |
2848 KB |
Output is correct |
10 |
Correct |
939 ms |
6232 KB |
Output is correct |
11 |
Correct |
995 ms |
6176 KB |
Output is correct |
12 |
Correct |
1406 ms |
6400 KB |
Output is correct |
13 |
Correct |
1361 ms |
5476 KB |
Output is correct |
14 |
Correct |
987 ms |
4888 KB |
Output is correct |
15 |
Correct |
517 ms |
3712 KB |
Output is correct |
16 |
Correct |
1075 ms |
5312 KB |
Output is correct |
17 |
Correct |
993 ms |
4852 KB |
Output is correct |
18 |
Correct |
31 ms |
2832 KB |
Output is correct |
19 |
Correct |
1038 ms |
5128 KB |
Output is correct |
20 |
Correct |
918 ms |
4796 KB |
Output is correct |
21 |
Correct |
879 ms |
4908 KB |
Output is correct |
22 |
Correct |
813 ms |
5144 KB |
Output is correct |
23 |
Correct |
788 ms |
5064 KB |
Output is correct |
24 |
Correct |
818 ms |
4468 KB |
Output is correct |
25 |
Correct |
796 ms |
4556 KB |
Output is correct |
26 |
Correct |
1364 ms |
6356 KB |
Output is correct |
27 |
Correct |
1594 ms |
6324 KB |
Output is correct |
28 |
Correct |
1466 ms |
6100 KB |
Output is correct |
29 |
Correct |
1241 ms |
6236 KB |
Output is correct |
30 |
Correct |
1539 ms |
6148 KB |
Output is correct |
31 |
Correct |
1572 ms |
6516 KB |
Output is correct |
32 |
Correct |
1557 ms |
6144 KB |
Output is correct |
33 |
Correct |
1425 ms |
6064 KB |
Output is correct |
34 |
Correct |
1454 ms |
5948 KB |
Output is correct |
35 |
Correct |
1449 ms |
6024 KB |
Output is correct |
36 |
Correct |
1233 ms |
5912 KB |
Output is correct |
37 |
Correct |
1225 ms |
5764 KB |
Output is correct |
38 |
Correct |
1236 ms |
5944 KB |
Output is correct |
39 |
Correct |
1142 ms |
5776 KB |
Output is correct |
40 |
Correct |
1142 ms |
6480 KB |
Output is correct |
41 |
Correct |
1169 ms |
5764 KB |
Output is correct |
42 |
Correct |
1121 ms |
5992 KB |
Output is correct |
43 |
Correct |
1124 ms |
5848 KB |
Output is correct |
44 |
Correct |
1113 ms |
5700 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
328 KB |
Output is correct |
3 |
Correct |
14 ms |
836 KB |
Output is correct |
4 |
Correct |
4 ms |
724 KB |
Output is correct |
5 |
Correct |
8 ms |
796 KB |
Output is correct |
6 |
Correct |
7 ms |
724 KB |
Output is correct |
7 |
Correct |
8 ms |
736 KB |
Output is correct |
8 |
Correct |
9 ms |
724 KB |
Output is correct |
9 |
Correct |
10 ms |
724 KB |
Output is correct |
10 |
Correct |
11 ms |
724 KB |
Output is correct |
11 |
Correct |
11 ms |
852 KB |
Output is correct |
12 |
Correct |
13 ms |
788 KB |
Output is correct |
13 |
Correct |
12 ms |
804 KB |
Output is correct |
14 |
Correct |
11 ms |
724 KB |
Output is correct |
15 |
Correct |
10 ms |
724 KB |
Output is correct |
16 |
Correct |
9 ms |
724 KB |
Output is correct |
17 |
Correct |
9 ms |
724 KB |
Output is correct |
18 |
Correct |
1415 ms |
6276 KB |
Output is correct |
19 |
Correct |
1459 ms |
6192 KB |
Output is correct |
20 |
Correct |
1478 ms |
6024 KB |
Output is correct |
21 |
Correct |
1394 ms |
5988 KB |
Output is correct |
22 |
Correct |
1380 ms |
6096 KB |
Output is correct |
23 |
Correct |
1739 ms |
6436 KB |
Output is correct |
24 |
Correct |
1742 ms |
6556 KB |
Output is correct |
25 |
Correct |
1791 ms |
6576 KB |
Output is correct |
26 |
Correct |
31 ms |
2848 KB |
Output is correct |
27 |
Correct |
939 ms |
6232 KB |
Output is correct |
28 |
Correct |
995 ms |
6176 KB |
Output is correct |
29 |
Correct |
1406 ms |
6400 KB |
Output is correct |
30 |
Correct |
1361 ms |
5476 KB |
Output is correct |
31 |
Correct |
987 ms |
4888 KB |
Output is correct |
32 |
Correct |
517 ms |
3712 KB |
Output is correct |
33 |
Correct |
1075 ms |
5312 KB |
Output is correct |
34 |
Correct |
993 ms |
4852 KB |
Output is correct |
35 |
Correct |
31 ms |
2832 KB |
Output is correct |
36 |
Correct |
1038 ms |
5128 KB |
Output is correct |
37 |
Correct |
918 ms |
4796 KB |
Output is correct |
38 |
Correct |
879 ms |
4908 KB |
Output is correct |
39 |
Correct |
813 ms |
5144 KB |
Output is correct |
40 |
Correct |
788 ms |
5064 KB |
Output is correct |
41 |
Correct |
818 ms |
4468 KB |
Output is correct |
42 |
Correct |
796 ms |
4556 KB |
Output is correct |
43 |
Correct |
2559 ms |
7648 KB |
Output is correct |
44 |
Correct |
31 ms |
2824 KB |
Output is correct |
45 |
Correct |
721 ms |
4912 KB |
Output is correct |
46 |
Correct |
381 ms |
4804 KB |
Output is correct |
47 |
Correct |
1644 ms |
7324 KB |
Output is correct |
48 |
Correct |
2578 ms |
7564 KB |
Output is correct |
49 |
Correct |
1526 ms |
7604 KB |
Output is correct |
50 |
Correct |
1189 ms |
5384 KB |
Output is correct |
51 |
Correct |
1164 ms |
5464 KB |
Output is correct |
52 |
Correct |
1160 ms |
5428 KB |
Output is correct |
53 |
Correct |
1933 ms |
6752 KB |
Output is correct |
54 |
Correct |
1882 ms |
6748 KB |
Output is correct |
55 |
Correct |
1934 ms |
6856 KB |
Output is correct |
56 |
Correct |
1436 ms |
7488 KB |
Output is correct |
57 |
Correct |
1484 ms |
7476 KB |
Output is correct |
58 |
Correct |
2471 ms |
7412 KB |
Output is correct |
59 |
Correct |
2514 ms |
7428 KB |
Output is correct |
60 |
Correct |
2509 ms |
7444 KB |
Output is correct |
61 |
Correct |
2465 ms |
7492 KB |
Output is correct |
62 |
Correct |
2097 ms |
7228 KB |
Output is correct |
63 |
Correct |
2117 ms |
7080 KB |
Output is correct |
64 |
Correct |
2393 ms |
7188 KB |
Output is correct |
65 |
Correct |
1494 ms |
6992 KB |
Output is correct |
66 |
Correct |
1364 ms |
6356 KB |
Output is correct |
67 |
Correct |
1594 ms |
6324 KB |
Output is correct |
68 |
Correct |
1466 ms |
6100 KB |
Output is correct |
69 |
Correct |
1241 ms |
6236 KB |
Output is correct |
70 |
Correct |
1539 ms |
6148 KB |
Output is correct |
71 |
Correct |
1572 ms |
6516 KB |
Output is correct |
72 |
Correct |
1557 ms |
6144 KB |
Output is correct |
73 |
Correct |
1425 ms |
6064 KB |
Output is correct |
74 |
Correct |
1454 ms |
5948 KB |
Output is correct |
75 |
Correct |
1449 ms |
6024 KB |
Output is correct |
76 |
Correct |
1233 ms |
5912 KB |
Output is correct |
77 |
Correct |
1225 ms |
5764 KB |
Output is correct |
78 |
Correct |
1236 ms |
5944 KB |
Output is correct |
79 |
Correct |
1142 ms |
5776 KB |
Output is correct |
80 |
Correct |
1142 ms |
6480 KB |
Output is correct |
81 |
Correct |
1169 ms |
5764 KB |
Output is correct |
82 |
Correct |
1121 ms |
5992 KB |
Output is correct |
83 |
Correct |
1124 ms |
5848 KB |
Output is correct |
84 |
Correct |
1113 ms |
5700 KB |
Output is correct |
85 |
Correct |
2540 ms |
8256 KB |
Output is correct |
86 |
Correct |
709 ms |
4804 KB |
Output is correct |
87 |
Correct |
357 ms |
4800 KB |
Output is correct |
88 |
Correct |
1551 ms |
8144 KB |
Output is correct |
89 |
Correct |
2501 ms |
8096 KB |
Output is correct |
90 |
Correct |
1569 ms |
7952 KB |
Output is correct |
91 |
Correct |
1424 ms |
6196 KB |
Output is correct |
92 |
Correct |
1428 ms |
6184 KB |
Output is correct |
93 |
Correct |
1767 ms |
6496 KB |
Output is correct |
94 |
Correct |
2092 ms |
7184 KB |
Output is correct |
95 |
Correct |
1966 ms |
7208 KB |
Output is correct |
96 |
Correct |
2037 ms |
7376 KB |
Output is correct |
97 |
Correct |
1576 ms |
7636 KB |
Output is correct |
98 |
Correct |
1460 ms |
7900 KB |
Output is correct |
99 |
Correct |
2716 ms |
7704 KB |
Output is correct |
100 |
Correct |
2697 ms |
10968 KB |
Output is correct |
101 |
Correct |
2723 ms |
11068 KB |
Output is correct |
102 |
Correct |
2724 ms |
11316 KB |
Output is correct |
103 |
Correct |
2293 ms |
10476 KB |
Output is correct |
104 |
Correct |
2322 ms |
10600 KB |
Output is correct |
105 |
Correct |
2209 ms |
10184 KB |
Output is correct |
106 |
Correct |
1787 ms |
10184 KB |
Output is correct |
107 |
Correct |
2045 ms |
10468 KB |
Output is correct |
108 |
Correct |
2513 ms |
10688 KB |
Output is correct |
109 |
Correct |
1546 ms |
9520 KB |
Output is correct |