#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
auto&operator<<(auto &o, pair<auto, auto> p) {o << "(" << p.first << ", " << p.second << ")"; return o;}
auto operator<<(auto &o, auto x)->decltype(x.end(), o) {o<<"{"; for(auto e : x) o<<e<<", "; return o<<"}";}
#define debug(X) cerr << "["#X"]: " << X << '\n';
#else
#define cerr if(0)cout
#define debug(X) ;
#endif
#define ll long long
#define all(v) (v).begin(), (v).end()
#define ssize(x) int(x.size())
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back
struct dynamicUF {
vector<int> e;
dynamicUF(int n): e(n, -1) {}
stack<array<int, 3>> s;
inline int get(int a) {
while(e[a] >= 0) a = e[a];
return a;
}
int unionn(int a, int b) {
a = get(a); b = get(b);
if(a == b) return 0;
if(-e[a] > -e[b]) swap(a, b);
// cerr << "ADD " << a << ' ' << b << '\n';
s.push({a, b, e[a]});
e[b] += e[a];
e[a] = b;
return 1;
}
void roll_back(int m = 1) {
while (m--) {
auto [a, b, sz] = s.top();
s.pop();
// cerr << "UNDO " << a << ' ' << b << '\n';
e[b] -= sz;
e[a] = sz;
}
}
};
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<int> w(m), u(m), v(m);
for(int i = 0; i < m; ++i) {
cin >> u[i] >> v[i] >> w[i];
u[i]--; v[i]--;
}
int q;
cin >> q;
vector<int> ans(q, -1);
const int B = 600;
// const int B = 1;
vector<array<int, 4>> ev;
vector<bool> changed(m);
vector<array<int, 3>> upd;
auto clean = [&] {
dynamicUF sp(n);
for(int i = 0; i < m; ++i) {
if(!changed[i]) {ev.eb((array<int, 4>){w[i], u[i], v[i], 0});}
else changed[i] = false;
}
sort(all(ev), [&](array<int, 4> x, array<int, 4> y) {
if (x[0] != y[0]) return x[0] > y[0];
return x[3] < y[3];
});
vector<int> M(m, -1);
for(auto [d, a, b, c] : ev) {
if(c == 0) {
sp.unionn(a, b);
}
else {
vector<int> to_add;
for(auto [idx, r, t] : upd) {
if(M[idx] == -1) to_add.eb(idx);
if(t <= b) {
M[idx] = r;
}
else if(M[idx] == -1) M[idx] = w[idx];
}
int cnt = 0;
for(auto idx : to_add) {
int r = M[idx];
if(r >= d) cnt += sp.unionn(u[idx], v[idx]);
M[idx] = -1;
}
ans[b] = -sp.e[sp.get(a)];
sp.roll_back(cnt);
}
}
for(auto [idx, r, t] : upd) {
w[idx] = r;
}
upd.clear();
ev.clear();
};
for(int t = 0; t < q; ++t) {
int c;
cin >> c;
if(c == 1) {
int b, r;
cin >> b >> r;
b--;
changed[b] = true;
upd.eb((array<int, 3>){b, r, t});
}
else {
int d, s;
cin >> s >> d;
s--;
ev.eb((array<int, 4>){d, s, t, 1});
}
if(t%B == B-1) {
clean();
}
}
clean();
for(int i = 0; i < q; i++) if(ans[i] > -1) cout << ans[i] << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
17 ms |
916 KB |
Output is correct |
4 |
Correct |
3 ms |
604 KB |
Output is correct |
5 |
Correct |
9 ms |
632 KB |
Output is correct |
6 |
Correct |
8 ms |
600 KB |
Output is correct |
7 |
Correct |
9 ms |
604 KB |
Output is correct |
8 |
Correct |
10 ms |
636 KB |
Output is correct |
9 |
Correct |
10 ms |
604 KB |
Output is correct |
10 |
Correct |
10 ms |
600 KB |
Output is correct |
11 |
Correct |
10 ms |
672 KB |
Output is correct |
12 |
Correct |
13 ms |
600 KB |
Output is correct |
13 |
Correct |
13 ms |
600 KB |
Output is correct |
14 |
Correct |
16 ms |
628 KB |
Output is correct |
15 |
Correct |
11 ms |
636 KB |
Output is correct |
16 |
Correct |
10 ms |
604 KB |
Output is correct |
17 |
Correct |
10 ms |
468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1094 ms |
5088 KB |
Output is correct |
2 |
Correct |
1104 ms |
5076 KB |
Output is correct |
3 |
Correct |
1097 ms |
5184 KB |
Output is correct |
4 |
Correct |
1123 ms |
5072 KB |
Output is correct |
5 |
Correct |
1118 ms |
5644 KB |
Output is correct |
6 |
Correct |
1224 ms |
5116 KB |
Output is correct |
7 |
Correct |
1209 ms |
5056 KB |
Output is correct |
8 |
Correct |
1228 ms |
5164 KB |
Output is correct |
9 |
Correct |
25 ms |
1876 KB |
Output is correct |
10 |
Correct |
753 ms |
4280 KB |
Output is correct |
11 |
Correct |
763 ms |
4368 KB |
Output is correct |
12 |
Correct |
990 ms |
5360 KB |
Output is correct |
13 |
Correct |
992 ms |
5056 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
807 ms |
4080 KB |
Output is correct |
2 |
Correct |
390 ms |
2372 KB |
Output is correct |
3 |
Correct |
825 ms |
3920 KB |
Output is correct |
4 |
Correct |
806 ms |
4020 KB |
Output is correct |
5 |
Correct |
25 ms |
2004 KB |
Output is correct |
6 |
Correct |
828 ms |
3728 KB |
Output is correct |
7 |
Correct |
765 ms |
3776 KB |
Output is correct |
8 |
Correct |
743 ms |
3628 KB |
Output is correct |
9 |
Correct |
646 ms |
3920 KB |
Output is correct |
10 |
Correct |
640 ms |
3908 KB |
Output is correct |
11 |
Correct |
660 ms |
3920 KB |
Output is correct |
12 |
Correct |
627 ms |
3752 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1874 ms |
7624 KB |
Output is correct |
2 |
Correct |
25 ms |
1880 KB |
Output is correct |
3 |
Correct |
204 ms |
5072 KB |
Output is correct |
4 |
Correct |
118 ms |
5032 KB |
Output is correct |
5 |
Correct |
1280 ms |
6332 KB |
Output is correct |
6 |
Correct |
1842 ms |
7704 KB |
Output is correct |
7 |
Correct |
1290 ms |
6660 KB |
Output is correct |
8 |
Correct |
877 ms |
5268 KB |
Output is correct |
9 |
Correct |
878 ms |
4984 KB |
Output is correct |
10 |
Correct |
874 ms |
5232 KB |
Output is correct |
11 |
Correct |
1398 ms |
6284 KB |
Output is correct |
12 |
Correct |
1384 ms |
6272 KB |
Output is correct |
13 |
Correct |
1389 ms |
6308 KB |
Output is correct |
14 |
Correct |
1140 ms |
6940 KB |
Output is correct |
15 |
Correct |
1225 ms |
6584 KB |
Output is correct |
16 |
Correct |
1892 ms |
7432 KB |
Output is correct |
17 |
Correct |
1881 ms |
7428 KB |
Output is correct |
18 |
Correct |
1890 ms |
7460 KB |
Output is correct |
19 |
Correct |
1879 ms |
7428 KB |
Output is correct |
20 |
Correct |
1589 ms |
6904 KB |
Output is correct |
21 |
Correct |
1595 ms |
6836 KB |
Output is correct |
22 |
Correct |
1808 ms |
7020 KB |
Output is correct |
23 |
Correct |
1265 ms |
6132 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1094 ms |
5088 KB |
Output is correct |
2 |
Correct |
1104 ms |
5076 KB |
Output is correct |
3 |
Correct |
1097 ms |
5184 KB |
Output is correct |
4 |
Correct |
1123 ms |
5072 KB |
Output is correct |
5 |
Correct |
1118 ms |
5644 KB |
Output is correct |
6 |
Correct |
1224 ms |
5116 KB |
Output is correct |
7 |
Correct |
1209 ms |
5056 KB |
Output is correct |
8 |
Correct |
1228 ms |
5164 KB |
Output is correct |
9 |
Correct |
25 ms |
1876 KB |
Output is correct |
10 |
Correct |
753 ms |
4280 KB |
Output is correct |
11 |
Correct |
763 ms |
4368 KB |
Output is correct |
12 |
Correct |
990 ms |
5360 KB |
Output is correct |
13 |
Correct |
992 ms |
5056 KB |
Output is correct |
14 |
Correct |
807 ms |
4080 KB |
Output is correct |
15 |
Correct |
390 ms |
2372 KB |
Output is correct |
16 |
Correct |
825 ms |
3920 KB |
Output is correct |
17 |
Correct |
806 ms |
4020 KB |
Output is correct |
18 |
Correct |
25 ms |
2004 KB |
Output is correct |
19 |
Correct |
828 ms |
3728 KB |
Output is correct |
20 |
Correct |
765 ms |
3776 KB |
Output is correct |
21 |
Correct |
743 ms |
3628 KB |
Output is correct |
22 |
Correct |
646 ms |
3920 KB |
Output is correct |
23 |
Correct |
640 ms |
3908 KB |
Output is correct |
24 |
Correct |
660 ms |
3920 KB |
Output is correct |
25 |
Correct |
627 ms |
3752 KB |
Output is correct |
26 |
Correct |
1157 ms |
5128 KB |
Output is correct |
27 |
Correct |
1209 ms |
4892 KB |
Output is correct |
28 |
Correct |
1159 ms |
5252 KB |
Output is correct |
29 |
Correct |
1014 ms |
4972 KB |
Output is correct |
30 |
Correct |
1178 ms |
5388 KB |
Output is correct |
31 |
Correct |
1168 ms |
5240 KB |
Output is correct |
32 |
Correct |
1204 ms |
5132 KB |
Output is correct |
33 |
Correct |
1121 ms |
5260 KB |
Output is correct |
34 |
Correct |
1130 ms |
5040 KB |
Output is correct |
35 |
Correct |
1130 ms |
5128 KB |
Output is correct |
36 |
Correct |
1018 ms |
5136 KB |
Output is correct |
37 |
Correct |
1027 ms |
5136 KB |
Output is correct |
38 |
Correct |
1012 ms |
5136 KB |
Output is correct |
39 |
Correct |
946 ms |
5036 KB |
Output is correct |
40 |
Correct |
937 ms |
5372 KB |
Output is correct |
41 |
Correct |
935 ms |
5132 KB |
Output is correct |
42 |
Correct |
915 ms |
4880 KB |
Output is correct |
43 |
Correct |
931 ms |
4936 KB |
Output is correct |
44 |
Correct |
915 ms |
5008 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
17 ms |
916 KB |
Output is correct |
4 |
Correct |
3 ms |
604 KB |
Output is correct |
5 |
Correct |
9 ms |
632 KB |
Output is correct |
6 |
Correct |
8 ms |
600 KB |
Output is correct |
7 |
Correct |
9 ms |
604 KB |
Output is correct |
8 |
Correct |
10 ms |
636 KB |
Output is correct |
9 |
Correct |
10 ms |
604 KB |
Output is correct |
10 |
Correct |
10 ms |
600 KB |
Output is correct |
11 |
Correct |
10 ms |
672 KB |
Output is correct |
12 |
Correct |
13 ms |
600 KB |
Output is correct |
13 |
Correct |
13 ms |
600 KB |
Output is correct |
14 |
Correct |
16 ms |
628 KB |
Output is correct |
15 |
Correct |
11 ms |
636 KB |
Output is correct |
16 |
Correct |
10 ms |
604 KB |
Output is correct |
17 |
Correct |
10 ms |
468 KB |
Output is correct |
18 |
Correct |
1094 ms |
5088 KB |
Output is correct |
19 |
Correct |
1104 ms |
5076 KB |
Output is correct |
20 |
Correct |
1097 ms |
5184 KB |
Output is correct |
21 |
Correct |
1123 ms |
5072 KB |
Output is correct |
22 |
Correct |
1118 ms |
5644 KB |
Output is correct |
23 |
Correct |
1224 ms |
5116 KB |
Output is correct |
24 |
Correct |
1209 ms |
5056 KB |
Output is correct |
25 |
Correct |
1228 ms |
5164 KB |
Output is correct |
26 |
Correct |
25 ms |
1876 KB |
Output is correct |
27 |
Correct |
753 ms |
4280 KB |
Output is correct |
28 |
Correct |
763 ms |
4368 KB |
Output is correct |
29 |
Correct |
990 ms |
5360 KB |
Output is correct |
30 |
Correct |
992 ms |
5056 KB |
Output is correct |
31 |
Correct |
807 ms |
4080 KB |
Output is correct |
32 |
Correct |
390 ms |
2372 KB |
Output is correct |
33 |
Correct |
825 ms |
3920 KB |
Output is correct |
34 |
Correct |
806 ms |
4020 KB |
Output is correct |
35 |
Correct |
25 ms |
2004 KB |
Output is correct |
36 |
Correct |
828 ms |
3728 KB |
Output is correct |
37 |
Correct |
765 ms |
3776 KB |
Output is correct |
38 |
Correct |
743 ms |
3628 KB |
Output is correct |
39 |
Correct |
646 ms |
3920 KB |
Output is correct |
40 |
Correct |
640 ms |
3908 KB |
Output is correct |
41 |
Correct |
660 ms |
3920 KB |
Output is correct |
42 |
Correct |
627 ms |
3752 KB |
Output is correct |
43 |
Correct |
1874 ms |
7624 KB |
Output is correct |
44 |
Correct |
25 ms |
1880 KB |
Output is correct |
45 |
Correct |
204 ms |
5072 KB |
Output is correct |
46 |
Correct |
118 ms |
5032 KB |
Output is correct |
47 |
Correct |
1280 ms |
6332 KB |
Output is correct |
48 |
Correct |
1842 ms |
7704 KB |
Output is correct |
49 |
Correct |
1290 ms |
6660 KB |
Output is correct |
50 |
Correct |
877 ms |
5268 KB |
Output is correct |
51 |
Correct |
878 ms |
4984 KB |
Output is correct |
52 |
Correct |
874 ms |
5232 KB |
Output is correct |
53 |
Correct |
1398 ms |
6284 KB |
Output is correct |
54 |
Correct |
1384 ms |
6272 KB |
Output is correct |
55 |
Correct |
1389 ms |
6308 KB |
Output is correct |
56 |
Correct |
1140 ms |
6940 KB |
Output is correct |
57 |
Correct |
1225 ms |
6584 KB |
Output is correct |
58 |
Correct |
1892 ms |
7432 KB |
Output is correct |
59 |
Correct |
1881 ms |
7428 KB |
Output is correct |
60 |
Correct |
1890 ms |
7460 KB |
Output is correct |
61 |
Correct |
1879 ms |
7428 KB |
Output is correct |
62 |
Correct |
1589 ms |
6904 KB |
Output is correct |
63 |
Correct |
1595 ms |
6836 KB |
Output is correct |
64 |
Correct |
1808 ms |
7020 KB |
Output is correct |
65 |
Correct |
1265 ms |
6132 KB |
Output is correct |
66 |
Correct |
1157 ms |
5128 KB |
Output is correct |
67 |
Correct |
1209 ms |
4892 KB |
Output is correct |
68 |
Correct |
1159 ms |
5252 KB |
Output is correct |
69 |
Correct |
1014 ms |
4972 KB |
Output is correct |
70 |
Correct |
1178 ms |
5388 KB |
Output is correct |
71 |
Correct |
1168 ms |
5240 KB |
Output is correct |
72 |
Correct |
1204 ms |
5132 KB |
Output is correct |
73 |
Correct |
1121 ms |
5260 KB |
Output is correct |
74 |
Correct |
1130 ms |
5040 KB |
Output is correct |
75 |
Correct |
1130 ms |
5128 KB |
Output is correct |
76 |
Correct |
1018 ms |
5136 KB |
Output is correct |
77 |
Correct |
1027 ms |
5136 KB |
Output is correct |
78 |
Correct |
1012 ms |
5136 KB |
Output is correct |
79 |
Correct |
946 ms |
5036 KB |
Output is correct |
80 |
Correct |
937 ms |
5372 KB |
Output is correct |
81 |
Correct |
935 ms |
5132 KB |
Output is correct |
82 |
Correct |
915 ms |
4880 KB |
Output is correct |
83 |
Correct |
931 ms |
4936 KB |
Output is correct |
84 |
Correct |
915 ms |
5008 KB |
Output is correct |
85 |
Correct |
2084 ms |
7344 KB |
Output is correct |
86 |
Correct |
210 ms |
5580 KB |
Output is correct |
87 |
Correct |
139 ms |
5840 KB |
Output is correct |
88 |
Correct |
1462 ms |
7304 KB |
Output is correct |
89 |
Correct |
2106 ms |
8708 KB |
Output is correct |
90 |
Correct |
1461 ms |
7344 KB |
Output is correct |
91 |
Correct |
1157 ms |
5928 KB |
Output is correct |
92 |
Correct |
1127 ms |
6184 KB |
Output is correct |
93 |
Correct |
1277 ms |
5796 KB |
Output is correct |
94 |
Correct |
1645 ms |
7108 KB |
Output is correct |
95 |
Correct |
1624 ms |
7628 KB |
Output is correct |
96 |
Correct |
1678 ms |
7308 KB |
Output is correct |
97 |
Correct |
1343 ms |
7404 KB |
Output is correct |
98 |
Correct |
1350 ms |
6960 KB |
Output is correct |
99 |
Correct |
2103 ms |
8844 KB |
Output is correct |
100 |
Correct |
2109 ms |
8716 KB |
Output is correct |
101 |
Correct |
2123 ms |
8976 KB |
Output is correct |
102 |
Correct |
2093 ms |
8624 KB |
Output is correct |
103 |
Correct |
1835 ms |
7820 KB |
Output is correct |
104 |
Correct |
1867 ms |
7992 KB |
Output is correct |
105 |
Correct |
1661 ms |
7632 KB |
Output is correct |
106 |
Correct |
1432 ms |
7444 KB |
Output is correct |
107 |
Correct |
1669 ms |
7992 KB |
Output is correct |
108 |
Correct |
2045 ms |
8468 KB |
Output is correct |
109 |
Correct |
1480 ms |
6280 KB |
Output is correct |