#include<bits/stdc++.h>
using namespace std;
template <typename A, typename B>
string to_string(pair<A, B> p);
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);
string to_string(const string& s) {
return '"' + s + '"';
}
string to_string(const char* s) {
return to_string((string) s);
}
string to_string(bool b) {
return (b ? "true" : "false");
}
string to_string(vector<bool> v) {
bool first = true;
string res = "{";
for (int i = 0; i < static_cast<int>(v.size()); i++) {
if (!first) {
res += ", ";
}
first = false;
res += to_string(v[i]);
}
res += "}";
return res;
}
template <size_t N>
string to_string(bitset<N> v) {
string res = "";
for (size_t i = 0; i < N; i++) {
res += static_cast<char>('0' + v[i]);
}
return res;
}
template <typename A>
string to_string(A v) {
bool first = true;
string res = "{";
for (const auto &x : v) {
if (!first) {
res += ", ";
}
first = false;
res += to_string(x);
}
res += "}";
return res;
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
cerr << " " << to_string(H);
debug_out(T...);
}
#ifndef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
struct dsu {
struct node {
int* p;
int val;
int time;
};
vector<node> event = {{NULL, 0, -1}};
vector<int> p;
int n;
dsu(int n) {
resize(n);
}
dsu() {
}
void resize(int _n) {
n = _n;
p = vector<int> (n, -1);
}
int count = 0;
int get(int x) {
return p[x] < 0 ? x : get(p[x]);
}
bool unite(int x, int y, bool need = false) {
x = get(x); y = get(y);
if (x != y) {
if (p[x] < p[y]) swap(x, y);
if (need) {
event.push_back({&p[x], p[x], count});
event.push_back({&p[y], p[y], count});
}
p[y] += p[x];
p[x] = y;
return true;
}
return false;
}
void recall() {
while (event.back().time == count) {
*event.back().p = event.back().val;
event.pop_back();
}
--count;
}
};
struct edge {
int u;
int v;
int w;
};
int main() {
#define qwer "test"
if (fopen(qwer".inp","r")) freopen(qwer".inp","r",stdin), freopen(qwer".out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
int _, n, m;
//cin >> _;
cin >> n >> m;
vector<edge> edges;
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
--u; --v;
edges.push_back({u, v, w});
}
int q;
cin >> q;
vector<tuple<int, int, int>> Query;
for (int i = 0; i < q; i++) {
int t, u, w;
cin >> t >> u >> w;
--u;
Query.emplace_back(t, u, w);
}
int sq = 2 * sqrt(q);
vector<int> ans(q);
vector<int> to(m, -1);
/*
x/4 * q + q/x * q
q * (x/4 + q/x) >= sqrtq sqrt17
*/
vector<int> p(m);
iota(p.begin(), p.end(), 0);
sort(p.begin(), p.end(), [&](int i, int j) {
return edges[i].w > edges[j].w;
});
for (int l = 0; l < q; l += sq) {
int r = min(q, l + sq);
dsu d(n);
vector<int> ask;
vector<int> rem;
vector<int> now;
for (int i = l; i < r; i++) {
if (get<0>(Query[i]) == 1) {
if (to[get<1>(Query[i])] == -1) {
rem.push_back(get<1>(Query[i]));
to[rem.back()] = edges[rem.back()].w;
}
now.push_back(i);
}
else {
ask.push_back(i);
}
}
vector<int> id;
for (int i = 0; i < m; i++) if (to[p[i]] == -1) id.push_back(p[i]);
sort(ask.begin(), ask.end(), [&](int i, int j) {
return get<2>(Query[i]) > get<2>(Query[j]);
});
int j = 0;
for (auto& i : ask) {
while (j < (int) id.size() && edges[id[j]].w >= get<2>(Query[i])) {
d.unite(edges[id[j]].u, edges[id[j]].v);
j++;
}
for (auto&x : now) {
if (x > i) break;
to[get<1>(Query[x])] = get<2>(Query[x]);
}
d.count++;
for (auto&x : rem) {
if (to[x] >= get<2>(Query[i])) {
d.unite(edges[x].u, edges[x].v, 1);
}
to[x] = edges[x].w;
}
ans[i] = -d.p[d.get(get<1>(Query[i]))];
d.recall();
}
for (auto&x : now) {
edges[get<1>(Query[x])].w = get<2>(Query[x]);
}
sort(rem.begin(), rem.end(), [&](int i, int j) {
return edges[i].w > edges[j].w;
});
merge(id.begin(), id.end(), rem.begin(), rem.end(), p.begin(), [&](int i, int j) {
return edges[i].w > edges[j].w;
});
for (auto&x : rem) {
to[x] = -1;
}
}
for (int i = 0; i < q; i++) if (get<0>(Query[i]) == 2) cout << ans[i] << "\n";
}
Compilation message
bridges.cpp: In function 'int main()':
bridges.cpp:149:6: warning: unused variable '_' [-Wunused-variable]
149 | int _, n, m;
| ^
bridges.cpp:146:36: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
146 | if (fopen(qwer".inp","r")) freopen(qwer".inp","r",stdin), freopen(qwer".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:146:67: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
146 | if (fopen(qwer".inp","r")) freopen(qwer".inp","r",stdin), freopen(qwer".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
14 ms |
764 KB |
Output is correct |
4 |
Correct |
5 ms |
716 KB |
Output is correct |
5 |
Correct |
11 ms |
716 KB |
Output is correct |
6 |
Correct |
9 ms |
712 KB |
Output is correct |
7 |
Correct |
14 ms |
656 KB |
Output is correct |
8 |
Correct |
12 ms |
728 KB |
Output is correct |
9 |
Correct |
14 ms |
652 KB |
Output is correct |
10 |
Correct |
13 ms |
716 KB |
Output is correct |
11 |
Correct |
13 ms |
728 KB |
Output is correct |
12 |
Correct |
14 ms |
716 KB |
Output is correct |
13 |
Correct |
14 ms |
732 KB |
Output is correct |
14 |
Correct |
14 ms |
732 KB |
Output is correct |
15 |
Correct |
14 ms |
728 KB |
Output is correct |
16 |
Correct |
13 ms |
652 KB |
Output is correct |
17 |
Correct |
12 ms |
648 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
877 ms |
6404 KB |
Output is correct |
2 |
Correct |
827 ms |
6248 KB |
Output is correct |
3 |
Correct |
832 ms |
6308 KB |
Output is correct |
4 |
Correct |
854 ms |
6332 KB |
Output is correct |
5 |
Correct |
901 ms |
6300 KB |
Output is correct |
6 |
Correct |
1172 ms |
6320 KB |
Output is correct |
7 |
Correct |
1182 ms |
6448 KB |
Output is correct |
8 |
Correct |
1216 ms |
6360 KB |
Output is correct |
9 |
Correct |
45 ms |
3392 KB |
Output is correct |
10 |
Correct |
864 ms |
5272 KB |
Output is correct |
11 |
Correct |
810 ms |
5400 KB |
Output is correct |
12 |
Correct |
668 ms |
6352 KB |
Output is correct |
13 |
Correct |
653 ms |
6224 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
692 ms |
5312 KB |
Output is correct |
2 |
Correct |
565 ms |
3816 KB |
Output is correct |
3 |
Correct |
813 ms |
5148 KB |
Output is correct |
4 |
Correct |
685 ms |
5428 KB |
Output is correct |
5 |
Correct |
43 ms |
3336 KB |
Output is correct |
6 |
Correct |
767 ms |
5304 KB |
Output is correct |
7 |
Correct |
631 ms |
5452 KB |
Output is correct |
8 |
Correct |
581 ms |
5216 KB |
Output is correct |
9 |
Correct |
427 ms |
5440 KB |
Output is correct |
10 |
Correct |
387 ms |
5328 KB |
Output is correct |
11 |
Correct |
455 ms |
5300 KB |
Output is correct |
12 |
Correct |
409 ms |
5184 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
827 ms |
9144 KB |
Output is correct |
2 |
Correct |
45 ms |
3384 KB |
Output is correct |
3 |
Correct |
209 ms |
5160 KB |
Output is correct |
4 |
Correct |
190 ms |
5316 KB |
Output is correct |
5 |
Correct |
669 ms |
7624 KB |
Output is correct |
6 |
Correct |
808 ms |
9152 KB |
Output is correct |
7 |
Correct |
670 ms |
7600 KB |
Output is correct |
8 |
Correct |
358 ms |
6312 KB |
Output is correct |
9 |
Correct |
357 ms |
6464 KB |
Output is correct |
10 |
Correct |
367 ms |
6288 KB |
Output is correct |
11 |
Correct |
625 ms |
7776 KB |
Output is correct |
12 |
Correct |
622 ms |
8048 KB |
Output is correct |
13 |
Correct |
683 ms |
7788 KB |
Output is correct |
14 |
Correct |
684 ms |
7832 KB |
Output is correct |
15 |
Correct |
702 ms |
7736 KB |
Output is correct |
16 |
Correct |
854 ms |
9052 KB |
Output is correct |
17 |
Correct |
857 ms |
9012 KB |
Output is correct |
18 |
Correct |
858 ms |
9148 KB |
Output is correct |
19 |
Correct |
831 ms |
9132 KB |
Output is correct |
20 |
Correct |
720 ms |
8220 KB |
Output is correct |
21 |
Correct |
743 ms |
8204 KB |
Output is correct |
22 |
Correct |
826 ms |
8900 KB |
Output is correct |
23 |
Correct |
650 ms |
7088 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
877 ms |
6404 KB |
Output is correct |
2 |
Correct |
827 ms |
6248 KB |
Output is correct |
3 |
Correct |
832 ms |
6308 KB |
Output is correct |
4 |
Correct |
854 ms |
6332 KB |
Output is correct |
5 |
Correct |
901 ms |
6300 KB |
Output is correct |
6 |
Correct |
1172 ms |
6320 KB |
Output is correct |
7 |
Correct |
1182 ms |
6448 KB |
Output is correct |
8 |
Correct |
1216 ms |
6360 KB |
Output is correct |
9 |
Correct |
45 ms |
3392 KB |
Output is correct |
10 |
Correct |
864 ms |
5272 KB |
Output is correct |
11 |
Correct |
810 ms |
5400 KB |
Output is correct |
12 |
Correct |
668 ms |
6352 KB |
Output is correct |
13 |
Correct |
653 ms |
6224 KB |
Output is correct |
14 |
Correct |
692 ms |
5312 KB |
Output is correct |
15 |
Correct |
565 ms |
3816 KB |
Output is correct |
16 |
Correct |
813 ms |
5148 KB |
Output is correct |
17 |
Correct |
685 ms |
5428 KB |
Output is correct |
18 |
Correct |
43 ms |
3336 KB |
Output is correct |
19 |
Correct |
767 ms |
5304 KB |
Output is correct |
20 |
Correct |
631 ms |
5452 KB |
Output is correct |
21 |
Correct |
581 ms |
5216 KB |
Output is correct |
22 |
Correct |
427 ms |
5440 KB |
Output is correct |
23 |
Correct |
387 ms |
5328 KB |
Output is correct |
24 |
Correct |
455 ms |
5300 KB |
Output is correct |
25 |
Correct |
409 ms |
5184 KB |
Output is correct |
26 |
Correct |
910 ms |
6396 KB |
Output is correct |
27 |
Correct |
1103 ms |
6196 KB |
Output is correct |
28 |
Correct |
887 ms |
6432 KB |
Output is correct |
29 |
Correct |
730 ms |
6336 KB |
Output is correct |
30 |
Correct |
986 ms |
6300 KB |
Output is correct |
31 |
Correct |
992 ms |
6232 KB |
Output is correct |
32 |
Correct |
1010 ms |
6228 KB |
Output is correct |
33 |
Correct |
846 ms |
6304 KB |
Output is correct |
34 |
Correct |
850 ms |
6328 KB |
Output is correct |
35 |
Correct |
871 ms |
6320 KB |
Output is correct |
36 |
Correct |
692 ms |
6244 KB |
Output is correct |
37 |
Correct |
724 ms |
6224 KB |
Output is correct |
38 |
Correct |
703 ms |
6232 KB |
Output is correct |
39 |
Correct |
493 ms |
6420 KB |
Output is correct |
40 |
Correct |
498 ms |
6336 KB |
Output is correct |
41 |
Correct |
493 ms |
6380 KB |
Output is correct |
42 |
Correct |
490 ms |
6224 KB |
Output is correct |
43 |
Correct |
493 ms |
6160 KB |
Output is correct |
44 |
Correct |
476 ms |
6224 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
14 ms |
764 KB |
Output is correct |
4 |
Correct |
5 ms |
716 KB |
Output is correct |
5 |
Correct |
11 ms |
716 KB |
Output is correct |
6 |
Correct |
9 ms |
712 KB |
Output is correct |
7 |
Correct |
14 ms |
656 KB |
Output is correct |
8 |
Correct |
12 ms |
728 KB |
Output is correct |
9 |
Correct |
14 ms |
652 KB |
Output is correct |
10 |
Correct |
13 ms |
716 KB |
Output is correct |
11 |
Correct |
13 ms |
728 KB |
Output is correct |
12 |
Correct |
14 ms |
716 KB |
Output is correct |
13 |
Correct |
14 ms |
732 KB |
Output is correct |
14 |
Correct |
14 ms |
732 KB |
Output is correct |
15 |
Correct |
14 ms |
728 KB |
Output is correct |
16 |
Correct |
13 ms |
652 KB |
Output is correct |
17 |
Correct |
12 ms |
648 KB |
Output is correct |
18 |
Correct |
877 ms |
6404 KB |
Output is correct |
19 |
Correct |
827 ms |
6248 KB |
Output is correct |
20 |
Correct |
832 ms |
6308 KB |
Output is correct |
21 |
Correct |
854 ms |
6332 KB |
Output is correct |
22 |
Correct |
901 ms |
6300 KB |
Output is correct |
23 |
Correct |
1172 ms |
6320 KB |
Output is correct |
24 |
Correct |
1182 ms |
6448 KB |
Output is correct |
25 |
Correct |
1216 ms |
6360 KB |
Output is correct |
26 |
Correct |
45 ms |
3392 KB |
Output is correct |
27 |
Correct |
864 ms |
5272 KB |
Output is correct |
28 |
Correct |
810 ms |
5400 KB |
Output is correct |
29 |
Correct |
668 ms |
6352 KB |
Output is correct |
30 |
Correct |
653 ms |
6224 KB |
Output is correct |
31 |
Correct |
692 ms |
5312 KB |
Output is correct |
32 |
Correct |
565 ms |
3816 KB |
Output is correct |
33 |
Correct |
813 ms |
5148 KB |
Output is correct |
34 |
Correct |
685 ms |
5428 KB |
Output is correct |
35 |
Correct |
43 ms |
3336 KB |
Output is correct |
36 |
Correct |
767 ms |
5304 KB |
Output is correct |
37 |
Correct |
631 ms |
5452 KB |
Output is correct |
38 |
Correct |
581 ms |
5216 KB |
Output is correct |
39 |
Correct |
427 ms |
5440 KB |
Output is correct |
40 |
Correct |
387 ms |
5328 KB |
Output is correct |
41 |
Correct |
455 ms |
5300 KB |
Output is correct |
42 |
Correct |
409 ms |
5184 KB |
Output is correct |
43 |
Correct |
827 ms |
9144 KB |
Output is correct |
44 |
Correct |
45 ms |
3384 KB |
Output is correct |
45 |
Correct |
209 ms |
5160 KB |
Output is correct |
46 |
Correct |
190 ms |
5316 KB |
Output is correct |
47 |
Correct |
669 ms |
7624 KB |
Output is correct |
48 |
Correct |
808 ms |
9152 KB |
Output is correct |
49 |
Correct |
670 ms |
7600 KB |
Output is correct |
50 |
Correct |
358 ms |
6312 KB |
Output is correct |
51 |
Correct |
357 ms |
6464 KB |
Output is correct |
52 |
Correct |
367 ms |
6288 KB |
Output is correct |
53 |
Correct |
625 ms |
7776 KB |
Output is correct |
54 |
Correct |
622 ms |
8048 KB |
Output is correct |
55 |
Correct |
683 ms |
7788 KB |
Output is correct |
56 |
Correct |
684 ms |
7832 KB |
Output is correct |
57 |
Correct |
702 ms |
7736 KB |
Output is correct |
58 |
Correct |
854 ms |
9052 KB |
Output is correct |
59 |
Correct |
857 ms |
9012 KB |
Output is correct |
60 |
Correct |
858 ms |
9148 KB |
Output is correct |
61 |
Correct |
831 ms |
9132 KB |
Output is correct |
62 |
Correct |
720 ms |
8220 KB |
Output is correct |
63 |
Correct |
743 ms |
8204 KB |
Output is correct |
64 |
Correct |
826 ms |
8900 KB |
Output is correct |
65 |
Correct |
650 ms |
7088 KB |
Output is correct |
66 |
Correct |
910 ms |
6396 KB |
Output is correct |
67 |
Correct |
1103 ms |
6196 KB |
Output is correct |
68 |
Correct |
887 ms |
6432 KB |
Output is correct |
69 |
Correct |
730 ms |
6336 KB |
Output is correct |
70 |
Correct |
986 ms |
6300 KB |
Output is correct |
71 |
Correct |
992 ms |
6232 KB |
Output is correct |
72 |
Correct |
1010 ms |
6228 KB |
Output is correct |
73 |
Correct |
846 ms |
6304 KB |
Output is correct |
74 |
Correct |
850 ms |
6328 KB |
Output is correct |
75 |
Correct |
871 ms |
6320 KB |
Output is correct |
76 |
Correct |
692 ms |
6244 KB |
Output is correct |
77 |
Correct |
724 ms |
6224 KB |
Output is correct |
78 |
Correct |
703 ms |
6232 KB |
Output is correct |
79 |
Correct |
493 ms |
6420 KB |
Output is correct |
80 |
Correct |
498 ms |
6336 KB |
Output is correct |
81 |
Correct |
493 ms |
6380 KB |
Output is correct |
82 |
Correct |
490 ms |
6224 KB |
Output is correct |
83 |
Correct |
493 ms |
6160 KB |
Output is correct |
84 |
Correct |
476 ms |
6224 KB |
Output is correct |
85 |
Correct |
1247 ms |
8912 KB |
Output is correct |
86 |
Correct |
240 ms |
5180 KB |
Output is correct |
87 |
Correct |
206 ms |
5372 KB |
Output is correct |
88 |
Correct |
1124 ms |
7492 KB |
Output is correct |
89 |
Correct |
1245 ms |
8900 KB |
Output is correct |
90 |
Correct |
1078 ms |
7480 KB |
Output is correct |
91 |
Correct |
893 ms |
6212 KB |
Output is correct |
92 |
Correct |
869 ms |
6336 KB |
Output is correct |
93 |
Correct |
1212 ms |
6248 KB |
Output is correct |
94 |
Correct |
1118 ms |
7572 KB |
Output is correct |
95 |
Correct |
1090 ms |
7844 KB |
Output is correct |
96 |
Correct |
1231 ms |
7624 KB |
Output is correct |
97 |
Correct |
855 ms |
7608 KB |
Output is correct |
98 |
Correct |
929 ms |
7228 KB |
Output is correct |
99 |
Correct |
1334 ms |
8864 KB |
Output is correct |
100 |
Correct |
1290 ms |
8884 KB |
Output is correct |
101 |
Correct |
1321 ms |
8904 KB |
Output is correct |
102 |
Correct |
1298 ms |
8900 KB |
Output is correct |
103 |
Correct |
1372 ms |
8072 KB |
Output is correct |
104 |
Correct |
1344 ms |
8068 KB |
Output is correct |
105 |
Correct |
994 ms |
7888 KB |
Output is correct |
106 |
Correct |
786 ms |
7572 KB |
Output is correct |
107 |
Correct |
941 ms |
8152 KB |
Output is correct |
108 |
Correct |
1253 ms |
8688 KB |
Output is correct |
109 |
Correct |
1137 ms |
6868 KB |
Output is correct |