#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define F first
#define S second
#define All(x) (x).begin(),(x).end()
#define len(x) (int)(x).size()
#define pb push_back
struct edge{
int u, v, w;
};
const int N = 1e5 + 7, SQ = 1000;
int n, m, q, ans[N], idx[N], par[N], T[N], X[N], Y[N];
vector<pair<pii, int>> record;
bool change[N], frst[N];
vector<int> qu[N];
edge ed[N];
int get_par(int u) {
return par[u] < 0? u: get_par(par[u]);
}
void merge(int u, int v) {
u = get_par(u), v = get_par(v);
if (u == v) {
record.pb({{-1, -1}, 0});
return;
}
if (par[u] < par[v])
swap(u, v);
record.pb({{u, v}, par[u]});
par[v] += par[u];
par[u] = v;
}
void undo() {
pair<pii, int> r = record.back();
record.pop_back();
if (r.F.F == -1)
return;
int u = r.F.F, v = r.F.S;
par[u] = r.S;
par[v] -= par[u];
}
int32_t main() {
ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 0; i < m; i++) {
cin >> ed[i].u >> ed[i].v >> ed[i].w;
ed[i].u--, ed[i].v--;
}
cin >> q;
for (int i = 0; i < q; i++) {
cin >> T[i] >> X[i] >> Y[i];
X[i]--;
}
vector<int> vec;
for (int i = 0; i < q; i += SQ) {
vec.clear();
fill(change, change + m, 0);
iota(idx, idx + m, 0);
sort(idx, idx + m, [] (int i, int j) {
return ed[i].w < ed[j].w;
});
for (int j = i; j < min(q, i + SQ); j++)
if (T[j] == 1)
change[X[j]] = true;
for (int i = 0; i < m; i++)
vec.pb(ed[idx[i]].w);
for (int i = 0; i <= m; i++)
qu[i].clear();
for (int j = i; j < min(q, i + SQ); j++)
if (T[j] == 2)
qu[lower_bound(All(vec), Y[j]) - vec.begin()].pb(j);
fill(par, par + n, -1);
record.clear();
for (int j = m; j >= 0; j--) {
if (j < m && !change[idx[j]]) {
int u = ed[idx[j]].u, v = ed[idx[j]].v;
merge(u, v);
}
for (int idx: qu[j]) {
int cnt = 0;
for (int k = idx; k >= i; k--)
if (T[k] == 1 && !frst[X[k]]) {
frst[X[k]] = true;
if (Y[k] >= Y[idx]) {
int u = ed[X[k]].u, v = ed[X[k]].v;
merge(u, v);
cnt++;
}
}
for (int k = i; k < min(q, i + SQ); k++)
if (T[k] == 1 && !frst[X[k]]) {
if (ed[X[k]].w >= Y[idx]) {
int u = ed[X[k]].u, v = ed[X[k]].v;
merge(u, v);
cnt++;
}
}
ans[idx] = abs(par[get_par(X[idx])]);
while (cnt--)
undo();
for (int j = i; j < min(q, i + SQ); j++)
frst[X[j]] = false;
}
}
for (int j = i; j < min(q, i + SQ); j++)
if (T[j] == 1)
ed[X[j]].w = Y[j];
}
for (int i = 0; i < q; i++)
if (T[i] == 2)
cout << ans[i] << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
1 ms |
4456 KB |
Output is correct |
3 |
Correct |
38 ms |
4956 KB |
Output is correct |
4 |
Correct |
16 ms |
4444 KB |
Output is correct |
5 |
Correct |
32 ms |
4664 KB |
Output is correct |
6 |
Correct |
27 ms |
4680 KB |
Output is correct |
7 |
Correct |
26 ms |
4952 KB |
Output is correct |
8 |
Correct |
29 ms |
4444 KB |
Output is correct |
9 |
Correct |
24 ms |
4688 KB |
Output is correct |
10 |
Correct |
30 ms |
4700 KB |
Output is correct |
11 |
Correct |
30 ms |
4684 KB |
Output is correct |
12 |
Correct |
30 ms |
4676 KB |
Output is correct |
13 |
Correct |
38 ms |
4444 KB |
Output is correct |
14 |
Correct |
35 ms |
4444 KB |
Output is correct |
15 |
Correct |
34 ms |
4664 KB |
Output is correct |
16 |
Correct |
25 ms |
4700 KB |
Output is correct |
17 |
Correct |
25 ms |
4700 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1058 ms |
7816 KB |
Output is correct |
2 |
Correct |
1059 ms |
7856 KB |
Output is correct |
3 |
Correct |
1090 ms |
8160 KB |
Output is correct |
4 |
Correct |
1102 ms |
8140 KB |
Output is correct |
5 |
Correct |
1102 ms |
7856 KB |
Output is correct |
6 |
Correct |
1401 ms |
7500 KB |
Output is correct |
7 |
Correct |
1388 ms |
7172 KB |
Output is correct |
8 |
Correct |
1448 ms |
7284 KB |
Output is correct |
9 |
Correct |
149 ms |
5784 KB |
Output is correct |
10 |
Correct |
683 ms |
7252 KB |
Output is correct |
11 |
Correct |
681 ms |
7264 KB |
Output is correct |
12 |
Correct |
1055 ms |
7628 KB |
Output is correct |
13 |
Correct |
962 ms |
7536 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
791 ms |
7336 KB |
Output is correct |
2 |
Correct |
478 ms |
6504 KB |
Output is correct |
3 |
Correct |
837 ms |
7432 KB |
Output is correct |
4 |
Correct |
773 ms |
7760 KB |
Output is correct |
5 |
Correct |
149 ms |
5716 KB |
Output is correct |
6 |
Correct |
822 ms |
7428 KB |
Output is correct |
7 |
Correct |
744 ms |
7584 KB |
Output is correct |
8 |
Correct |
700 ms |
7312 KB |
Output is correct |
9 |
Correct |
680 ms |
7632 KB |
Output is correct |
10 |
Correct |
657 ms |
7472 KB |
Output is correct |
11 |
Correct |
583 ms |
6860 KB |
Output is correct |
12 |
Correct |
546 ms |
6928 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1724 ms |
10080 KB |
Output is correct |
2 |
Correct |
150 ms |
6996 KB |
Output is correct |
3 |
Correct |
180 ms |
9300 KB |
Output is correct |
4 |
Correct |
93 ms |
9548 KB |
Output is correct |
5 |
Correct |
928 ms |
11092 KB |
Output is correct |
6 |
Correct |
1637 ms |
13676 KB |
Output is correct |
7 |
Correct |
933 ms |
11060 KB |
Output is correct |
8 |
Correct |
848 ms |
10632 KB |
Output is correct |
9 |
Correct |
844 ms |
10836 KB |
Output is correct |
10 |
Correct |
851 ms |
10068 KB |
Output is correct |
11 |
Correct |
1264 ms |
12032 KB |
Output is correct |
12 |
Correct |
1244 ms |
12140 KB |
Output is correct |
13 |
Correct |
1250 ms |
11576 KB |
Output is correct |
14 |
Correct |
880 ms |
11472 KB |
Output is correct |
15 |
Correct |
901 ms |
10900 KB |
Output is correct |
16 |
Correct |
1737 ms |
13488 KB |
Output is correct |
17 |
Correct |
1730 ms |
13912 KB |
Output is correct |
18 |
Correct |
1734 ms |
13500 KB |
Output is correct |
19 |
Correct |
1704 ms |
13452 KB |
Output is correct |
20 |
Correct |
1454 ms |
11504 KB |
Output is correct |
21 |
Correct |
1468 ms |
11580 KB |
Output is correct |
22 |
Correct |
1680 ms |
12696 KB |
Output is correct |
23 |
Correct |
979 ms |
10572 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1058 ms |
7816 KB |
Output is correct |
2 |
Correct |
1059 ms |
7856 KB |
Output is correct |
3 |
Correct |
1090 ms |
8160 KB |
Output is correct |
4 |
Correct |
1102 ms |
8140 KB |
Output is correct |
5 |
Correct |
1102 ms |
7856 KB |
Output is correct |
6 |
Correct |
1401 ms |
7500 KB |
Output is correct |
7 |
Correct |
1388 ms |
7172 KB |
Output is correct |
8 |
Correct |
1448 ms |
7284 KB |
Output is correct |
9 |
Correct |
149 ms |
5784 KB |
Output is correct |
10 |
Correct |
683 ms |
7252 KB |
Output is correct |
11 |
Correct |
681 ms |
7264 KB |
Output is correct |
12 |
Correct |
1055 ms |
7628 KB |
Output is correct |
13 |
Correct |
962 ms |
7536 KB |
Output is correct |
14 |
Correct |
791 ms |
7336 KB |
Output is correct |
15 |
Correct |
478 ms |
6504 KB |
Output is correct |
16 |
Correct |
837 ms |
7432 KB |
Output is correct |
17 |
Correct |
773 ms |
7760 KB |
Output is correct |
18 |
Correct |
149 ms |
5716 KB |
Output is correct |
19 |
Correct |
822 ms |
7428 KB |
Output is correct |
20 |
Correct |
744 ms |
7584 KB |
Output is correct |
21 |
Correct |
700 ms |
7312 KB |
Output is correct |
22 |
Correct |
680 ms |
7632 KB |
Output is correct |
23 |
Correct |
657 ms |
7472 KB |
Output is correct |
24 |
Correct |
583 ms |
6860 KB |
Output is correct |
25 |
Correct |
546 ms |
6928 KB |
Output is correct |
26 |
Correct |
1044 ms |
7928 KB |
Output is correct |
27 |
Correct |
1190 ms |
7756 KB |
Output is correct |
28 |
Correct |
1083 ms |
8156 KB |
Output is correct |
29 |
Correct |
978 ms |
7508 KB |
Output is correct |
30 |
Correct |
1156 ms |
7872 KB |
Output is correct |
31 |
Correct |
1162 ms |
8424 KB |
Output is correct |
32 |
Correct |
1135 ms |
8168 KB |
Output is correct |
33 |
Correct |
1093 ms |
8008 KB |
Output is correct |
34 |
Correct |
1088 ms |
8020 KB |
Output is correct |
35 |
Correct |
1092 ms |
7896 KB |
Output is correct |
36 |
Correct |
1002 ms |
7520 KB |
Output is correct |
37 |
Correct |
987 ms |
7528 KB |
Output is correct |
38 |
Correct |
956 ms |
7504 KB |
Output is correct |
39 |
Correct |
918 ms |
8012 KB |
Output is correct |
40 |
Correct |
923 ms |
7984 KB |
Output is correct |
41 |
Correct |
901 ms |
7888 KB |
Output is correct |
42 |
Correct |
760 ms |
7216 KB |
Output is correct |
43 |
Correct |
770 ms |
7080 KB |
Output is correct |
44 |
Correct |
779 ms |
6988 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
1 ms |
4456 KB |
Output is correct |
3 |
Correct |
38 ms |
4956 KB |
Output is correct |
4 |
Correct |
16 ms |
4444 KB |
Output is correct |
5 |
Correct |
32 ms |
4664 KB |
Output is correct |
6 |
Correct |
27 ms |
4680 KB |
Output is correct |
7 |
Correct |
26 ms |
4952 KB |
Output is correct |
8 |
Correct |
29 ms |
4444 KB |
Output is correct |
9 |
Correct |
24 ms |
4688 KB |
Output is correct |
10 |
Correct |
30 ms |
4700 KB |
Output is correct |
11 |
Correct |
30 ms |
4684 KB |
Output is correct |
12 |
Correct |
30 ms |
4676 KB |
Output is correct |
13 |
Correct |
38 ms |
4444 KB |
Output is correct |
14 |
Correct |
35 ms |
4444 KB |
Output is correct |
15 |
Correct |
34 ms |
4664 KB |
Output is correct |
16 |
Correct |
25 ms |
4700 KB |
Output is correct |
17 |
Correct |
25 ms |
4700 KB |
Output is correct |
18 |
Correct |
1058 ms |
7816 KB |
Output is correct |
19 |
Correct |
1059 ms |
7856 KB |
Output is correct |
20 |
Correct |
1090 ms |
8160 KB |
Output is correct |
21 |
Correct |
1102 ms |
8140 KB |
Output is correct |
22 |
Correct |
1102 ms |
7856 KB |
Output is correct |
23 |
Correct |
1401 ms |
7500 KB |
Output is correct |
24 |
Correct |
1388 ms |
7172 KB |
Output is correct |
25 |
Correct |
1448 ms |
7284 KB |
Output is correct |
26 |
Correct |
149 ms |
5784 KB |
Output is correct |
27 |
Correct |
683 ms |
7252 KB |
Output is correct |
28 |
Correct |
681 ms |
7264 KB |
Output is correct |
29 |
Correct |
1055 ms |
7628 KB |
Output is correct |
30 |
Correct |
962 ms |
7536 KB |
Output is correct |
31 |
Correct |
791 ms |
7336 KB |
Output is correct |
32 |
Correct |
478 ms |
6504 KB |
Output is correct |
33 |
Correct |
837 ms |
7432 KB |
Output is correct |
34 |
Correct |
773 ms |
7760 KB |
Output is correct |
35 |
Correct |
149 ms |
5716 KB |
Output is correct |
36 |
Correct |
822 ms |
7428 KB |
Output is correct |
37 |
Correct |
744 ms |
7584 KB |
Output is correct |
38 |
Correct |
700 ms |
7312 KB |
Output is correct |
39 |
Correct |
680 ms |
7632 KB |
Output is correct |
40 |
Correct |
657 ms |
7472 KB |
Output is correct |
41 |
Correct |
583 ms |
6860 KB |
Output is correct |
42 |
Correct |
546 ms |
6928 KB |
Output is correct |
43 |
Correct |
1724 ms |
10080 KB |
Output is correct |
44 |
Correct |
150 ms |
6996 KB |
Output is correct |
45 |
Correct |
180 ms |
9300 KB |
Output is correct |
46 |
Correct |
93 ms |
9548 KB |
Output is correct |
47 |
Correct |
928 ms |
11092 KB |
Output is correct |
48 |
Correct |
1637 ms |
13676 KB |
Output is correct |
49 |
Correct |
933 ms |
11060 KB |
Output is correct |
50 |
Correct |
848 ms |
10632 KB |
Output is correct |
51 |
Correct |
844 ms |
10836 KB |
Output is correct |
52 |
Correct |
851 ms |
10068 KB |
Output is correct |
53 |
Correct |
1264 ms |
12032 KB |
Output is correct |
54 |
Correct |
1244 ms |
12140 KB |
Output is correct |
55 |
Correct |
1250 ms |
11576 KB |
Output is correct |
56 |
Correct |
880 ms |
11472 KB |
Output is correct |
57 |
Correct |
901 ms |
10900 KB |
Output is correct |
58 |
Correct |
1737 ms |
13488 KB |
Output is correct |
59 |
Correct |
1730 ms |
13912 KB |
Output is correct |
60 |
Correct |
1734 ms |
13500 KB |
Output is correct |
61 |
Correct |
1704 ms |
13452 KB |
Output is correct |
62 |
Correct |
1454 ms |
11504 KB |
Output is correct |
63 |
Correct |
1468 ms |
11580 KB |
Output is correct |
64 |
Correct |
1680 ms |
12696 KB |
Output is correct |
65 |
Correct |
979 ms |
10572 KB |
Output is correct |
66 |
Correct |
1044 ms |
7928 KB |
Output is correct |
67 |
Correct |
1190 ms |
7756 KB |
Output is correct |
68 |
Correct |
1083 ms |
8156 KB |
Output is correct |
69 |
Correct |
978 ms |
7508 KB |
Output is correct |
70 |
Correct |
1156 ms |
7872 KB |
Output is correct |
71 |
Correct |
1162 ms |
8424 KB |
Output is correct |
72 |
Correct |
1135 ms |
8168 KB |
Output is correct |
73 |
Correct |
1093 ms |
8008 KB |
Output is correct |
74 |
Correct |
1088 ms |
8020 KB |
Output is correct |
75 |
Correct |
1092 ms |
7896 KB |
Output is correct |
76 |
Correct |
1002 ms |
7520 KB |
Output is correct |
77 |
Correct |
987 ms |
7528 KB |
Output is correct |
78 |
Correct |
956 ms |
7504 KB |
Output is correct |
79 |
Correct |
918 ms |
8012 KB |
Output is correct |
80 |
Correct |
923 ms |
7984 KB |
Output is correct |
81 |
Correct |
901 ms |
7888 KB |
Output is correct |
82 |
Correct |
760 ms |
7216 KB |
Output is correct |
83 |
Correct |
770 ms |
7080 KB |
Output is correct |
84 |
Correct |
779 ms |
6988 KB |
Output is correct |
85 |
Correct |
1970 ms |
13056 KB |
Output is correct |
86 |
Correct |
205 ms |
9296 KB |
Output is correct |
87 |
Correct |
111 ms |
9304 KB |
Output is correct |
88 |
Correct |
1125 ms |
10832 KB |
Output is correct |
89 |
Correct |
1885 ms |
13492 KB |
Output is correct |
90 |
Correct |
1118 ms |
10828 KB |
Output is correct |
91 |
Correct |
1073 ms |
10540 KB |
Output is correct |
92 |
Correct |
1077 ms |
10728 KB |
Output is correct |
93 |
Correct |
1294 ms |
9664 KB |
Output is correct |
94 |
Correct |
1585 ms |
11984 KB |
Output is correct |
95 |
Correct |
1522 ms |
11860 KB |
Output is correct |
96 |
Correct |
1669 ms |
11284 KB |
Output is correct |
97 |
Correct |
1016 ms |
11028 KB |
Output is correct |
98 |
Correct |
934 ms |
10772 KB |
Output is correct |
99 |
Correct |
1968 ms |
12864 KB |
Output is correct |
100 |
Correct |
1970 ms |
12996 KB |
Output is correct |
101 |
Correct |
1988 ms |
13024 KB |
Output is correct |
102 |
Correct |
1985 ms |
12952 KB |
Output is correct |
103 |
Correct |
1817 ms |
11676 KB |
Output is correct |
104 |
Correct |
1839 ms |
11424 KB |
Output is correct |
105 |
Correct |
1500 ms |
11304 KB |
Output is correct |
106 |
Correct |
1213 ms |
11248 KB |
Output is correct |
107 |
Correct |
1583 ms |
11612 KB |
Output is correct |
108 |
Correct |
1876 ms |
12456 KB |
Output is correct |
109 |
Correct |
1249 ms |
10080 KB |
Output is correct |