#include <cstdio>
#include <algorithm>
#include <utility>
#include <vector>
#include <set>
struct dsu {
dsu *p;
int size;
dsu() {
p = 0;
size = 1;
}
void reset(int size_ = 1) {
p = 0;
size = size_;
}
dsu *find() {
if (!p) return this;
return p = p->find();
}
};
void unite(dsu *a, dsu *b)
{
a = a->find();
b = b->find();
if (a != b) {
if (a->size < b->size) std::swap(a, b);
b->p = a;
a->size += b->size;
}
}
const int N = 50000;
const int M = 100000;
const int K = 1000;
int n, m, q, a[M], b[M], aa[M], bb[M], w[M], t[M], x[M], y[M], ans[M], u[M], last[M];
dsu d[N], dd[N];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < m; ++i) {
scanf("%d%d%d", a + i, b + i, w + i);
--a[i];
--b[i];
}
scanf("%d", &q);
for (int i = 0; i < q; i += K) {
std::vector<std::pair<int, int> > ask;
for (int j = i; j < std::min(q, i + K); ++j) {
scanf("%d%d%d", t + j, x + j, y + j);
--x[j];
if (t[j] == 1) u[x[j]] = i + 1;
else ask.push_back(std::make_pair(y[j], j));
}
std::sort(ask.begin(), ask.end());
std::vector<std::pair<int, int> > s;
for (int j = 0; j < m; ++j) if (u[j] <= i) s.push_back(std::make_pair(w[j], j));
std::sort(s.begin(), s.end());
int it = (int)s.size() - 1;
for (int j = (int)ask.size() - 1; j >= 0; --j) {
while (it >= 0 && s[it].first >= ask[j].first) {
unite(d + a[s[it].second], d + b[s[it].second]);
--it;
}
for (int k = std::min(q, i + K) - 1; k >= i; --k) if (t[k] == 1) {
aa[k] = d[a[x[k]]].find() - d;
bb[k] = d[b[x[k]]].find() - d;
dd[aa[k]].reset(d[aa[k]].size);
dd[bb[k]].reset(d[bb[k]].size);
}
dd[d[x[ask[j].second]].find() - d].reset(d[x[ask[j].second]].find()->size);
for (int k = ask[j].second - 1; k >= i; --k) if (t[k] == 1 && last[x[k]] != ask[j].second + 1) {
if (y[k] >= ask[j].first) unite(dd + aa[k], dd + bb[k]);
last[x[k]] = ask[j].second + 1;
}
for (int k = std::min(q, i + K) - 1; k >= ask[j].second; --k) if (t[k] == 1 && last[x[k]] != ask[j].second + 1) {
if (w[x[k]] >= ask[j].first) unite(dd + aa[k], dd + bb[k]);
last[x[k]] = ask[j].second + 1;
}
ans[ask[j].second] = dd[d[x[ask[j].second]].find() - d].find()->size;
}
for (int j = i; j < std::min(q, i + K); ++j) if (t[j] == 1) w[x[j]] = y[j];
for (int i = 0; i < n; ++i) d[i].reset();
}
for (int i = 0; i < q; ++i) if (ans[i]) printf("%d\n", ans[i]);
return 0;
}
Compilation message
bridges.cpp: In function 'int main()':
bridges.cpp:43:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
43 | scanf("%d%d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~
bridges.cpp:45:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
45 | scanf("%d%d%d", a + i, b + i, w + i);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:49:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
49 | scanf("%d", &q);
| ~~~~~^~~~~~~~~~
bridges.cpp:53:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
53 | scanf("%d%d%d", t + j, x + j, y + j);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1868 KB |
Output is correct |
2 |
Correct |
1 ms |
1868 KB |
Output is correct |
3 |
Correct |
83 ms |
2100 KB |
Output is correct |
4 |
Correct |
22 ms |
1996 KB |
Output is correct |
5 |
Correct |
62 ms |
2024 KB |
Output is correct |
6 |
Correct |
59 ms |
2096 KB |
Output is correct |
7 |
Correct |
58 ms |
2116 KB |
Output is correct |
8 |
Correct |
62 ms |
2108 KB |
Output is correct |
9 |
Correct |
58 ms |
2096 KB |
Output is correct |
10 |
Correct |
62 ms |
2040 KB |
Output is correct |
11 |
Correct |
63 ms |
2116 KB |
Output is correct |
12 |
Correct |
64 ms |
2120 KB |
Output is correct |
13 |
Correct |
73 ms |
2068 KB |
Output is correct |
14 |
Correct |
68 ms |
2100 KB |
Output is correct |
15 |
Correct |
67 ms |
2012 KB |
Output is correct |
16 |
Correct |
59 ms |
2040 KB |
Output is correct |
17 |
Correct |
58 ms |
2020 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1996 ms |
6152 KB |
Output is correct |
2 |
Correct |
1983 ms |
6152 KB |
Output is correct |
3 |
Correct |
1959 ms |
6236 KB |
Output is correct |
4 |
Correct |
1984 ms |
6192 KB |
Output is correct |
5 |
Correct |
2009 ms |
6136 KB |
Output is correct |
6 |
Correct |
2308 ms |
6200 KB |
Output is correct |
7 |
Correct |
2315 ms |
6320 KB |
Output is correct |
8 |
Correct |
2301 ms |
6064 KB |
Output is correct |
9 |
Correct |
210 ms |
3652 KB |
Output is correct |
10 |
Correct |
1824 ms |
6208 KB |
Output is correct |
11 |
Correct |
1781 ms |
6040 KB |
Output is correct |
12 |
Correct |
1403 ms |
6008 KB |
Output is correct |
13 |
Correct |
1353 ms |
6292 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1508 ms |
5268 KB |
Output is correct |
2 |
Correct |
1160 ms |
4604 KB |
Output is correct |
3 |
Correct |
1607 ms |
5372 KB |
Output is correct |
4 |
Correct |
1507 ms |
5292 KB |
Output is correct |
5 |
Correct |
208 ms |
3656 KB |
Output is correct |
6 |
Correct |
1573 ms |
5396 KB |
Output is correct |
7 |
Correct |
1527 ms |
5488 KB |
Output is correct |
8 |
Correct |
1404 ms |
5552 KB |
Output is correct |
9 |
Correct |
1029 ms |
5276 KB |
Output is correct |
10 |
Correct |
987 ms |
5560 KB |
Output is correct |
11 |
Correct |
900 ms |
5316 KB |
Output is correct |
12 |
Correct |
902 ms |
5520 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1721 ms |
6600 KB |
Output is correct |
2 |
Correct |
206 ms |
3524 KB |
Output is correct |
3 |
Correct |
174 ms |
5004 KB |
Output is correct |
4 |
Correct |
146 ms |
4992 KB |
Output is correct |
5 |
Correct |
1636 ms |
6388 KB |
Output is correct |
6 |
Correct |
1715 ms |
6484 KB |
Output is correct |
7 |
Correct |
1677 ms |
6440 KB |
Output is correct |
8 |
Correct |
944 ms |
5080 KB |
Output is correct |
9 |
Correct |
960 ms |
5020 KB |
Output is correct |
10 |
Correct |
979 ms |
4864 KB |
Output is correct |
11 |
Correct |
1413 ms |
6404 KB |
Output is correct |
12 |
Correct |
1370 ms |
5996 KB |
Output is correct |
13 |
Correct |
1420 ms |
6028 KB |
Output is correct |
14 |
Correct |
1491 ms |
6468 KB |
Output is correct |
15 |
Correct |
1592 ms |
6568 KB |
Output is correct |
16 |
Correct |
1790 ms |
6508 KB |
Output is correct |
17 |
Correct |
1803 ms |
6512 KB |
Output is correct |
18 |
Correct |
1790 ms |
6364 KB |
Output is correct |
19 |
Correct |
1794 ms |
6308 KB |
Output is correct |
20 |
Correct |
1559 ms |
6252 KB |
Output is correct |
21 |
Correct |
1563 ms |
6188 KB |
Output is correct |
22 |
Correct |
1700 ms |
6372 KB |
Output is correct |
23 |
Correct |
1609 ms |
5992 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1996 ms |
6152 KB |
Output is correct |
2 |
Correct |
1983 ms |
6152 KB |
Output is correct |
3 |
Correct |
1959 ms |
6236 KB |
Output is correct |
4 |
Correct |
1984 ms |
6192 KB |
Output is correct |
5 |
Correct |
2009 ms |
6136 KB |
Output is correct |
6 |
Correct |
2308 ms |
6200 KB |
Output is correct |
7 |
Correct |
2315 ms |
6320 KB |
Output is correct |
8 |
Correct |
2301 ms |
6064 KB |
Output is correct |
9 |
Correct |
210 ms |
3652 KB |
Output is correct |
10 |
Correct |
1824 ms |
6208 KB |
Output is correct |
11 |
Correct |
1781 ms |
6040 KB |
Output is correct |
12 |
Correct |
1403 ms |
6008 KB |
Output is correct |
13 |
Correct |
1353 ms |
6292 KB |
Output is correct |
14 |
Correct |
1508 ms |
5268 KB |
Output is correct |
15 |
Correct |
1160 ms |
4604 KB |
Output is correct |
16 |
Correct |
1607 ms |
5372 KB |
Output is correct |
17 |
Correct |
1507 ms |
5292 KB |
Output is correct |
18 |
Correct |
208 ms |
3656 KB |
Output is correct |
19 |
Correct |
1573 ms |
5396 KB |
Output is correct |
20 |
Correct |
1527 ms |
5488 KB |
Output is correct |
21 |
Correct |
1404 ms |
5552 KB |
Output is correct |
22 |
Correct |
1029 ms |
5276 KB |
Output is correct |
23 |
Correct |
987 ms |
5560 KB |
Output is correct |
24 |
Correct |
900 ms |
5316 KB |
Output is correct |
25 |
Correct |
902 ms |
5520 KB |
Output is correct |
26 |
Correct |
1824 ms |
6288 KB |
Output is correct |
27 |
Correct |
1982 ms |
6208 KB |
Output is correct |
28 |
Correct |
1890 ms |
6144 KB |
Output is correct |
29 |
Correct |
1669 ms |
6096 KB |
Output is correct |
30 |
Correct |
2070 ms |
6048 KB |
Output is correct |
31 |
Correct |
2060 ms |
6028 KB |
Output is correct |
32 |
Correct |
2084 ms |
6112 KB |
Output is correct |
33 |
Correct |
1935 ms |
6212 KB |
Output is correct |
34 |
Correct |
1917 ms |
6072 KB |
Output is correct |
35 |
Correct |
1921 ms |
6012 KB |
Output is correct |
36 |
Correct |
1733 ms |
6160 KB |
Output is correct |
37 |
Correct |
1721 ms |
6184 KB |
Output is correct |
38 |
Correct |
1699 ms |
6344 KB |
Output is correct |
39 |
Correct |
1262 ms |
6120 KB |
Output is correct |
40 |
Correct |
1278 ms |
6152 KB |
Output is correct |
41 |
Correct |
1268 ms |
6212 KB |
Output is correct |
42 |
Correct |
1122 ms |
6064 KB |
Output is correct |
43 |
Correct |
1152 ms |
6152 KB |
Output is correct |
44 |
Correct |
1142 ms |
6180 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1868 KB |
Output is correct |
2 |
Correct |
1 ms |
1868 KB |
Output is correct |
3 |
Correct |
83 ms |
2100 KB |
Output is correct |
4 |
Correct |
22 ms |
1996 KB |
Output is correct |
5 |
Correct |
62 ms |
2024 KB |
Output is correct |
6 |
Correct |
59 ms |
2096 KB |
Output is correct |
7 |
Correct |
58 ms |
2116 KB |
Output is correct |
8 |
Correct |
62 ms |
2108 KB |
Output is correct |
9 |
Correct |
58 ms |
2096 KB |
Output is correct |
10 |
Correct |
62 ms |
2040 KB |
Output is correct |
11 |
Correct |
63 ms |
2116 KB |
Output is correct |
12 |
Correct |
64 ms |
2120 KB |
Output is correct |
13 |
Correct |
73 ms |
2068 KB |
Output is correct |
14 |
Correct |
68 ms |
2100 KB |
Output is correct |
15 |
Correct |
67 ms |
2012 KB |
Output is correct |
16 |
Correct |
59 ms |
2040 KB |
Output is correct |
17 |
Correct |
58 ms |
2020 KB |
Output is correct |
18 |
Correct |
1996 ms |
6152 KB |
Output is correct |
19 |
Correct |
1983 ms |
6152 KB |
Output is correct |
20 |
Correct |
1959 ms |
6236 KB |
Output is correct |
21 |
Correct |
1984 ms |
6192 KB |
Output is correct |
22 |
Correct |
2009 ms |
6136 KB |
Output is correct |
23 |
Correct |
2308 ms |
6200 KB |
Output is correct |
24 |
Correct |
2315 ms |
6320 KB |
Output is correct |
25 |
Correct |
2301 ms |
6064 KB |
Output is correct |
26 |
Correct |
210 ms |
3652 KB |
Output is correct |
27 |
Correct |
1824 ms |
6208 KB |
Output is correct |
28 |
Correct |
1781 ms |
6040 KB |
Output is correct |
29 |
Correct |
1403 ms |
6008 KB |
Output is correct |
30 |
Correct |
1353 ms |
6292 KB |
Output is correct |
31 |
Correct |
1508 ms |
5268 KB |
Output is correct |
32 |
Correct |
1160 ms |
4604 KB |
Output is correct |
33 |
Correct |
1607 ms |
5372 KB |
Output is correct |
34 |
Correct |
1507 ms |
5292 KB |
Output is correct |
35 |
Correct |
208 ms |
3656 KB |
Output is correct |
36 |
Correct |
1573 ms |
5396 KB |
Output is correct |
37 |
Correct |
1527 ms |
5488 KB |
Output is correct |
38 |
Correct |
1404 ms |
5552 KB |
Output is correct |
39 |
Correct |
1029 ms |
5276 KB |
Output is correct |
40 |
Correct |
987 ms |
5560 KB |
Output is correct |
41 |
Correct |
900 ms |
5316 KB |
Output is correct |
42 |
Correct |
902 ms |
5520 KB |
Output is correct |
43 |
Correct |
1721 ms |
6600 KB |
Output is correct |
44 |
Correct |
206 ms |
3524 KB |
Output is correct |
45 |
Correct |
174 ms |
5004 KB |
Output is correct |
46 |
Correct |
146 ms |
4992 KB |
Output is correct |
47 |
Correct |
1636 ms |
6388 KB |
Output is correct |
48 |
Correct |
1715 ms |
6484 KB |
Output is correct |
49 |
Correct |
1677 ms |
6440 KB |
Output is correct |
50 |
Correct |
944 ms |
5080 KB |
Output is correct |
51 |
Correct |
960 ms |
5020 KB |
Output is correct |
52 |
Correct |
979 ms |
4864 KB |
Output is correct |
53 |
Correct |
1413 ms |
6404 KB |
Output is correct |
54 |
Correct |
1370 ms |
5996 KB |
Output is correct |
55 |
Correct |
1420 ms |
6028 KB |
Output is correct |
56 |
Correct |
1491 ms |
6468 KB |
Output is correct |
57 |
Correct |
1592 ms |
6568 KB |
Output is correct |
58 |
Correct |
1790 ms |
6508 KB |
Output is correct |
59 |
Correct |
1803 ms |
6512 KB |
Output is correct |
60 |
Correct |
1790 ms |
6364 KB |
Output is correct |
61 |
Correct |
1794 ms |
6308 KB |
Output is correct |
62 |
Correct |
1559 ms |
6252 KB |
Output is correct |
63 |
Correct |
1563 ms |
6188 KB |
Output is correct |
64 |
Correct |
1700 ms |
6372 KB |
Output is correct |
65 |
Correct |
1609 ms |
5992 KB |
Output is correct |
66 |
Correct |
1824 ms |
6288 KB |
Output is correct |
67 |
Correct |
1982 ms |
6208 KB |
Output is correct |
68 |
Correct |
1890 ms |
6144 KB |
Output is correct |
69 |
Correct |
1669 ms |
6096 KB |
Output is correct |
70 |
Correct |
2070 ms |
6048 KB |
Output is correct |
71 |
Correct |
2060 ms |
6028 KB |
Output is correct |
72 |
Correct |
2084 ms |
6112 KB |
Output is correct |
73 |
Correct |
1935 ms |
6212 KB |
Output is correct |
74 |
Correct |
1917 ms |
6072 KB |
Output is correct |
75 |
Correct |
1921 ms |
6012 KB |
Output is correct |
76 |
Correct |
1733 ms |
6160 KB |
Output is correct |
77 |
Correct |
1721 ms |
6184 KB |
Output is correct |
78 |
Correct |
1699 ms |
6344 KB |
Output is correct |
79 |
Correct |
1262 ms |
6120 KB |
Output is correct |
80 |
Correct |
1278 ms |
6152 KB |
Output is correct |
81 |
Correct |
1268 ms |
6212 KB |
Output is correct |
82 |
Correct |
1122 ms |
6064 KB |
Output is correct |
83 |
Correct |
1152 ms |
6152 KB |
Output is correct |
84 |
Correct |
1142 ms |
6180 KB |
Output is correct |
85 |
Correct |
2744 ms |
8096 KB |
Output is correct |
86 |
Correct |
262 ms |
7656 KB |
Output is correct |
87 |
Correct |
237 ms |
7776 KB |
Output is correct |
88 |
Correct |
2601 ms |
10344 KB |
Output is correct |
89 |
Correct |
2757 ms |
11932 KB |
Output is correct |
90 |
Correct |
2628 ms |
9928 KB |
Output is correct |
91 |
Correct |
1972 ms |
8924 KB |
Output is correct |
92 |
Correct |
2025 ms |
8792 KB |
Output is correct |
93 |
Correct |
2308 ms |
8620 KB |
Output is correct |
94 |
Correct |
2473 ms |
10436 KB |
Output is correct |
95 |
Correct |
2434 ms |
10576 KB |
Output is correct |
96 |
Correct |
2458 ms |
10356 KB |
Output is correct |
97 |
Correct |
2058 ms |
10008 KB |
Output is correct |
98 |
Correct |
1964 ms |
9852 KB |
Output is correct |
99 |
Correct |
2883 ms |
11860 KB |
Output is correct |
100 |
Correct |
2809 ms |
11744 KB |
Output is correct |
101 |
Correct |
2890 ms |
11768 KB |
Output is correct |
102 |
Correct |
2879 ms |
11964 KB |
Output is correct |
103 |
Correct |
2607 ms |
10612 KB |
Output is correct |
104 |
Correct |
2584 ms |
10644 KB |
Output is correct |
105 |
Correct |
1821 ms |
10772 KB |
Output is correct |
106 |
Correct |
1455 ms |
10524 KB |
Output is correct |
107 |
Correct |
1990 ms |
10580 KB |
Output is correct |
108 |
Correct |
2724 ms |
11244 KB |
Output is correct |
109 |
Correct |
2587 ms |
9236 KB |
Output is correct |