#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...);
}
#ifdef 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, bool need = false) {
if (p[x] < 0) return x;
return get(p[x], need);
}
bool unite(int x, int y, bool need = false) {
x = get(x, need); y = get(y, need);
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 = 1500;
vector<int> ans(q);
vector<int> to(m, -1);
/*
x/4 * q + q/x * qlog
q * (x/4 + q/x17) >= sqrtq sqrt17
*/
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[i] == -1) id.push_back(i);
sort(id.begin(), id.end(), [&](int i, int j) {
return edges[i].w > edges[j].w;
});
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]), 1)];
d.recall();
}
for (auto&x : now) {
edges[get<1>(Query[x])].w = get<2>(Query[x]);
}
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:150:6: warning: unused variable '_' [-Wunused-variable]
150 | int _, n, m;
| ^
bridges.cpp:147:36: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
147 | if (fopen(qwer".inp","r")) freopen(qwer".inp","r",stdin), freopen(qwer".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:147:67: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
147 | 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 |
40 ms |
592 KB |
Output is correct |
4 |
Correct |
5 ms |
588 KB |
Output is correct |
5 |
Correct |
22 ms |
588 KB |
Output is correct |
6 |
Correct |
21 ms |
588 KB |
Output is correct |
7 |
Correct |
24 ms |
652 KB |
Output is correct |
8 |
Correct |
25 ms |
588 KB |
Output is correct |
9 |
Correct |
28 ms |
588 KB |
Output is correct |
10 |
Correct |
26 ms |
588 KB |
Output is correct |
11 |
Correct |
25 ms |
588 KB |
Output is correct |
12 |
Correct |
26 ms |
588 KB |
Output is correct |
13 |
Correct |
30 ms |
588 KB |
Output is correct |
14 |
Correct |
29 ms |
588 KB |
Output is correct |
15 |
Correct |
26 ms |
588 KB |
Output is correct |
16 |
Correct |
26 ms |
588 KB |
Output is correct |
17 |
Correct |
26 ms |
620 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1518 ms |
3328 KB |
Output is correct |
2 |
Correct |
1527 ms |
3396 KB |
Output is correct |
3 |
Correct |
1535 ms |
3324 KB |
Output is correct |
4 |
Correct |
1567 ms |
3352 KB |
Output is correct |
5 |
Correct |
1574 ms |
3400 KB |
Output is correct |
6 |
Correct |
2238 ms |
3592 KB |
Output is correct |
7 |
Correct |
2252 ms |
3676 KB |
Output is correct |
8 |
Correct |
2255 ms |
3592 KB |
Output is correct |
9 |
Correct |
46 ms |
1992 KB |
Output is correct |
10 |
Correct |
1451 ms |
3472 KB |
Output is correct |
11 |
Correct |
1341 ms |
3452 KB |
Output is correct |
12 |
Correct |
1203 ms |
3720 KB |
Output is correct |
13 |
Correct |
1194 ms |
3332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1339 ms |
2892 KB |
Output is correct |
2 |
Correct |
1173 ms |
2276 KB |
Output is correct |
3 |
Correct |
1592 ms |
2908 KB |
Output is correct |
4 |
Correct |
1299 ms |
2912 KB |
Output is correct |
5 |
Correct |
44 ms |
1992 KB |
Output is correct |
6 |
Correct |
1484 ms |
3008 KB |
Output is correct |
7 |
Correct |
1221 ms |
2912 KB |
Output is correct |
8 |
Correct |
1072 ms |
2876 KB |
Output is correct |
9 |
Correct |
738 ms |
3048 KB |
Output is correct |
10 |
Correct |
656 ms |
2916 KB |
Output is correct |
11 |
Correct |
812 ms |
2788 KB |
Output is correct |
12 |
Correct |
689 ms |
2880 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1176 ms |
4932 KB |
Output is correct |
2 |
Correct |
50 ms |
1984 KB |
Output is correct |
3 |
Correct |
140 ms |
2960 KB |
Output is correct |
4 |
Correct |
76 ms |
2964 KB |
Output is correct |
5 |
Correct |
585 ms |
4952 KB |
Output is correct |
6 |
Correct |
1131 ms |
5044 KB |
Output is correct |
7 |
Correct |
586 ms |
4940 KB |
Output is correct |
8 |
Correct |
562 ms |
3444 KB |
Output is correct |
9 |
Correct |
538 ms |
3540 KB |
Output is correct |
10 |
Correct |
551 ms |
3704 KB |
Output is correct |
11 |
Correct |
896 ms |
4256 KB |
Output is correct |
12 |
Correct |
843 ms |
4320 KB |
Output is correct |
13 |
Correct |
869 ms |
4524 KB |
Output is correct |
14 |
Correct |
515 ms |
5048 KB |
Output is correct |
15 |
Correct |
593 ms |
5060 KB |
Output is correct |
16 |
Correct |
1169 ms |
4920 KB |
Output is correct |
17 |
Correct |
1153 ms |
4908 KB |
Output is correct |
18 |
Correct |
1161 ms |
4924 KB |
Output is correct |
19 |
Correct |
1164 ms |
5040 KB |
Output is correct |
20 |
Correct |
971 ms |
4736 KB |
Output is correct |
21 |
Correct |
983 ms |
4736 KB |
Output is correct |
22 |
Correct |
1115 ms |
5008 KB |
Output is correct |
23 |
Correct |
677 ms |
4652 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1518 ms |
3328 KB |
Output is correct |
2 |
Correct |
1527 ms |
3396 KB |
Output is correct |
3 |
Correct |
1535 ms |
3324 KB |
Output is correct |
4 |
Correct |
1567 ms |
3352 KB |
Output is correct |
5 |
Correct |
1574 ms |
3400 KB |
Output is correct |
6 |
Correct |
2238 ms |
3592 KB |
Output is correct |
7 |
Correct |
2252 ms |
3676 KB |
Output is correct |
8 |
Correct |
2255 ms |
3592 KB |
Output is correct |
9 |
Correct |
46 ms |
1992 KB |
Output is correct |
10 |
Correct |
1451 ms |
3472 KB |
Output is correct |
11 |
Correct |
1341 ms |
3452 KB |
Output is correct |
12 |
Correct |
1203 ms |
3720 KB |
Output is correct |
13 |
Correct |
1194 ms |
3332 KB |
Output is correct |
14 |
Correct |
1339 ms |
2892 KB |
Output is correct |
15 |
Correct |
1173 ms |
2276 KB |
Output is correct |
16 |
Correct |
1592 ms |
2908 KB |
Output is correct |
17 |
Correct |
1299 ms |
2912 KB |
Output is correct |
18 |
Correct |
44 ms |
1992 KB |
Output is correct |
19 |
Correct |
1484 ms |
3008 KB |
Output is correct |
20 |
Correct |
1221 ms |
2912 KB |
Output is correct |
21 |
Correct |
1072 ms |
2876 KB |
Output is correct |
22 |
Correct |
738 ms |
3048 KB |
Output is correct |
23 |
Correct |
656 ms |
2916 KB |
Output is correct |
24 |
Correct |
812 ms |
2788 KB |
Output is correct |
25 |
Correct |
689 ms |
2880 KB |
Output is correct |
26 |
Correct |
1612 ms |
3444 KB |
Output is correct |
27 |
Correct |
1978 ms |
3544 KB |
Output is correct |
28 |
Correct |
1629 ms |
3528 KB |
Output is correct |
29 |
Correct |
1089 ms |
3400 KB |
Output is correct |
30 |
Correct |
1808 ms |
3536 KB |
Output is correct |
31 |
Correct |
1893 ms |
3532 KB |
Output is correct |
32 |
Correct |
1905 ms |
3532 KB |
Output is correct |
33 |
Correct |
1581 ms |
3404 KB |
Output is correct |
34 |
Correct |
1576 ms |
3520 KB |
Output is correct |
35 |
Correct |
1564 ms |
3516 KB |
Output is correct |
36 |
Correct |
1189 ms |
3408 KB |
Output is correct |
37 |
Correct |
1137 ms |
3392 KB |
Output is correct |
38 |
Correct |
1133 ms |
3532 KB |
Output is correct |
39 |
Correct |
771 ms |
3512 KB |
Output is correct |
40 |
Correct |
776 ms |
3572 KB |
Output is correct |
41 |
Correct |
761 ms |
3644 KB |
Output is correct |
42 |
Correct |
778 ms |
3408 KB |
Output is correct |
43 |
Correct |
774 ms |
3536 KB |
Output is correct |
44 |
Correct |
756 ms |
3532 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 |
40 ms |
592 KB |
Output is correct |
4 |
Correct |
5 ms |
588 KB |
Output is correct |
5 |
Correct |
22 ms |
588 KB |
Output is correct |
6 |
Correct |
21 ms |
588 KB |
Output is correct |
7 |
Correct |
24 ms |
652 KB |
Output is correct |
8 |
Correct |
25 ms |
588 KB |
Output is correct |
9 |
Correct |
28 ms |
588 KB |
Output is correct |
10 |
Correct |
26 ms |
588 KB |
Output is correct |
11 |
Correct |
25 ms |
588 KB |
Output is correct |
12 |
Correct |
26 ms |
588 KB |
Output is correct |
13 |
Correct |
30 ms |
588 KB |
Output is correct |
14 |
Correct |
29 ms |
588 KB |
Output is correct |
15 |
Correct |
26 ms |
588 KB |
Output is correct |
16 |
Correct |
26 ms |
588 KB |
Output is correct |
17 |
Correct |
26 ms |
620 KB |
Output is correct |
18 |
Correct |
1518 ms |
3328 KB |
Output is correct |
19 |
Correct |
1527 ms |
3396 KB |
Output is correct |
20 |
Correct |
1535 ms |
3324 KB |
Output is correct |
21 |
Correct |
1567 ms |
3352 KB |
Output is correct |
22 |
Correct |
1574 ms |
3400 KB |
Output is correct |
23 |
Correct |
2238 ms |
3592 KB |
Output is correct |
24 |
Correct |
2252 ms |
3676 KB |
Output is correct |
25 |
Correct |
2255 ms |
3592 KB |
Output is correct |
26 |
Correct |
46 ms |
1992 KB |
Output is correct |
27 |
Correct |
1451 ms |
3472 KB |
Output is correct |
28 |
Correct |
1341 ms |
3452 KB |
Output is correct |
29 |
Correct |
1203 ms |
3720 KB |
Output is correct |
30 |
Correct |
1194 ms |
3332 KB |
Output is correct |
31 |
Correct |
1339 ms |
2892 KB |
Output is correct |
32 |
Correct |
1173 ms |
2276 KB |
Output is correct |
33 |
Correct |
1592 ms |
2908 KB |
Output is correct |
34 |
Correct |
1299 ms |
2912 KB |
Output is correct |
35 |
Correct |
44 ms |
1992 KB |
Output is correct |
36 |
Correct |
1484 ms |
3008 KB |
Output is correct |
37 |
Correct |
1221 ms |
2912 KB |
Output is correct |
38 |
Correct |
1072 ms |
2876 KB |
Output is correct |
39 |
Correct |
738 ms |
3048 KB |
Output is correct |
40 |
Correct |
656 ms |
2916 KB |
Output is correct |
41 |
Correct |
812 ms |
2788 KB |
Output is correct |
42 |
Correct |
689 ms |
2880 KB |
Output is correct |
43 |
Correct |
1176 ms |
4932 KB |
Output is correct |
44 |
Correct |
50 ms |
1984 KB |
Output is correct |
45 |
Correct |
140 ms |
2960 KB |
Output is correct |
46 |
Correct |
76 ms |
2964 KB |
Output is correct |
47 |
Correct |
585 ms |
4952 KB |
Output is correct |
48 |
Correct |
1131 ms |
5044 KB |
Output is correct |
49 |
Correct |
586 ms |
4940 KB |
Output is correct |
50 |
Correct |
562 ms |
3444 KB |
Output is correct |
51 |
Correct |
538 ms |
3540 KB |
Output is correct |
52 |
Correct |
551 ms |
3704 KB |
Output is correct |
53 |
Correct |
896 ms |
4256 KB |
Output is correct |
54 |
Correct |
843 ms |
4320 KB |
Output is correct |
55 |
Correct |
869 ms |
4524 KB |
Output is correct |
56 |
Correct |
515 ms |
5048 KB |
Output is correct |
57 |
Correct |
593 ms |
5060 KB |
Output is correct |
58 |
Correct |
1169 ms |
4920 KB |
Output is correct |
59 |
Correct |
1153 ms |
4908 KB |
Output is correct |
60 |
Correct |
1161 ms |
4924 KB |
Output is correct |
61 |
Correct |
1164 ms |
5040 KB |
Output is correct |
62 |
Correct |
971 ms |
4736 KB |
Output is correct |
63 |
Correct |
983 ms |
4736 KB |
Output is correct |
64 |
Correct |
1115 ms |
5008 KB |
Output is correct |
65 |
Correct |
677 ms |
4652 KB |
Output is correct |
66 |
Correct |
1612 ms |
3444 KB |
Output is correct |
67 |
Correct |
1978 ms |
3544 KB |
Output is correct |
68 |
Correct |
1629 ms |
3528 KB |
Output is correct |
69 |
Correct |
1089 ms |
3400 KB |
Output is correct |
70 |
Correct |
1808 ms |
3536 KB |
Output is correct |
71 |
Correct |
1893 ms |
3532 KB |
Output is correct |
72 |
Correct |
1905 ms |
3532 KB |
Output is correct |
73 |
Correct |
1581 ms |
3404 KB |
Output is correct |
74 |
Correct |
1576 ms |
3520 KB |
Output is correct |
75 |
Correct |
1564 ms |
3516 KB |
Output is correct |
76 |
Correct |
1189 ms |
3408 KB |
Output is correct |
77 |
Correct |
1137 ms |
3392 KB |
Output is correct |
78 |
Correct |
1133 ms |
3532 KB |
Output is correct |
79 |
Correct |
771 ms |
3512 KB |
Output is correct |
80 |
Correct |
776 ms |
3572 KB |
Output is correct |
81 |
Correct |
761 ms |
3644 KB |
Output is correct |
82 |
Correct |
778 ms |
3408 KB |
Output is correct |
83 |
Correct |
774 ms |
3536 KB |
Output is correct |
84 |
Correct |
756 ms |
3532 KB |
Output is correct |
85 |
Correct |
1887 ms |
4764 KB |
Output is correct |
86 |
Correct |
188 ms |
2992 KB |
Output is correct |
87 |
Correct |
125 ms |
2992 KB |
Output is correct |
88 |
Correct |
1236 ms |
4736 KB |
Output is correct |
89 |
Correct |
1864 ms |
4796 KB |
Output is correct |
90 |
Correct |
1233 ms |
4856 KB |
Output is correct |
91 |
Correct |
1642 ms |
3364 KB |
Output is correct |
92 |
Correct |
1608 ms |
3368 KB |
Output is correct |
93 |
Correct |
2398 ms |
3512 KB |
Output is correct |
94 |
Correct |
1707 ms |
4236 KB |
Output is correct |
95 |
Correct |
1727 ms |
4240 KB |
Output is correct |
96 |
Correct |
1738 ms |
4240 KB |
Output is correct |
97 |
Correct |
819 ms |
5004 KB |
Output is correct |
98 |
Correct |
913 ms |
4608 KB |
Output is correct |
99 |
Correct |
1911 ms |
4708 KB |
Output is correct |
100 |
Correct |
1903 ms |
4700 KB |
Output is correct |
101 |
Correct |
1938 ms |
4716 KB |
Output is correct |
102 |
Correct |
1935 ms |
4712 KB |
Output is correct |
103 |
Correct |
1809 ms |
4536 KB |
Output is correct |
104 |
Correct |
1809 ms |
4528 KB |
Output is correct |
105 |
Correct |
1335 ms |
4280 KB |
Output is correct |
106 |
Correct |
1084 ms |
4116 KB |
Output is correct |
107 |
Correct |
1255 ms |
4668 KB |
Output is correct |
108 |
Correct |
1783 ms |
4760 KB |
Output is correct |
109 |
Correct |
1312 ms |
4400 KB |
Output is correct |